Методы внутренней сортировки

Под сортировкой понимают, процесс перестановки объектов множества в определенном порядке. Целью алгоритма сортировки является переорганизация записей в файле так, чтобы они располагались в нем в каком-либо строго определенном порядке (обычно в алфавитном или числовом).

Если сортируемый файл целиком помещается в память (или целиком помещается в массив), то для него мы используем внутренние методы сортировки. Сортировка данных с ленты или диска называется внешней сортировкой.

Главное отличие между ними состоит в том, что при внутренней сортировке любая запись - легко доступна, в то время как при внешней сортировке мы можем пользоваться записями только последовательно, или большими блоками.

Для оценки быстродействия алгоритмов различных методов сорти­ровки, как правило, используют два показателя:

• количество присваиваний;

• количество сравнений.

Все методы сортировки можно разделить на две большие группы:

• прямые методы сортировки;

• улучшенные методы сортировки.

Прямые методы сортировки по принципу, лежащему в основе ме­тода, в свою очередь разделяются на три подгруппы:

1) сортировка выбором (выделением);

2) сортировка вставкой (включением);

3) сортировка обменом ("пузырьковая" сортировка).

Улучшенные методы сортировки основываются на тех же принци­пах, что и прямые, но используют некоторые оригинальные идеи для ус­корения процесса сортировки. Прямые методы на практике используют­ся довольно редко, так как имеют относительно низкое быстродействие. Однако они хорошо показывают суть основанных на них улучшенных методов. Кроме того, в некоторых случаях (как правило, при небольшой длине массива и/или особом исходном расположении элементов массива) некоторые из прямых методов могут даже превзойти улучшенные методы.

Сортировка Выбором

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

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

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

Сортировка Вставкой

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

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

Пузырьковая Сортировка

Проходит через массив, обменивая, если нужно элементы; когда на каком-то шаге обменов не потребуется - сортировка окончена.

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

Характеристики Простейших Сортировок

1 Сортировка выбором использует около N2/2 сравнений и N обменов.

2 Сортировка вставкой использует около N2/4 сравнений и N2/8 обменов в среднем, и в два раза больше в наихудшем случае.

3 Пузырьковая сортировка использует около N2/2 сравнений и N2/2 обменов в среднем и наихудшем случаях.

4 Сортировка вставкой линейна для "почти сортированных" файлов.

5 Сортировка выбором линейна для файлов с большими записями и маленькими ключами.