Изучение предметной области

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

Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.

Итак, каждый алгоритм сортировки состоит из трех основных частей:

Функция сравнения пары элементов сортируемого массива Процедура перестановки, меняющая местами пару элементов Сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены.

В данной работе будет рассмотрена реализация метода сортировки Хоара.

Практическая реализация алгоритма сортировки данных

Быстрая сортировка (сортировка Хоара)

Шаги алгоритма быстрой сортировки таковы:

• 1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
• 2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы со значением меньшим или равным опорному элементу, оказались слева от него, а все элементы, превышающие по значению опорный — справа от него. Обычный алгоритм операции:
  • — Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.
  • — Вычисляется индекс опорного элемента m.
  • — Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше либо равен опорному.
  • — Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
  • — Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
  • — Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно, изменяется именно индекс опорного элемента и алгоритм продолжает свое выполнение.
• 3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
• 4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.

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