Довольно часто в спортивном программировании или же просто реализации алгоритмов необходимо отсортировать массив входных данных по определённому критерию. В то время как в ответе требуется исходный порядок. В статье я рассмотрю несколько способов сделать это минимальной кровью на C++. Если интересна эта тематика или имеются интересные предложения, прошу под кат…
![](https://habrastorage.org/r/w780q1/storage/49967509/776bc607/529163eb/a53ff5da.jpg)
Автор изображения: Tobias Rad, лицензия Creative Commons Attribution-Share Alike 3.0 Unported
Первая идея была отсортировать массив своим алгоритмом, запомнить все пары обменов значений в массиве, кого с кем меняли местами. И когда потребуется вернуть исходный порядок, повторить эти же обмены в обратном порядке. Конечно же свой алгоритм сортировки, написанный за пару минут, даже отдалённо не догоняет std::sort(). Потому появилась вторая идея, запоминать начальные индексы записей и сортировать по ним при помощи std::sort().
В приведенных способах при заполнении массива данными необходимо поле Domino::index заполнять порядковым номером записи.
![](https://habrastorage.org/r/w1560/storage/9a5f9b3e/3396c7d4/a398c530/5b06c62b.png)
Исходник можно взять здесь: http://codepad.org/0PWSzTBc
![](https://habrastorage.org/r/w1560/storage/0453192f/ab98a69b/27eeb73b/61d76f23.png)
Исходник можно взять здесь: http://codepad.org/1zsTnk4s
![](https://habrastorage.org/r/w1560/storage/d5bbcd9d/6b43061b/f49d9b39/1d7925d1.png)
Исходник можно взять здесь: http://codepad.org/5WRgCxLw
Первые два способа очень похожи, за исключением оператора, который передаётся явным образом или используется по-умолчанию функцией сортировки. Третий способ просто показывает насколько проще можно получить тот же результат, описывая оператор прямо в месте его использования. К сожалению, далеко не все платформы для проведения соревнований по спортивному программированию поддерживают C++0x.
![](https://habrastorage.org/storage/49967509/776bc607/529163eb/a53ff5da.jpg)
Автор изображения: Tobias Rad, лицензия Creative Commons Attribution-Share Alike 3.0 Unported
Первая идея была отсортировать массив своим алгоритмом, запомнить все пары обменов значений в массиве, кого с кем меняли местами. И когда потребуется вернуть исходный порядок, повторить эти же обмены в обратном порядке. Конечно же свой алгоритм сортировки, написанный за пару минут, даже отдалённо не догоняет std::sort(). Потому появилась вторая идея, запоминать начальные индексы записей и сортировать по ним при помощи std::sort().
В приведенных способах при заполнении массива данными необходимо поле Domino::index заполнять порядковым номером записи.
Первый способ, с использованием статического члена и функтора:
![](https://habrastorage.org/storage/9a5f9b3e/3396c7d4/a398c530/5b06c62b.png)
Исходник можно взять здесь: http://codepad.org/0PWSzTBc
Второй способ, с использованием статического члена и оператора<:
![](https://habrastorage.org/storage/0453192f/ab98a69b/27eeb73b/61d76f23.png)
Исходник можно взять здесь: http://codepad.org/1zsTnk4s
Третий способ, с использованием лямбд (C++0x):
![](https://habrastorage.org/storage/d5bbcd9d/6b43061b/f49d9b39/1d7925d1.png)
Исходник можно взять здесь: http://codepad.org/5WRgCxLw
Первые два способа очень похожи, за исключением оператора, который передаётся явным образом или используется по-умолчанию функцией сортировки. Третий способ просто показывает насколько проще можно получить тот же результат, описывая оператор прямо в месте его использования. К сожалению, далеко не все платформы для проведения соревнований по спортивному программированию поддерживают C++0x.