Изучение методов сортировки. Алгоритм сортировки простым обменом

Изучение методов сортировки

         Сортировка – операция, упорядочивающая последовательность (массив) элементов по ключам. Ключ – некоторое числовое свойство элемента массива, т.е. каждому элементу массива ставиться в соответствие некоторое число, которое называется ключом элемента.

         Если мы имеем числовой массив, то ключ элемента – это сам элемент. В этом случае сортировка массива – это упорядочивание массива (перестановка его элементов) таким образом, чтобы получилась неубывающая или невозрастающая последовательность.

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

         Если слова состоят из букв и цифр, как, например, имена файлов, то считается, что любая цифра имеет меньший ключ, чем любая буква. Как мы знаем, каждому символу, изображенному на клавиатуре компьютера, соответствует код в некоторой кодовой таблице. Этот код и есть ключ, по которому происходит упорядочивание имен. Так имена:

h10ga,  g2, g10, ha10g

будут упорядочиваться в соответствии с возрастанием кодов символов

следующим образом:

g10, g2, h10ga, ha10g.

         Указанный выше принцип упорядочивания слов называется лексикографическим порядком.

         Разработкой различных алгоритмов сортировки информации, хранящейся в оперативной памяти компьютера или на его магнитном диске, стали заниматься уже давно. Интерес к этой проблеме обусловлен тем, что по оценке специалистов 25% всего времени обработки информации расходуется на сортировку данных.

         Ясно, что с отсортированными данными работать легче, чем с произвольно расположенными. Когда элементы отсортированы, их проще найти и установить, что их нет. Представьте себе, что в толковом словаре слова будут расположены в том порядке, в каком составители получали их объяснения от специалистов. Как вы будете искать нужное вам слово?

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

         Ниже рассматриваются  алгоритмы сортировки числовых массивов, но все сказанное справедливо и для произвольных массивов записей.

         Заметим ещё в заключении, что, когда говорят возрастание (убывание), то предполагают, что в массиве одинаковых элементов нет. В общем случае надо вместо “возрастания” говорить “неубывание”, а вместо “убывание”  – “невозрастание”.

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

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

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

или

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

Мы за скорость будем принимать отношение количества сравнений к общему числу элементов.

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

·  простые (прямые) методы сортировки;

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

·   

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

·  сортировка обменом (“пузырьковая” сортировка);

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

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

·  сортировка методом попарного сравнения).

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

Классификация методов сортировки

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