Довольно часто в спортивном программировании или же просто реализации алгоритмов необходимо отсортировать массив входных данных по определённому критерию. В то время как в ответе требуется исходный порядок. В статье я рассмотрю несколько способов сделать это минимальной кровью на C++. Если интересна эта тематика или имеются интересные предложения, прошу под кат…
Автор изображения: Tobias Rad, лицензия Creative Commons Attribution-Share Alike 3.0 Unported
Первая идея была отсортировать массив своим алгоритмом, запомнить все пары обменов значений в массиве, кого с кем меняли местами. И когда потребуется вернуть исходный порядок, повторить эти же обмены в обратном порядке. Конечно же свой алгоритм сортировки, написанный за пару минут, даже отдалённо не догоняет std::sort(). Потому появилась вторая идея, запоминать начальные индексы записей и сортировать по ним при помощи std::sort().
В приведенных способах при заполнении массива данными необходимо поле Domino::index заполнять порядковым номером записи.
Исходник можно взять здесь: http://codepad.org/0PWSzTBc
Исходник можно взять здесь: http://codepad.org/1zsTnk4s
Исходник можно взять здесь: http://codepad.org/5WRgCxLw
Первые два способа очень похожи, за исключением оператора, который передаётся явным образом или используется по-умолчанию функцией сортировки. Третий способ просто показывает насколько проще можно получить тот же результат, описывая оператор прямо в месте его использования. К сожалению, далеко не все платформы для проведения соревнований по спортивному программированию поддерживают C++0x.
Автор изображения: Tobias Rad, лицензия Creative Commons Attribution-Share Alike 3.0 Unported
Первая идея была отсортировать массив своим алгоритмом, запомнить все пары обменов значений в массиве, кого с кем меняли местами. И когда потребуется вернуть исходный порядок, повторить эти же обмены в обратном порядке. Конечно же свой алгоритм сортировки, написанный за пару минут, даже отдалённо не догоняет std::sort(). Потому появилась вторая идея, запоминать начальные индексы записей и сортировать по ним при помощи std::sort().
В приведенных способах при заполнении массива данными необходимо поле Domino::index заполнять порядковым номером записи.
Первый способ, с использованием статического члена и функтора:
Исходник можно взять здесь: http://codepad.org/0PWSzTBc
Второй способ, с использованием статического члена и оператора<:
Исходник можно взять здесь: http://codepad.org/1zsTnk4s
Третий способ, с использованием лямбд (C++0x):
Исходник можно взять здесь: http://codepad.org/5WRgCxLw
Первые два способа очень похожи, за исключением оператора, который передаётся явным образом или используется по-умолчанию функцией сортировки. Третий способ просто показывает насколько проще можно получить тот же результат, описывая оператор прямо в месте его использования. К сожалению, далеко не все платформы для проведения соревнований по спортивному программированию поддерживают C++0x.
