Алгоритмы сортировки в Delphi

 

Пример:  

60,79, 82, 58, 39, 9, 54, 92, 44, 32

60,79, 82, 58, 39, 9, 54, 92, 44, 32

9,79, 82, 58, 39, 60, 54, 92, 44, 32

9,79, 82, 58, 39, 60, 54, 92, 44, 32

9, 32, 82, 58, 39, 60, 54, 92, 44, 79

9, 32, 44, 58, 39, 60, 54, 92, 82, 79

9, 32, 44, 58, 39, 54, 60, 92, 82, 79

9, 32, 44, 58, 39, 92, 60, 54, 82, 79

9, 32, 44, 58, 39, 54, 60, 79, 82, 92

9, 32, 44, 58, 54, 39, 60, 79, 82, 92

9, 32, 44, 58, 60, 39, 54, 79, 82, 92

9, 32, 44, 58, 54, 39, 60, 79, 82, 92

9, 32, 44, 58, 54, 39, 60, 79, 82, 92

9, 32, 44, 58, 54, 39, 60, 79, 82, 92

9, 32, 39, 58, 54, 44, 60, 79, 82, 92

9, 32, 39, 58, 54, 44, 60, 79, 82, 92

9, 32, 39, 44, 54, 58, 60, 79, 82, 92

9, 32, 39, 44, 58, 54, 60, 79, 82, 92

9, 32, 39, 44, 54, 58, 60, 79, 82, 92

9, 32, 39, 44, 54, 58, 60, 79, 92, 82

9, 32, 39, 44, 54, 58, 60, 79, 82, 92

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

Самая сомнительная черта вышеприведенной программы состоит в том, что она очень мало эффективна на простых подфайлах. Например, если файл уже сортирован, то разделы будут вырожденными, и программа просто вызовет сама себя N раз, каждый раз с меньшим на од ин элемент подфайлом. Это означает, что не только производительность программы упадет примерно до N2/2, но и пространство необходимое для ее работы будет около N (смотри ниже), что неприемлемо. К счастью, есть довольно простые способы сделать так, чтобы т акой "худший" случай не произошел при практическом использовании программы.

Когда в файле  присутствуют одинаковые ключи, то возникает  еще два сомнительных вопроса. Первое, должны ли оба указателя останавливаться  на ключах равных делящему элементу или  останавливать только один из них, а второй будет проходить их все, или оба указа теля должны проходить над ними. На самом деле, этот вопрос детально изучался, и результаты показали, что самое лучшее - это останавливать оба указателя. Это позволяет удерживать более или менее сбалансированные разделы в присутствии многих одинаковых ключ ей. На самом деле, эта программа может быть слегка улучшена терминированием сканирования j<i, и использованием после этого quicksort(l, j) для первого рекурсивного вызова.

Характеристики  Производительности Быстрой Сортировки

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

CN = 2CN/2+N - наилучший  случай.

(2CN/2 покрывает  расходы по сортировке двух  полученных подфайлов; N - это стоимость  обработки каждого элемента, используя  один или другой указатель.) Нам  известно также, что примерное  значение этого выражения равно  CN = N lg N.

Хотя мы встречаемся  с подобной ситуацией не так часто, но в среднем время работы программы  будет соответствовать этой формуле. Если принять во внимание вероятные  позиции каждого раздела, то это  сделает вычисления более сложными, но конечный результат буде т аналогичным.

Свойство 1 Быстрая  сортировка в среднем использует 2N ln N сравнений.

Методы  улучшения быстрой  сортировки.

1. Небольшие  Подфайлы.

Первое улучшение  в алгоритме быстрой сортировки возникает из наблюдения, что программа  гарантировано вызывает себя для огромного количества небольших подфайлов, поэтому следует использовать самый лучший метод сортировки когда мы встречаем небольшой подфай л. Очевидный способ добиться этого, это изменить проверку в начале рекурсивной функции из "if r>l then" на вызов сортировки вставкой (соответственно измененной для восприятия границ сортируемого подфайла): "if r-l<=M then insertion(l, r)." Значение для M не обязано быть "самым-самым" лучшим: алгоритм работает примерно одинаково для M от 5 до 25. Время работы программы при этом снижается примерно на 20% для большинства программ.

