Сортировка представляет собой расстановку объектов в определенном порядке, например, по убыванию или по возрастанию. Вообще упорядочивание элементов – самая распространенная манипуляция с данными, облегчающая в дальнейшем поиск нужной информации. Это во многом относится к различным системам управления базами данных. Алгоритмы сортировки в настоящий момент времени существуют в большом количестве, хотя имеют сходные черты (этапы): сравнение и перестановку элементов попарно до тех пор, пока последовательность не станет упорядоченной.
Алгоритмы сортировки можно классифицировать на внутренние и внешние. Первые характеризуются тем, что все сортируемые элементы размещаются в оперативной памяти и возможно получить произвольный доступ к любому из них. Вторые могут работать с данными, размещенными во внешней памяти (в файлах). Доступ к таким элементам может быть реализован последовательно.
Удобнее сортировать элементы, когда они находятся в структуре одномерного массива. У каждого такого элемента есть порядковый номер, и обращение к элементу массива происходит по индексу. Алгоритмы сортировки в этом случае получаются наиболее простыми и понятными для использования.
Рассмотрим внутренний алгоритм сортировки по убыванию методом пузырька и его усовершенствованную версию, отличающуюся затрачиваемым временем на сортировку. Сортировка методом пузырька на самом деле имеет множество названий. Его называют также методом линейной сортировки или методом обменной сортировки выбором. Но, впрочем, дело не в названии. Почему пузырек? Оказавшись в воде, пузырек воздуха всплывет, так как он легче. Так, например, при сортировке по возрастанию наверху окажется наименьший из элементов.
Рассмотрим первый вариант алгоритма сортировки массива методом пузырька. Словесный алгоритм сортировки массива, имеющего идентификатор mas и состоящего из N элементов, выглядит следующим образом:
1. Поместить на место первого элемента (mas[1]) наибольший элемент массива. Для этого будем сравнивать его по очереди со всеми оставшимися элементами (mas[2], mas[3] … mas[N]). Если окажется, что какой-либо из оставшихся элементов больше mas[1], то требуется поменять их местами (через дополнительную переменную buf).
2. Исключив из рассмотрения элемент mas[1], повторить пункт 1 для элемента mas[2].
3. Эти действия повторять для всех элементо, кроме последнего.
Реализация алгоритма сортировки пузырьком на языке программирования Паскаль:
Про второй вариант (усовершенствованный метод пузырька) можно сказать, что это алгоритм быстрой сортировки. Так, если попытаться его использовать для сортировки уже отсортированного массива, алгоритм закончит свою работу уже после первого прохода по элементам массива. А значит, что не будем тратить вычислительные ресурсы системы и время на бессмысленное сравнение элементов.
Приведем реализацию этого алгоритма сортировки для языка программирования Паскаль:
Итак, алгоритмы сортировки являются средством упорядочивания последовательностей данных. При выборе определенного алгоритма следует учитывать затраты с точки зрения времени и ресурсов системы.
