7.2.5.Быстрая сортировка

Алгоритм быстрой сортировки является, по-видимому, самым эффективным алгоритмом сортировки массивов. В этом алгоритме для сортировки элементов массива X[1],X[2],...,X[N] из этих элементов выбирается некоторый элемент, значение которого берется в качестве опорного значения v, относительно которого переупорядочиваются элементы массива. Переупорядочивание заключается в том, чтобы для некоторого индекса j все элементы X[1],...,X[j] имели значение меньше v, а все элементы X[j+1],...,X[N] имели значение больше или равно v. Затем процедура рекурсивно применяется к частям массива, состоящим из элементов X[1],...,X[j] и X[j+1],...,X[N]. Желательно выбрать опорное значение так, чтобы сортируемый массив разбивался на две примерно равные части.

На рис.7.11 показаны шаги выполнения процедуры быстрой сортировки, выполняемые для массива, состоящего из чисел 3,1,4,1,5,9,2,6,5,3. На каждом шаге значение v выбирается как наибольшее значение из двух самых левых различных элементов части текущей части массива. Сортировка завершается, когда части массива, на которые разбивается исходный массив в процессе рекурсивных вызовов процедуры, будут содержать одинаковые элементы.

Алгоритм быстрой сортировки представлен блок-схемами на рис.7.12.

Время выполнения алгоритма быстрой сортировки в худшем случае равно O(n²). Однако, в среднем время выполнения алгоритма быстрой сортировки равно O(nlog₂n). Практика применения алгоритма быстрой сортировки показывает, что он более эффективен чем алгоритм пирамидальной сортировки, у которого время выполнения в худшем случае равно O(nlog₂n).

7.2.6.Сортировка слиянием

Если данные хранятся в файле и объем данных превышает размер оперативной памяти, то для сортировки таких данных можно воспользоваться сортировкой слиянием. Основная идея сортировки слиянием проиллюстрирована на рис.7.14. В данном случае исходный файл F0 разбивается на две части, которые могут быть помещены в оперативную память (в общем случае число таких частей может быть больше двух). Далее обе части сортируются любым из методов внутренней сортировки и записываются на диск. В данном примере запись осуществляется в рабочие файлы F1 и F2. Однако можно было осуществить запись отсортированных частей файла на место исходного файла. Далее отсортированные части файла сливаются в одну.

Слияние двух отсортированных файлов в один осуществляется следующим образом:

1. В качестве текущих элементов первого и второго файла принять первые элементы в этих файлах. Результирующий файл пуст.

2. Если значение текущего элемента первого файла больше значения текущего элемента второго файла, то в результирующий файл записать значение текущего элемента второго файла и в качестве текущего элемента второго файла принять следующий элемент в этом файле

3. Если значение текущего элемента первого файла меньше или равно значению текущего элемента второго файла, то в результирующий файл записать значение текущего элемента первого файла и в качестве текущего элемента первого файла принять следующий элемент в этом файле

4. Если достигнут конец первого файла, то все элементы второго файла переписать в результирующий файл.

5. Если достигнут конец второго файла, то все элементы первого файла переписать в результирующий файл.

Этапы слияния исходных файлов F1 и F2 в результирующий файл F3 (см. рис.7.14) представлены в табл.7.1.

Таблица 7.1