Содержание
- 2. Постановка задачи сортировки Простые алгоритмы сортировки Быстрые алгоритмы сортировки Содержание
- 3. 2. Постановка задачи сортировки
- 4. Эта Тема посвящена сугубо алгоритмической проблеме упорядочения данных. Необходимость отсортировать какие-либо величины возникает в программировании очень
- 5. Однако верно и обратное. Сколь бы хорошим и эффективным ни был выбранный вами алгоритм, но если
- 6. Методы упорядочения подразделяются на внутренние (обрабатывающие массивы) и внешние (занимающиеся только файлами). В этой Теме рассматриваются
- 7. Под сортировкой последовательности понимают процесс перестановки элементов последовательности в определенном порядке: по возрастанию, убыванию, последней цифре,
- 8. Основными требованиями к программе сортировки массива являются эффективность по времени и экономное использование памяти. Это означает,
- 9. К простым внутренним сортировкам относят методы, сложность которых пропорциональна квадрату размерности входных данных. Иными словами, при
- 10. Сортировка Алгоритмы: простые и понятные, но неэффективные для больших массивов метод пузырька метод выбора сложные, но
- 11. Количество действий, необходимых для упорядочения некоторой последовательности данных, конечно же, зависит не только от длины этой
- 12. Как правило, сложность алгоритмов подсчитывают раздельно по количеству сравнений и по количеству перемещений данных в памяти
- 13. 3. Простые алгоритмы сортировки
- 14. Метод пузырька Идея – пузырек воздуха в стакане воды поднимается со дна вверх. Для массивов –
- 15. © С.В.Кухта, 2009 Программа 1-ый проход: сравниваются пары A[N-1] и A[N], A[N-2] и A[N-1] … A[1]
- 16. © С.В.Кухта, 2009 Программа program qq; const N = 10; var A: array[1..N] of integer; i,
- 17. Внешний цикл выполнился n–1 раз. Внутренний цикл выполняется j раз (K = n–2, n–1, ..., 1).
- 18. Метод пузырька с флажком Идея – если при выполнении метода пузырька не было обменов, массив уже
- 19. Метод пузырька с флажком i := 0; repeat i := i + 1; flag := False;
- 20. Метод выбора Идея: найти минимальный элемент и поставить на первое место (поменять местами с A[1]) из
- 21. Метод выбора for i := 1 to N-1 do begin nMin = i ; for j:=
- 22. Самый простой способ сортировки, который приходит в голову, - это упорядочение данных по мере их поступления.
- 23. Алгоритм ПрВст Первый элемент записать "не раздумывая". Пока не закончится последовательность вводимых данных, для каждого нового
- 24. Фрагмент программы: Сортировка простыми вставками for i:= 2 to N do if a[i-1]>a[i] then begin {*}
- 25. Чтобы сократить количество сравнений, производимых нашей программой, дополним сортируемый массив нулевой компонентой (это следует сделать в
- 26. Фрагмент программы: for i:= 2 to N do if a[i-1]>a[i] then begin a[0]:= a[i]; {*} j:=
- 27. Эффективность алгоритма. Понятно, что для этой сортировки наилучшим будет случай, когда на вход подается уже упорядоченная
- 28. Пример сортировки. Предположим, что нужно отсортировать следующий набор чисел: 5 3 4 3 6 2 1
- 29. Сортировку простыми вставками можно немного улучшить: поиск "подходящего места" в упорядоченной последовательности можно вести более экономичным
- 30. Сортировка бинарными вставками Пусть, к примеру, нужно найти место для элемента 7 в таком массиве: [2
- 31. Давайте договоримся, что новой "серединой" последовательности всегда будет становиться левый центральный элемент. Это соответствует вычислению номера
- 32. Если бы в той же самой последовательности нужно было найти позицию не для семерки, а для
- 33. Из приведенных примеров уже видно, что поиск ведется до тех пор, пока левая граница не окажется
- 34. Будет ли такой алгоритм универсальным? Давайте проверим, что же произойдет, если мы станем искать позицию для
- 35. Добавим число 21 в последовательность. 2 4 6 8 10 [12 14 16 18] 2 4
- 36. Фрагмент программы: for i:= 2 to n do if a[i-1]>a[i] then begin x:= a[i]; left:= 1;
- 37. Эффективность алгоритма. Теперь на каждом шаге выполняется не N, а log2N проверок, что уже значительно лучше
- 38. 4. Быстрые алгоритмы сортировки
- 39. В отличие от простых сортировок, имеющих сложность O(N2), к улучшенным сортировкам относятся алгоритмы с общей сложностью
- 40. Эта сортировка базируется на уже известном нам алгоритме простых вставок. Смысл ее состоит в раздельной сортировке
- 41. Сортировку Шелла придумал Дональд Л. Шелл. Ее необычность состоит в том, что она рассматривает весь список
- 42. Сортирует элементы массива А[1..n] следующим образом: на первом шаге упорядочиваются элементы n/2 пар (A[i], А[n/2 +
- 43. На рис. а изображены восемь подсписков, по два элемента в каждом, в которых первый подсписок содержит
- 44. На рис. б мы видим уже четыре подсписка по четыре элемента в каждом: первый подсписок на
- 45. На рис. в показаны два подсписка, состоящие из элементов с нечетными и четными номерами соответственно. Сортировка
- 46. На рис. г мы вновь возвращаемся к одному списку. Сортировка Шелла
- 47. Фрагмент программы: incr:= n div 2; while incr>0 do begin for i:=incr+1 to n do begin
- 48. Полный анализ сортировки Шелла чрезвычайно сложен, и мы не собираемся на нем останавливаться. Было доказано, что
- 49. Попытаемся теперь усовершенствовать другой рассмотренный выше простой алгоритм: сортировку простым выбором. Р.Флойд предложил перестроить линейный массив
- 50. Для начала необходимо перестроить исходный массив так, чтобы он превратился в пирамиду, где каждый элемент "опирается"
- 51. Итак, будем рассматривать наш линейный массив как пирамидальную структуру: Видно, что любой элемент a[i] (1 И
- 52. Начнем процесс просеивания "снизу". Половина элементов (с ((N div 2)+1)-го по N-й) являются основанием пирамиды, их
- 53. Фрагмент программы алгоритма просеивания: for i:= (N div 2)downto 1 do begin j:=i; while j k:=2*j;
- 54. Пример результата просеивания Возьмем массив [1,7,5,4,9,8,12,11,2,10,3,6] (N = 12). Его исходное состояние таково (серым цветом выделено
- 55. перестановка не требуется Пирамидальная сортировка: просеивание
- 56. перестановка элементов 9 и 10 Пирамидальная сортировка: просеивание
- 57. перестановка элементов 4 и 11 Пирамидальная сортировка: просеивание
- 58. перестановка элементов 5 и 12 элемент 5 сыновей не имеет, проверка вниз не производится Пирамидальная сортировка:
- 59. перестановка элементов 7 и 11 производится проверка тройки элементов 7, 4 и 2; перестановка не требуется
- 60. производится проверка тройки элементов 1, 8 и 5; требуется перестановка 1 и 8 производится проверка пары
- 61. Итак, мы превратили исходный массив в пирамиду: в любой тройке a[i], a[2*i] и a[2*i+1] максимум находится
- 62. Для того чтобы отсортировать массив методом Пирамиды, необходимо выполнить такую последовательность действий: 0-й шаг: Превратить исходный
- 63. © С.В.Кухта, 2009 Часть программы, реализующая нулевой шаг алгоритма, приведена в пункте "Просеивание", поэтому здесь приведена
- 64. Продолжим сортировку массива, для которого мы уже построили пирамиду: [12, 11, 8, 7, 10, 6, 5,
- 65. 1) Меняем местами a[1] и a[12]: [1, 11, 8, 7, 10, 6, 5, 4, 2, 9,
- 66. 5) Меняем местами a[1] и a[10]: [1, 9, 8, 7, 3, 6, 5, 4, 2], 10,
- 67. 5) Меняем местами a[1] и a[10]: [1, 9, 8, 7, 3, 6, 5, 4, 2], 10,
- 68. 9) Меняем местами a[1] и a[8]: [1, 7, 6, 4, 3, 2, 5], 8, 9, 10,
- 69. 13) Меняем местами a[1] и a[6]: [2, 4, 5, 1, 3], 6, 7, 8, 9, 10,
- 70. 19) Меняем местами a[1] и a[3]: [2, 1], 3, 4, 5, 6, 7, 8, 9, 10,
- 71. Эффективность алгоритма Пирамидальная сортировка хорошо работает с большими массивами, однако на маленьких примерах (N В среднем
- 72. Идея метода 1. Делим массив элементов на две части: если сортируемый массив состоит из n элементов,
- 73. Сортировка слиянием Procedure SortMerge ( var A: Massiv; first, last: integer); Var c: integer; begin if
- 74. Сортировка слиянием Procedure Merge(var A: Massiv; first, c, last: integer); Var B: Massiv; i, j, k:
- 75. Сортировка слиянием while (i B[k]:=A[i]; k:=k+1; i:=i+1 end; while (j B[k]:=A[j]; k:=k+1; j:=j+1 end; k:=0; for
- 76. Пример Сортировка слиянием
- 77. «Быстрая сортировка» (Quick Sort) Идея – более эффективно переставлять элементы, расположенные дальше друг от друга. N
- 78. «Быстрая сортировка» (Quick Sort) Медиана – такое значение X, что слева и справа от него в
- 79. «Быстрая сортировка» (Quick Sort)
- 80. «Быстрая сортировка» (Quick Sort) procedure QuickSort ( var A: Massiv; first, last: integer); var L, R,
- 81. Схема выполнения алгоритма «быстрой сортировки»: «Быстрая сортировка» (Quick Sort)
- 82. «Быстрая сортировка» (Quick Sort) program qq; const N = 10; Type massiv=array[1..N] of integer; var A:massiv;
- 83. © С.В.Кухта, 2009 Количество перестановок (случайные данные)
- 85. Скачать презентацию