Введение в сортировку

Под сортировкой понимают процесс перестановки объектов данного множества в определенном порядке.

Цель сортировки — облегчить последующий поиск элементов в отсортированном множестве. Следовательно, методы сортировки важны особенно при обработке данных [1, 3, 9, 10, 13].

Зависимость выбора алгоритма от структуры данных — явление довольно частое, и в случае сортировки она настолько сильна, что методы сортировки обычно разделяют на две категории: сортировка массивов (внутренняя сортировка) и сортировка файлов (внешняя сортировка). Массивы обычно располагаются в оперативной памяти, для которой характерен быстрый произвольный доступ; файлы хранятся в более медленной, но более вместительной внешней памяти, на дисках.

Введем некоторую терминологию [3]. Пусть даны элементы ai,ci2,...,a_n. Сортировка означает перестановку элементов в таком порядке а^\, ^аю., ■■■,^кп-, что при заданной упорядочивающей функции f(x) справедливо отношение

f(a_xl)<f(a_xl)<...<f(a_m).

Обычно упорядочивающая функция не вычисляется, а содержится в виде явной компоненты каждого элемента — поля. Её значение называется ключом элемента. Следовательно, для представления элемента a_t подходит структурный тип данных:

struct item

{ int key;

описание других компонент;

};,

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

Сортировка массивов. Основное требование к методам сортировки массивов — экономное использование памяти. Это значит, что перестановки элементов нужно выполнять на том же месте оперативной памяти, где они находятся, и что методы, которые пересылают элементы из массива А в массив В, не представляют интереса. Таким образом, выбирая метод сортировки, руководствуясь критерием экономии памяти, классификацию алгоритмов, проводят в соответствии с их эффективностью, т.е. быстродействием. Удобная мера эффективности получается при подсчете числа необходимых сравнений ключей С и пересылок элементов М. Эти параметры зависят от числа сортируемых элементов п. Хорошие алгоритмы сортировки требуют порядка nlogn сравнений.

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

Методы сортировки массивов можно разбить на три класса [3]:

1) сортировка включениями;

2) сортировка выбором;

3) сортировка обменом.

Сравним эти методы. Используем массив а, описанный следующим образом:

int nambers[n\;.