1.2. Сортировка выбором

Один из самых простых методов сортировки работает следующим образом: находим наименьший элемент в массиве и обмениваем его с элементом находящимся на первом месте. Потом повторяем процесс со второй позиции в файле и найденный элемент обмениваем со вторым элементном и так далее пока весь массив не будет отсортирован. Этот метод называется сортировка выбором, поскольку он работает, циклически выбирая наименьший из оставшихся элементов.

Этот метод работает очень хорошо для небольших файлов. Его «внутренний цикл» состоит из сравнения a[i]<a[min] (плюс код необходимый для увеличения j и проверки на то, что он не превысил N), что вряд ли можно еще упростить.

Кроме того, хотя сортировка выбором является методом «грубой силы», он имеет очень важное применение: поскольку каждый элемент передвигается не более чем раз, то он очень хорош для больших записей с маленькими ключами.

1.3.Сортировка вставкой

Метод сортировки вставкой, почти столь же прост, что и сортировка выбором, но гораздо более гибкий. Этот метод часто используют при сортировке карт: берем один элемент и вставляем его в нужное место среди тех, что мы уже обработали (тем самым, оставляя их отсортированными). Рассматриваемый элемент вставляется в позицию посредством передвижения большего элемента на одну позицию вправо и затем размещением меньшего элемента в освободившуюся позицию.

Этот процесс реализован в следующей программе. Для каждого i от 2 до N, под массив a[1..i] сортируется посредством помещения a[i] в подходящую позицию среди уже отсортированных элементов:

Также как и при сортировке, выбором, в процессе сортировки элементы слева от указателя i находятся уже в сортированном порядке, но они не обязательно находятся в своей последней позиции, поскольку их еще могут передвинуть направо, чтобы вставить более маленькие элементы встреченные позже. Массив становится полностью сортированным, когда указатель достигает правого края.

Виды сортировок вставкой:

• Сортировка простыми вставками

• Сортировка бинарными вставками

• Сортировка двухпутевыми вставками. Здесь первый - элемент помещается в середину области вывода, и место для последующих элементов освобождается при помощи сдвигов влево или вправо, туда, куда удобнее. Таким образом, удается сэкономить примерно половину времени работы по сравнению с простыми вставками за счет некоторого усложнения программы.

1.4. Метод Шелла

Этот метод является модификацией метода пузырька. Такой метод предложен в 1959 г. Дональдом Л. Шеллом. Основная его идея заключается в том, чтобы вначале устранить массовый беспорядок в сортируемой последовательности, сравнивая, далеко отстоящие друг от друга элементы. Интервал между сравниваемыми элементами постепенно уменьшают до единицы, то есть на первом проходе гарантируется, что все элементы, расстояние между которыми L₁ < N – 1, упорядочиваются друг относительно друга, на втором то же гарантируется для элементов, расстояние между которыми L₂ < L₁ и так далее до последнего k-ого прохода, когда должно выполняться L_k = 1. Обычно расстояние L для сортировки Шелла берутся из приблизительного соотношения L_k ≤ 2L_k-1 и L₁ ≤ N/2, но лучше для расстояний L брать простые числа, ближайшие к L_k, выбираемой по описанной выше схеме.