Содержание
- 2. Быстрая обменная сортировка (сортировка Хоара). Быстрая сортировка вставкой (сортировка Шелла). Быстрые сортировки выбором. Сравнительный анализ методов
- 3. 4.10. Быстрая обменная сортировка (сортировка Хоара) Считается самой эффективной из известных внутренних сортировок. Получила название –
- 4. Быстрая обменная сортировка (сортировка Хоара) Идея алгоритма: Из исходного массива выбирается некоторый элемент, который принимается в
- 5. В примере реализации алгоритма создаётся процедура Hoor(left, right:integer) - в Pascal или функция void hoor(int left,right)
- 6. Сортировка Хоара (Pascal) procedure Hoor(left, right:integer); var i,j,x:integer; begin i:=left; j:=right; x:=a[(left+right) div 2]; repeat while
- 7. Сортировка Хоара (C/C++) void hoor(int left, int right) { int i=left; int j=right; int x=a[(left+right)/2]; do
- 8. Среднее время выполнения алгоритма: T(n) = O(n × log n) Если массив почти упорядочен, время работы
- 9. Суть метода медианы случайной выборки: Из массива произвольно выбирается группа элементов (обычно до ста элементов), которые
- 10. Быстрая обменная сортировка (сортировка Хоара) - Пример
- 14. 4.11. Быстрая сортировка вставкой – сортировка Шелла Сортировка Шелла является видом сортировки вставкой с изменяющимся расстоянием
- 15. Идея алгоритма: Исходный массив разбивается на несколько подмассивов. В качестве подмассива выбираются элементы, удалённые на d
- 16. На эффективность сортировки Шелла существенным образом влияет выбор закона изменения расстояния d. Основное требование: расстояния di,
- 17. Быстрая сортировка вставкой – сортировка Шелла - пример Обозначения: A – исходный массив; t – количество
- 18. Сортировка Шелла (Pascal) t:=trunc(log2(n))-1; {количество расстояний} d[1]:=1; for i:=2 to t do d[i]:=2*d[i-1]+1; {формирование последовательности di
- 19. Сортировка Шелла (C++) t=(int)log((double)n)-1; //количество расстояний d[0]=1; for (i=1; i //формирование последовательности di по первому варианту
- 22. Быстрые сортировки выбором На практике используется несколько сортировок выбором. Наиболее известные: «Турнир с выбыванием»; Пирамидальная сортировка.
- 23. 4.12. Сортировка «Турнир с выбыванием» Идея алгоритма: Элементы массива разбиваются на пары. Из каждой пары выбирается
- 24. Алгоритм «Турнир с выбыванием» Сравниваем пары соседних ключей и запоминаем значение меньшего ключа из каждой пары.
- 25. Вносим значение, найденное в п.2 в массив упорядоченных ключей (дополнительный массив). Проходим от корня к листу
- 26. 6. Повторяем пункты 3-5, пока победителем не станет число max = 100. Оценка временной сложности алгоритма:
- 27. Достоинства: Быстрота. Оценки худшего и среднего времени выполнения алгоритма совпадают. Недостатки: Дополнительный расход памяти на хранение
- 28. 4.13. Пирамидальная сортировка Выполняется на базе дерева. Алгоритм состоит из 2-х этапов: Построение пирамиды на месте
- 29. Пирамидальная сортировка Бинарное дерево можно представить в виде одномерного массива, в котором: a[1] – корень дерева;
- 30. Данное дерево будет являться пирамидой, если для любого i-го элемента, имеющего потомков, выполняются неравенства: a[i]>=a[2i] a[i]>=a[2i+1]
- 31. Пусть имеется массив: a1, … , an, причём его часть am, … , an (m=n div
- 32. Процедура добавления элемента в готовую пирамиду (Pascal) procedure Shift(left,right:integer); begin i:=left; j:=2*left; x:=a[left]; {Новый элемент x
- 33. Функция добавления элемента в готовую пирамиду (С++) void shift(int left,right) { int i,j,x; i=left; j=2*left; x=a[left];
- 34. Таким образом, процесс формирования пирамиды из n элементов a1, … , an, описывается следующим образом: Pascal:
- 35. После превращения массива в пирамиду получается частично упорядоченная последовательность элементов. Для достижения полной упорядоченности надо проделать
- 36. Пирамидальная сортировка Pascal: right:=n; while right>1 do begin x:=a[1]; a[1]:=a[right]; a[right]:=x; right:=right-1; Shift(1,right); end; C/C++: right=n;
- 37. Реализация пирамидальной сортировки (Pascal) left:=n div 2; right:=n; {определяем место элемента, у которого нет потомков и
- 38. Реализация пирамидальной сортировки (C/C++) left=n/2; right=n; //определяем место элемента, у которого нет потомков и номер последнего
- 40. Данное дерево не является пирамидой, поэтому его надо изменить. Представим пирамиду, состоящую только из нижнего уровня,
- 41. Шаг 1 Добавляем элемент a[7]=40. У него два потомка a[14]=25 и a[15]=71. Т.к. a[7] Шаг 2
- 43. Шаг 4. Добавляем a[1]=20. Меняем местами a[1] и a[2], a[2] и a[4], a[4] и a[9]. В
- 44. Меняем местами первый и последний элементы. В результате в конце массива максимальный элемент и на следующем
- 45. Полученное дерево – не пирамида. Не на своём месте a[1], его надо «просеять». Для этого меняем
- 47. Сравнительный анализ методов сортировки Сравнение быстродействия различных алгоритмов сортировки можно выполнить по ряду показателей: среднему времени
- 48. Формулы, определяющие количество операций, выполняемых с ключами при использовании простых методов сортировки
- 49. Количество операций сравнения, выполняемых при использовании различных методов сортировки
- 51. Скачать презентацию