Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
СОРТИРОВКА
Содержание
- 1. СОРТИРОВКА
- 2. В общем случае сортировку следует понимать как
- 3. Сортировка является одной из фундаментальных алгоритмических задач
- 4. Алгоритм сортировкиАлгоритмом сортировки называется алгоритм для упорядочения
- 5. Практически каждый алгоритм сортировки можно разбить на
- 6. Универсального, наилучшего алгоритма сортировки на данный момент
- 7. Параметры оценки алгоритмовВремя сортировки – основной параметр,
- 8. Параметры оценки алгоритмовУстойчивость – это параметр, который
- 9. Классификация алгоритмов сортировокВсе разнообразие и многообразие алгоритмов
- 10. Классификация алгоритмов сортировки по сфере примененияВнутренняя сортировка
- 11. Внутренняя сортировкаЭто алгоритм сортировки, который в процессе
- 12. Внешняя сортировкаЭто алгоритм сортировки, который при проведении
- 13. Внутренняя сортировка является базовой для любого алгоритма
- 14. Перечислим наиболее известные алгоритмы внутренней сортировки:1. Сортировка
- 15. Введём некоторые понятия и обозначенияЕсли у нас
- 16. Обычно упорядочивающая функция не выполняется по какому-либо
- 17. В одних случаях необходимо размещать записи в
- 18. Сортировка таблицы адресов
- 19. Другие схемы сортировки используют вспомогательное поле связи,
- 20. После сортировки таблицы адресов или сортировки списка
- 21. Сортировка подсчетом Идея алгоритма состоит в том,
- 22. Алгоритм сортировки подсчетом 1. Начало алгоритма. 2.
- 23. Пример работы алгоритма
- 24. Для работы нужен дополнительный массив размером N
- 25. Временная сложность этого алгоритма приведена в [Кнут].O
- 26. Сортировки вставками ( insert sort)
- 27. Сортировки вставками ( insert sort)
- 28. Пример сортировки простыми вставками
- 29. Алгоритм сортировки вставками1. Начало алгоритма. 2. Цикл
- 30. Бинарные вставкиКогда при сортировке простыми вставками обрабатывается
- 31. Этот метод называется бинарными вставками, он был
- 32. Двухпутевые вставкиРассматриваются различные усовершенствования, которые позволяет сократить
- 33. Анализ алгоритмаO(n2) сравнений и перестановок O(1) дополнительной памятиУстойчивый Естественность поведения O(n)
- 34. Сортировка Шелла Сортировка с убывающим
- 35. Общая схема метода1. Происходит упорядочивание элементов n/2
- 36. В результате проведенного в [Кнуте] анализа предлагается
- 37. В настоящее время неизвестна последовательность hi,hi-1,hi-2,...,h1,, оптимальность
- 38. Пример сортировки Шелла
- 39. Пример сортировки Шелла
- 40. 1. Начало алгоритма 2. Определяем Т. H[0]=1.
- 41. Анализ алгоритмаO(t)~N1,2 ÷ N1,3 зависит от выбора
- 42. Shell-sort with Hungarian (Székely) folk dance
- 43. Bubble-sort with Hungarian ("Csángó") folk dance
- 44. Quick-sort with Hungarian (Küküllőmenti legényes) folk dance
- 45. Обменные сортировки1. Обменная сортировка с выбором и
- 46. Обменная сортировкаОбменная сортировка основана на последовательном сравнении
- 47. Пузырьковая сортировка Bubble-sortЕсли процесс сравнения пар начинается
- 48. Шейкерная сортировкаУсовершенствованием этих алгоритмов является алгоритм «шейкерной»
- 49. Быстрая сортировка Хоара QuicksortБыстрая сортировка – это
- 50. Опорным (ведущим) элементом называется некоторый элемент массива,
- 51. Интересночто Хоар разработал этот метод применительно к
- 52. Сортировка ХоараВ алгоритме используется подход, в котором
- 53. Алгоритм быстрой сортировкиПусть дан массив x[n] размерности
- 54. Рекурсивный алгоритм быстрой сортировки1. Начало алгоритма. 2.
- 55. Слайд 55
- 56. Сортировка ХоараВ алгоритме используется подход, в котором
- 57. Пример работы
- 58. Анализ алгоритмаO(n2)O(n·lg(n)) O(lg(n)) дополнительной памятиНеустойчивый Неестественность поведения
- 59. Quick-sort with Hungarian (Küküllőmenti legényes) folk dance
- 60. Сортировка выбором При сортировке простым выбором
- 61. Сложность такого алгоритма O(n2) (в среднем, немного
- 62. Алгоритм1. Начало алгоритма. 2. Цикл 1 i=0,
- 63. Метод квадратичного выбораПростой выбор можно усовершенствовать. Э.Х.Фрэнд
- 64. Пример
- 65. Дальнейшее совершенствованиеДалее тот же автор предложил идею
- 66. Пирамидальная сортировка Heap Sort Дж. Уильямс
- 67. Потомки K –го элемента вычисляется как (2*К)
- 68. Слайд 68
- 69. Алгоритм пирамидальной сортировки (heapsort) 1. Начало алгоритма.
- 70. Алгоритм процедуры Form 1. Начало алгоритма процедуры 2. i=L; j=2*i+1; 3. Цикл 1: пока j
- 71. Слайд 71
- 72. Слайд 72
- 73. Слайд 73
- 74. Слайд 74
- 75. Анализ алгоритмаO(n·lg(n)) Не использует дополнительной памятиНеустойчивый Неестественность
- 76. Скачать презентанцию
В общем случае сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определённом порядке. Цель сортировки – облегчить последующий поиск элементов в таком отсортированном (упорядоченном) множестве.
Слайды и текст этой презентации
Слайд 2В общем случае сортировку следует понимать как процесс перегруппировки заданного
множества объектов в некотором определённом порядке.
последующий поиск элементов в таком отсортированном (упорядоченном) множестве.
Слайд 3Сортировка является одной из фундаментальных алгоритмических задач программирования. Сортировка применяется
во всех без исключения областях программирования, будь то базы данных
или математические программы. Алгоритмы сортировки имеют большое практическое применение.Решению проблем, связанных с сортировкой, посвящено множество научных исследований, разработано множество алгоритмов.
Слайд 4Алгоритм сортировки
Алгоритмом сортировки называется алгоритм для упорядочения некоторого множества элементов.
Обычно под алгоритмом сортировки подразумевают алгоритм упорядочивания множества элементов по
возрастанию или убыванию.Выбор алгоритма зависит от структуры обрабатываемых данных.
Слайд 5Практически каждый алгоритм сортировки можно разбить на 3 части:
сравнение, определяющее
упорядоченность пары элементов;
перестановку, меняющую местами пару элементов;
собственно сортирующий алгоритм, который
осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены.
Слайд 6Универсального, наилучшего алгоритма сортировки на данный момент не существует.
Однако,
имея приблизительные характеристики входных данных, можно подобрать метод, работающий оптимальным
образом.Для этого необходимо знать параметры, по которым будет производиться оценка алгоритмов.
Слайд 7Параметры оценки алгоритмов
Время сортировки – основной параметр, характеризующий быстродействие алгоритма.
Память
– один из параметров, который характеризуется тем, что ряд алгоритмов
сортировки требуют выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться память, которую занимает исходный массив данных и независящие от входной последовательности затраты, например, на хранение кода программы.
Слайд 8Параметры оценки алгоритмов
Устойчивость – это параметр, который отвечает за то,
что сортировка не меняет взаимного расположения равных элементов.
Естественность поведения –
параметр, которой указывает на эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Алгоритм ведет себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
Слайд 9Классификация алгоритмов сортировок
Все разнообразие и многообразие алгоритмов сортировок можно классифицировать
по различным признакам:
по устойчивости,
по поведению,
по использованию операций сравнения,
по
потребности в дополнительной памяти,по потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, и другие.
Слайд 10Классификация алгоритмов сортировки по сфере применения
Внутренняя сортировка или сортировка массивов
Внешняя сортировка или сортировка последовательностей (файлов)
Классификация алгоритмов сортировки по книге
«Искусство программирования для ЭВМ. Т.3. Сортировка и поиск», автор Д.Кнут 
Слайд 11Внутренняя сортировка
Это алгоритм сортировки, который в процессе упорядочивания данных использует
только оперативную память компьютера. То есть оперативной памяти достаточно для
помещения в нее сортируемого массива данных с произвольным доступом к любой ячейке и собственно для выполнения алгоритма.Внутренняя сортировка применяется во всех случаях, за исключением однопроходного считывания данных и однопроходной записи отсортированных данных.
В зависимости от конкретного алгоритма и его реализации данные могут сортироваться в той же области памяти, либо использовать дополнительную оперативную память.
Слайд 12Внешняя сортировка
Это алгоритм сортировки, который при проведении упорядочивания данных использует
внешнюю память, как правило, жесткие диски.
Внешняя сортировка разработана для
обработки больших списков данных, которые не помещаются в оперативную память. Обращение к различным носителям накладывает некоторые дополнительные ограничения на данный алгоритм: доступ к носителю осуществляется последовательным образом, то есть в каждый момент времени можно считать или записать только элемент, следующий за текущим.
Слайд 13Внутренняя сортировка является базовой для любого алгоритма внешней сортировки –
отдельные части массива данных сортируются в оперативной памяти и с
помощью специального алгоритма сцепляются в один массив, упорядоченный по ключу.Следует отметить, что внутренняя сортировка значительно эффективней внешней, так как на обращение к оперативной памяти затрачивается намного меньше времени, чем к носителям.
Слайд 14Перечислим наиболее известные алгоритмы внутренней сортировки:
1. Сортировка вставками (или прямого
включения). 2. Обменная сортировка. 3. Сортировка посредством выбора. 4. Сортировка
подсчётом. 5. Сортировка слиянием (на линейных списках). 6. Распределяющая сортировка.
Слайд 15Введём некоторые понятия и обозначения
Если у нас есть элементы a1,
a2, …, an, то сортировка есть перестановка этих элементов ak1,
ak2,…, akn,где при некоторой упорядочивающей функции f выполняются отношения
f (ak1) ≤ f (ak2) ≤… ≤ f(akn).
Слайд 16Обычно упорядочивающая функция не выполняется по какому-либо правилу, а хранится
как явная компонента (поле) каждого элемента.
Её значение называется ключом (key)
элемента. Поэтому для представления элементов хорошо подходят такие структуры данных как записи struct Item { int Key; /*… другие поля или компоненты*/ };
Слайд 17В одних случаях необходимо размещать записи в памяти так, чтобы
их ключи были упорядочены; в других случаях можно обойтись вспомогательной
таблицей некоторого вида, которая определяет перестановку. Если записи и/или ключи занимают несколько ячеек (слов) памяти, то часто лучше составить новую таблицу адресов (ссылок), которые указывают на записи, и работать с этими адресами, не перемещая громоздкие записи.Такой метод называется сортировкой таблицы адресов (индексов)
Если ключи короткие, а сопутствующая информация в записях велика, то для повышения скорости ключи можно вынести в таблицу адресов. Это называется сортировкой ключей.
Слайд 19Другие схемы сортировки используют вспомогательное поле связи, которое включается в
каждую запись. Связи обрабатываются таким образом, что в результате все
записи оказываются связанными в линейный список, в котором каждая связь указывает на следующую по порядку запись. Это называют сортировкой списка
Слайд 20После сортировки таблицы адресов или сортировки списка можно либо расположить
сами записи в заданном порядке (в данном примере неубывающем). Для
этого имеется несколько способов:Используя одну дополнительную ячейку памяти.
Используя дополнительную память размером равную исходному массиву.
Слайд 21Сортировка подсчетом
Идея алгоритма состоит в том, чтобы сравнить попарно
все ключи и подсчитать, сколько из них больше (или меньше)
каждого отдельного ключа.Далее, при увеличении каждого из полученных значений на 1, мы получим данные о том, где должны располагаться упорядоченные элементы массива.
Знак больше соответствует сортировке по возрастанию, а меньше – по убыванию. N – число записей (ключей-элементов).
N(N-1)/2 – число сравнений.
Слайд 22Алгоритм сортировки подсчетом
1. Начало алгоритма.
2. В массив счетчиков Count
записать 1. 3. Цикл 1 i=0, N-2. Выполнять пункт 4
. 4. Цикл 2 j=i+1, N-1. Выполнять пункт 5. 5. Если K[i]>K[j], тогда Count[i]+=1, иначе Count[j]+=1. 6. Цикл i=0,N-1 выполнитьnewK [Count[i]]= K[i]. 7. Конец алгоритма.
По окончании счетчики содержат номера позиций, на которых должны стоять элементы в упорядоченном массиве.
Слайд 24Для работы нужен дополнительный массив размером N - счётчик Count
[N-1]. В этом алгоритме записи не перемещаются. Count [i] указывает
на место, куда нужно переслать запись.Перемещение записи производится с использованием дополнительной памяти:
Цикл i =0,N-1 выполнять newK[Count[i]]= K[i], K- исходный массив
![Для работы нужен дополнительный массив размером N - счётчик Count [N-1]. В этом алгоритме записи не перемещаются.](/img/thumbs/c54854f7684188a8cf8d415315c5260b-800x.jpg "СОРТИРОВКА Для работы нужен дополнительный массив размером N - счётчик Count [N-1].")
Слайд 25Временная сложность этого алгоритма приведена в [Кнут].
O (t) = 3N2
+ 10 N до 5,5N2 +7,5N.
O (t) = C
N2Эта сортировка впервые упоминается в работе Фрэнда(E.H.Friend) в 1956 году.
![Временная сложность этого алгоритма приведена в [Кнут].O (t) = 3N2 + 10 N до 5,5N2 +7,5N. O](/img/thumbs/56e8444c2a1bdd5b3f6c917179b926d9-800x.jpg "СОРТИРОВКА Временная сложность этого алгоритма приведена в [Кнут].O (t) = 3N2 +")
Слайд 26Сортировки вставками
( insert sort)
Простые вставки
Пусть 1 < j
≤ N и записи R1…Rj-1 уже размещены так, что их
ключи упорядочены: К1 ≤ К2 ≤…≤ Кj-1.Будем сравнивать по очереди: Кj с Кj-1,Кj-2,… до тех пор пока не обнаружим, что запись Rj следует вставить между Ri и Ri+1:
тогда подвинем записи Ri+1,…,Rj-1 на одно место и поместим новую запись в позицию i+1.
Слайд 29Алгоритм сортировки вставками
1. Начало алгоритма.
2. Цикл j = 1, N-1.
Выполнить пункты (3-6) 3. Установить значения: i = j-1, key =K[j]. 4.
Пока (i>0) && (key
Слайд 30Бинарные вставки
Когда при сортировке простыми вставками обрабатывается j-я запись, её
ключ сравнивается в среднем примерно с j/2 ранее упорядоченными ключами,
поэтому общее число сравнений равно (1+2+…+N)/2 ≈ N²/4.Если для поиска места вставки в уже упорядоченную последовательность воспользоваться бинарным поиском, то можно значительно сократить число сравнений.
Слайд 31Этот метод называется бинарными вставками, он был упомянут в 1946
году Джоном Мочли в первой публикации по машинной сортировке.
Но
этот метод снижает только время поиска, но для вставки Rj придётся передвигать в среднем примерно j/2 ранее отсортированных записей. 
Слайд 32Двухпутевые вставки
Рассматриваются различные усовершенствования, которые позволяет сократить число необходимых перемещений.
Например: первый элемент помещают в середину области вывода, и место
для последующих элементов освобождается при помощи сдвигов влево и вправо. Это позволяет сэкономить примерно половину времени по сравнению с простыми вставками, но алгоритм становится сложнее. Он называется двухпутевыми вставками.Для алгоритмов сортировки, которые каждый раз перемещают запись только на одну позицию, среднее время примерно N².
Слайд 33Анализ алгоритма
O(n2) сравнений и перестановок
O(1) дополнительной памяти
Устойчивый
Естественность поведения
O(n)
Слайд 34Сортировка Шелла
Сортировка с убывающим шагом
Сортировка Шелла была
названа в честь ее изобретателя – Дональда Шелла, который опубликовал
этот алгоритм в 1959 году.Общая идея сортировки Шелла состоит в сравнении на начальных стадиях сортировки пар значений, расположенных достаточно далеко друг от друга в упорядочиваемом наборе данных. Такая модификация метода сортировки позволяет быстро переставлять далекие неупорядоченные пары значений
Слайд 35Общая схема метода
1. Происходит упорядочивание элементов n/2 пар (xi,xn/2+i) для
1< i < n/2.
2. Упорядочиваются элементы в n/4 группах из
четырех элементов (xi,xn/4+i,xn/2+i,x3n/4+i) для 1< i < n/4.3. Упорядочиваются элементы уже в n/4 группах из восьми элементов и т.д.
На последнем шаге упорядочиваются элементы сразу во всем массиве x1,x2,...,xn.
На каждом шаге для упорядочивания элементов в группах используется метод сортировки вставками
Слайд 36В результате проведенного в [Кнуте] анализа предлагается различные способы задания
числа групп, например:
T = [log2N]-1 или T = [log3N]-1 , где обозначение [k] соответствует наибольшему целому значению меньшему или равному k. Для 1 формулы при N=16 T= 3 . Число записей в каждой из Т групп определяется по формуле: H1 = 1, H-1 = 2*Hs +1. Тогда для T= 3 имеем последовательность:1 3 7 вместо: 1 2 4 8, при T = 4: 1 3 7 15 и т.д. При N=10000 Т = [log210000]-1=12.
![В результате проведенного в [Кнуте] анализа предлагается различные способы задания числа групп, например:](/img/thumbs/00d99e27db1f05aaaa6d6fa119f2cd0f-800x.jpg "СОРТИРОВКА В результате проведенного в [Кнуте] анализа предлагается различные способы задания числа")
Слайд 37В настоящее время неизвестна последовательность hi,hi-1,hi-2,...,h1,, оптимальность которой доказана.
Для
достаточно больших массивов рекомендуемой считается такая последовательность, что hi+1=3hi+1, а
h1=1. Начинается процесс с hm, что hm > [n/9].Иногда значение h вычисляют проще: hi+1=hi/2,h1=1,hm=n/2. Это упрощенное вычисление h и будем использовать в примере .
Слайд 401. Начало алгоритма 2. Определяем Т. H[0]=1. 3. Цикл 1: s=0,T-1. Выполнять
H[s+1]= 2*H[s]+1. 4. Цикл 2: s=T-1,0. Выполнять пункты 5 – 11. 5.
Ht = H[s]. 6. Цикл 3 j=Ht, N-1. Выполнять пункты 7 – 10 . 7. i=j-Ht, key=K[j]. 8. Цикл 4 пока i<0 и key![1. Начало алгоритма 2. Определяем Т. H[0]=1. 3. Цикл 1: s=0,T-1. Выполнять H[s+1]= 2*H[s]+1. 4. Цикл 2:](/img/thumbs/df07c0b9ba73f898811338a8ba45614a-800x.jpg "СОРТИРОВКА 1. Начало алгоритма 2. Определяем Т. H[0]=1. 3. Цикл 1: s=0,T-1.")
Слайд 41Анализ алгоритма
O(t)~N1,2 ÷ N1,3 зависит от выбора
O(n3/2) при t=[log2N]-1
O(1) дополнительной памяти
Неустойчивый
Естественность поведения O(n·lg(n))
![Анализ алгоритмаO(t)~N1,2 ÷ N1,3 зависит от выбора O(n3/2) при t=[log2N]-1 O(1) дополнительной памятиНеустойчивый Естественность поведения O(n·lg(n))](/img/thumbs/131bcea709c1bb2642f0e17877fea3aa-800x.jpg "СОРТИРОВКА Анализ алгоритмаO(t)~N1,2 ÷ N1,3 зависит от выбора O(n3/2) при t=[log2N]-1 O(1)")
Слайд 45Обменные сортировки
1. Обменная сортировка с выбором и её усовершенствование –
метод пузырька, шейкерная сортировка. 2. Обменная сортировка со слиянием (Бэтчера) –
параллельная. 3. Обменная с разделением (“быстрая сортировка” Хоара). 4. Поразрядная обменная сортировка.
Слайд 46Обменная сортировка
Обменная сортировка основана на последовательном сравнении двух соседних элементов
и если они расположены не по порядку, то их обмене
местами.Сравнение пар соседних элементов производится до тех пор, пока имеются перестановки.
В результате одного цикла сравнения пар, начиная с первого элемента, последний элемент встает на свое окончательное место, и в следующем цикле не участвует.
В каждом следующем цикле число просматриваемых пар уменьшается на 1. Такой алгоритм называют алгоритмом простого обмена.
Слайд 47Пузырьковая сортировка
Bubble-sort
Если процесс сравнения пар начинается с конца последовательности, то
такой алгоритм называют пузырьковой сортировкой.
В этом случае на первом
месте оказывается элемент, который в дальнейшем сравнении не участвует. 
Слайд 48Шейкерная сортировка
Усовершенствованием этих алгоритмов является алгоритм «шейкерной» сортировки
Первый цикл сравнения
производится, начиная с начала последовательности, второй цикл, начиная с ее
конца.Третий цикл начинается со второго элемента, а четвертый - с предпоследнего, и так далее, пока есть обмены.
Сложность обменной, в том числе шейкерной сортировки: O(t) ~ cn².
Слайд 49Быстрая сортировка Хоара
Quicksort
Быстрая сортировка – это общее название ряда алгоритмов,
которые отражают различные подходы к получению критичного параметра, влияющего на
производительность метода.Метод основывается на последовательном разделении сортируемого набора данных на блоки меньшего размера таким образом, что между значениями разных блоков обеспечивается отношение упорядоченности (для любой пары блоков все значения одного из этих блоков не превышают значений другого блока).
Слайд 50Опорным (ведущим) элементом называется некоторый элемент массива, который выбирается определенный
образом.
С точки зрения корректности алгоритма выбор опорного элемента безразличен.
С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных ее обычно невозможно получить. Необходимо выбирать постоянно один и тот же элемент (например, средний или последний по положению) или выбирать элемент со случайно выбранным индексом.
Слайд 51Интересно
что Хоар разработал этот метод применительно к машинному переводу: дело
в том, что в то время словарь хранился на магнитной
ленте, и если упорядочить все слова в тексте, их переводы можно получить за один прогон ленты.Алгоритм был придуман Хоаром во время его пребывания в Советском Союзе, где он обучался в Московском университете компьютерному переводу и занимался разработкой русско-английского разговорника (говорят, этот алгоритм был подслушан им у русских студентов).
[ An Interview with C.A.R. Hoare. Communications of the ACM, March 2009 ("premium content"). ]
Слайд 52Сортировка Хоара
В алгоритме используется подход, в котором следующее действие зависит
от результата предыдущего сравнения
Рассмотрим схему сравнений/обменов:
Необходимо установить 2 указателя адресов
i и j. Вначале устанавливаем i=0, j=N-1. Сравниваем K[i] и K[j], если обмен не потребуется, то j=j-1 и повторяем сравнение. После первого обмена увеличиваем i на 1 и далее продолжаем сравнения, увеличивая счетчик i , пока не произойдёт следующий обмен, тогда снова j=j-1 и т.д.
Все эти действия производятся до тех пор, пока i не станет равным j. К тому моменту, когда i == j запись R1 (ключ K1) займет свою окончательную позицию, т. к. слева от него все ключи меньше него, а справа – больше него.
Теперь к каждой из частей, расположенных слева и справа от установленного ключа, необходимо применить тот же подход.
Слайд 53Алгоритм быстрой сортировки
Пусть дан массив x[n] размерности n.
1. Выбирается опорный
элемент массива.
2. Массив разбивается на два – левый и правый
– относительно опорного элемента. Реорганизуем массив таким образом, чтобы все элементы, меньшие опорного элемента, оказались слева от него, а все элементы, большие опорного – справа от него.3. Далее повторяется шаг 2 для каждого из двух вновь образованных массивов. Каждый раз при повторении преобразования очередная часть массива разбивается на два меньших и т. д., пока не получится массив из двух элементов
![Алгоритм быстрой сортировкиПусть дан массив x[n] размерности n.1. Выбирается опорный элемент массива.2. Массив разбивается на два –](/img/thumbs/6aa87093de0a889ba8da509dbf92c7cd-800x.jpg "СОРТИРОВКА Алгоритм быстрой сортировкиПусть дан массив x[n] размерности n.1. Выбирается опорный элемент")
Слайд 54Рекурсивный алгоритм быстрой сортировки
1. Начало алгоритма.
2. L=0; r=N; Начало процедуры
sort(0,N-1); 3. s=(L+r)/2; kl:=K[s]; 4. i=L; j=r; 5. Повторять пункты 6
– 10. 6. Пока выполняется условие K[i]![Рекурсивный алгоритм быстрой сортировки1. Начало алгоритма. 2. L=0; r=N; Начало процедуры sort(0,N-1); 3. s=(L+r)/2; kl:=K[s]; 4.](/img/thumbs/31642b0be56bb23f16fc503efa34b45f-800x.jpg "СОРТИРОВКА Рекурсивный алгоритм быстрой сортировки1. Начало алгоритма. 2. L=0; r=N; Начало процедуры")
Слайд 56Сортировка Хоара
В алгоритме используется подход, в котором следующее действие зависит
от результата предыдущего сравнения
Рассмотрим схему сравнений/обменов:
Необходимо установить 2 указателя адресов
i и j. Вначале устанавливаем i=0, j=N-1. Сравниваем K[i] и K[j], если обмен не потребуется, то j=j-1 и повторяем сравнение. После первого обмена увеличиваем i на 1 и далее продолжаем сравнения, увеличивая счетчик i , пока не произойдёт следующий обмен, тогда снова j=j-1 и т.д.
Все эти действия производятся до тех пор, пока i не станет равным j. К тому моменту, когда i == j запись R1 (ключ K1) займет свою окончательную позицию, т. к. слева от него все ключи меньше него, а справа – больше него.
Теперь к каждой из частей, расположенных слева и справа от установленного ключа, необходимо применить тот же подход.
Слайд 58Анализ алгоритма
O(n2)
O(n·lg(n))
O(lg(n)) дополнительной памяти
Неустойчивый
Неестественность поведения
Слайд 60 Сортировка выбором
При сортировке простым выбором массив условно делится
на две части: упорядоченную и неупорядоченную.
Первоначально упорядоченная часть пуста,
а неупорядоченная часть (остаток) включает все элементы. В остатке ищется минимальный элемент (при сортировке по возрастанию).
Найденный элемент меняется местами с первым элементом из остатка, и упорядоченная часть увеличивается на один элемент, а остаток уменьшается на один элемент.
Слайд 61Сложность такого алгоритма O(n2)
(в среднем, немного медленнее простых вставок).
В общем случае эта сортировка быстрее, чем обменная, т. к.
здесь меньше обменов.
Слайд 62Алгоритм
1. Начало алгоритма.
2. Цикл 1 i=0, N-2 выполнять пункты 3-7.
3.
min=K[i]; imin=i; 4. Цикл j=i+1,N-1 выполнять пункты 5-6. 5. Если K[j]
выполнить пункт 6, иначе продолжить цикл 2. 6. Установить min=K[j]; imin=j; продолжить цикл 2 7. Установить K[imin]=K[i]; K[i]=min; продолжить цикл 1. 8. Конец алгоритма.![Алгоритм1. Начало алгоритма. 2. Цикл 1 i=0, N-2 выполнять пункты 3-7. 3. min=K[i]; imin=i; 4. Цикл j=i+1,N-1](/img/thumbs/3d6be9187fd4f20431f98815fa0afeac-800x.jpg "СОРТИРОВКА Алгоритм1. Начало алгоритма. 2. Цикл 1 i=0, N-2 выполнять пункты 3-7.")
Слайд 63Метод квадратичного выбора
Простой выбор можно усовершенствовать.
Э.Х.Фрэнд (в 1956 году)
впервые был опубликовал метод квадратичного выбора, заключающийся в том, что
весь массив разбивается на √n подмассивов (сложность такого алгоритма O(n√n). Далее определяется минимальный элемент в каждом подмассиве.На рисунке подчеркнуты элементы, которые выбираются на каждом шаге алгоритма. Нужен дополнительный массив для записи результата.
Слайд 65Дальнейшее совершенствование
Далее тот же автор предложил идею кубического выбора, т.
е. разделить массив на 3√N подмассивов.
Далее используя 4√N, 5√N
и т. д. подмассивов, мы придём к тому, что Фрэнд назвал выбором n-й степени, основанной на структуре бинарного дерева и тогда сложность такого алгоритма O(n·lg(n)) и он называется алгоритмом выбора из дерева. 
Слайд 66Пирамидальная сортировка
Heap Sort
Дж. Уильямс в 1964г., используя идею выбора
из дерева, опубликовал алгоритм пирамидальной сортировки.
Массив ключей К1, К2, …,
КN называется «пирамидой», если К[j/2] >=Кj, при 1 ≤ [j/2] < j ≤ N. В пирамиде потомки всегда меньше своих родителей.
В этом случае K1 ≥ K2 , K1 ≥ K3 ,
K2 ≥ K4 , K2 ≥ K5, K3 ≥ K6, K3 ≥ K7, … .
Слайд 67Потомки K –го элемента вычисляется как (2*К) и (2*К+1).
Необходимо,
сначала преобразовать исходный массив К в пирамиду, а затем использовать
бинарное дерево, перемещая на каждом шаге в его вершину максимальный элемент.Бинарное дерево ( адреса элементов в одномерном массиве) будет иметь вид
Слайд 69Алгоритм пирамидальной сортировки (heapsort)
1. Начало алгоритма.
2. r=N-1, L=N/2.
3. Цикл
1 пока L>0 выполнять пункты 4-5. 4. L=L-1; kl=K[L]. 5. Вызов процедуры
Form. 6. Цикл пока r>1 выполнять пункты 7-8. 7. kl=K[r]; K[r]=K[1]; r=r-1. 8. Вызов процедуры Form. 9. K[0]=kl. 10. Конец алгоритма.
Слайд 70Алгоритм процедуры Form
1. Начало алгоритма процедуры
2. i=L;
j=2*i+1; 3. Цикл 1: пока j
&& k[j]
Слайд 75Анализ алгоритма
O(n·lg(n))
Не использует дополнительной памяти
Неустойчивый
Неестественность поведения
(Данная сортировка
на почти отсортированных массивах работает также долго, выигрыш ее получается
только на больших n. )