При небольших  подфайлах (5- 25 элементов) быстрая сортировка очень много раз вызывает сама себя (в наше примере для 10 элементов  она вызвала сама себя 15 раз), поэтому  следует применять не быструю сортировку, а сортировку вставкой.

 

2. Деление по Медиане из Трех

Второе улучшение  в алгоритме быстрой сортировки состоит в попытке использования  лучшего делящего элемента. У нас  есть несколько возможностей. Наиболее безопасная из них будет попытка  избежать худшего случая посредством  выбора произвольного элемента массив а в качестве делящего элемента. Тогда вероятность худшего случая становится пренебрежимо мала. Это простой пример "вероятностного" алгоритма, который почти всегда работает вне зависимости от входных данных. Произвольность может быть хорошим инструментом п ри разработке алгоритмов, особенно если возможны подозрительные входные данные.

Более полезное улучшение состоит в том, чтобы  взять из файла три элемента, и  затем использовать среднее из них  в качестве делящего элемента. Если элементы взяты из начала, середины, и конца файла, то можно избежать использования сторожевых элементов: сорт ируем взятые три элемента, затем обмениваем центральный элемент с a[r-1], и затем используем алгоритм деления на массиве a[l+1..r-2]. Это улучшение называется делением по медиане из трех.

Метод деления  по медиане из трех полезен по трем причинам. Во-первых, он делает вероятность  худшего случая гораздо более  низкой. Чтобы этот алгоритм использовал  время пропорциональной N2, два из трех взятых элементов должны быть либо самыми меньшими, либо самыми большими, и это должно повторяться из раздела в раздел. Во-вторых, этот метод уничтожает необходимость в сторожевых элементах, поскольку эту роль играет один из трех взятых нами перед делением элементов. В третьих, он на самом деле снижает время р аботы алгоритма приблизительно на 5%.

 

3. Нерекурсивная реализация.

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

Комбинация нерекурсивной  реализации деления по медиане из трех с отсечением на небольшие файлы  может улучшить время работы алгоритма  от 25% до 30%.

Итак, на сегодняшнем  занятии мы рассмотрели алгоритм быстрой сортировки.

Слияние

На сегодняшнем  занятии мы начнем рассмотрении темы внешняя сортировка.

Внешняя сортировка сортирует файлы, которые не помещаются целиком в оперативную память.

Внешняя сортировка сильно отличается от внутренней. Дело в том, что доступ к файлу является последовательным, а не параллельным как это было в массиве. И поэтому считывать файл можно только блоками и этот блок отсортировать в памяти и снова записать в фай л.

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

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

Слияние - намного  более простая операция, чем сортировка.

Мы рассмотрим 2 алгоритма слияния:

Прямое слияние. Алгоритм Боуза - Нельсона Естественное (Неймановское) слияние.  
Прямое слияние. Алгоритм Боуза - Нельсона Последовательность а разбивается на две половины b и с.

Последовательности b и с сливаются при помощи объединения  отдельных элементов в упорядоченные  пары.

Полученной последовательности присваивается имя а, после чего повторяются шаги 1 и 2; при этом упорядоченные  пары сливаются в упорядоченные четверки.

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

Пример 

Исходная последовательность  

А = 44 55 12 42 94 18 06 67 

1 

b = 44 55 12 42

с = 94 18 06 67

а = 44 94' 18 55' 06 12' 42 67 

2 

b = 44 94' 18 55'

с =06 12' 42 67

а = 06 12 44 94' 18 42 55 67' 

3 

b = 06 12 44 94'

с = 18 42 55 67'

а = 06 12 18 42 44 55 67 94

Операция, которая  однократно обрабатывает всё множество данных, называется фазой.

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

В нашем примере  сортировка производится за три прохода. Каждый проход состоит из фазы разбиения  и фазы слияния.

Главным минусом  сортировки слиянием является удвоение размера памяти, первоначально занятой  сортируемыми данными. Рассмотрим алгоритм с рекурсивным актом слияния, предложенный Боузом и Нельсоном  и не требующий резерва памяти.

Он основан  на очевидной идее: слить две равные упорядоченные части можно слиянием их начальных половин, слиянием конечных и слиянием 2-й половины 1-го результата с 1-й половиной 2-го результата, например:

Если части  не равны или не делятся точно  пополам, процедуру уточняют надлежащим образом. Аналогично слияние "половинок" можно свести к слиянию "четвертушек", "восьмушек" и т. д.; имеет место рекурсия.