Содержание
- 2. План лекции Понятие сортировки Внутренняя и внешняя сортировка Алгоритмы сортировки Простые Улучшенные Анализ числа операций Нижняя
- 3. Задача сортировки Значения элементов массива (списка) делятся на ключ и произвольные данные struct KeyData { K
- 4. Устойчивая сортировка Сортировка называется устойчивой, если она не меняет порядок объектов с одинаковыми ключами a[i].key =
- 5. Классификация алгоритмов сортировки По объёму данных Внутренние Все данные в памяти Внешние Часть данных на диске
- 6. Сортировка включением Разделим элементы массива на неотсортированную часть a[i], ... , а[N] и отсортированную часть a[1],
- 7. Пример Процесс сортировки включениями покажем на примере последовательности, состоящей из восьми ключей: i = 1 40
- 8. Программа void sort_by_insertion(struct KeyData a[], int N) { int i; for (i=1; i =0 && x.key
- 9. Анализ сортировки включением Для числа сравнений Сi во внутреннем цикле на i-м шаге внешнего цикла справедливо
- 10. Сортировка бинарными включениями Если место для a[i] искать методом бинарного поиска в отсортированном массиве, то всего
- 11. Сортировка выбором Разделим элементы массива на неотсортированную часть a[i], ... , а[N] и отсортированную часть a[1],
- 12. Программа void sort_by_selection(struct KeyData key a[], int N) { int i; for( i=0; i a[j].key) k=j;
- 13. Анализ сортировки выбором Число Сi сравнений на i-м шаге внешего цикла есть N-i На первом шаге
- 14. Анализ сортировки выбором Число сравнений в методе выбора всегда равно максимальному числу сравнений в методе простых
- 15. Пирамидальная сортировка Линейный поиск min элемента делает сложность всей сортировки выбором квадратичной Как найти минимальный элемент
- 16. Определение пирамиды Пусть дана последовательность h[1], ..., h[n] Элемент h[i] образует пирамиду в этой последовательности, если
- 17. Полная пирамида при n = 15 Полная пирамида может быть изображена в виде корневого бинарного дерева,
- 18. Пример полной пирамиды при n = 12 Если число элементов в полной пирамиде не равно 2^k
- 19. Макет пирамидальной сортировки Подготовка к сортировке Входная неупорядоченная последовательность перестраивается в пирамиду Сортировка Массив делится на
- 20. Макет пирамидальной сортировки Основой алгоритм является процедура просеивания, так перестраивающая h[i+1], ..., h[n], образующие пирамиду, чтобы
- 21. Просеивание Просеять (h, i, n) пока 2 * i hL и h[i] > hR то конец
- 22. Построение пирамиды h1 h2 h3 h4 h5 h6 h7 h8 h9 h10 Шаг 1, i=5: 52
- 24. Алгоритм пирамидальной сортировки Шаг 1 Построение пирамиды i = n / 2; пока i >= 1
- 25. Просеивание void Sift(struct KeyData а[], int i, int n) { int l; i++; while ((l=2*i) =a[l-1]
- 26. Пирамидальная сортировка void heap_sort(struct KeyData a[], int N) { int i; /* строим полную пирамиду */
- 27. Анализ пирамидальной сортировки Число итераций цикла в процедуре просеивания не превосходит высоты пирамиды Высота полного бинарного
- 28. Понятие сортировки Внутренняя и внешняя сортировка Алгоритмы сортировки Простые Включением, выбором, пузырёк Улучшенные Пирамидальная, быстрая Анализ
- 29. Сортировка простым обменом (пузырёк) На первом шаге сравним последний и предпоследний элементы, если они не упорядочены,
- 30. Пример i = 0 40 51 8 38 90 14 2 63 i = 1 2
- 31. Алгоритм (метод пузырька) для i от 2 до N с шагом 1 // проход от конца
- 32. Анализ Поскольку число сравнений Сi на i-м шаге внешнего цикла равно N-i Cmin = Cmax =
- 33. Последние проходы сортировки простым обменом работают «вхолостую», если элементы уже упорядочены Запомним, производился ли на очередном
- 34. Шейкер-сортировка (алгоритм) left = 1 // левая граница несортированной части right = N // правая граница
- 35. если не упор то // TODO – rewrite упор = истина i = right пока i
- 36. Программа void shaker_sort (struct KeyData A [], int N) { int left = 0, right =
- 37. Продолжение программы if (!sorted) for (i = left+1; i if (A[i-1] > A[i]) { struct KeyData
- 38. Анализ Сmin= N –1, Сmax = O(N*N) Число пересылок такое же как для сортировки пузырьком Каждый
- 39. Сортировка подсчётом Для каждого элемента подсчитаем число элементов, которые меньше его Это число (+1) есть его
- 40. Алгоритм (на одном массиве) i = 1; // номер 1-го элемента в несортированной части массива пока
- 41. Сортировка с разделением Быстрая сортировка Ч. Э. Р. Хоар В время парктики Московском Государственном Университете им.
- 42. Сортировка разделением, идея алгоритма Пусть a[m] произвольный пилотируемый элемент Разделим элементы массива относительно a[m] так, что
- 43. Сортировка разделением (макет) СортировкаРазделением (a, l, r) выбрать пилотируемый элемент m разделить а[l],…, а[r] относительно a[m]
- 44. Анализ макета Массив упорядочивается "сам собой" по мере упорядочения его частей?! Рекурсия приводит к сортировке массива
- 45. Разделение массива Пусть x = a[m] – значение пилотируемого элемента Сортируемую часть массива разделим на три
- 46. Процесс разделения i = l; j = r; пока i = х */ конец пока х
- 47. Комментарии Циклы по встречным индексам переносят из средней части в левую или правую элементы, строго меньшие
- 48. Комментарии Проверка того, что бегущие индексы не выходят за границы l...r не нужна На первом проходе
- 49. Комментарии Цикл оканчивается при i ≥ j. Однако нам еще надо определить медиану. Определенные границы левой
- 50. Разделение: 40 51 8 38 89 1 15 63 Начало: i x j Первый проход:i j
- 51. Пример быстрой сортировки
- 52. Программа void quicksort(struct KeyData a[], int l, int r) { int i = l, j =
- 53. Анализ Число сравнений и пересылок зависит от выбора пилотируемого элемента Если брать пилотируемый элемент равным медиане
- 54. Нижняя граница числа сравнений в сортировке Для сортировки массива из N элементов необходимо О( N *
- 55. Дерево решений для массива из 3 элементов
- 56. Для задачи сортировки в дереве решений N! листьев Значит, высота дерева решений ≥ log2(N) Из неравенства
- 57. Заключение Понятие сортировки Внутренняя и внешняя сортировка Алгоритмы сортировки Простые Включением, выбором, пузырёк Улучшенные Пирамидальная, быстрая
- 58. Просуммируем всевозможные варианты выбора медианы и разделим эту сумму на N, в результате получим ожидаемое число
- 59. Однако в худшем случае сортировка становится «медленной». Например, когда в качестве пилотируемого элемента всегда выбирается наибольшее
- 60. Алгоритм Условно разделить массив A на отсортированную и несортированную части. К сортированной части сначала относится только
- 61. Сортировка включениями с убывающим шагом. Метод Шелла Хоар, Флойд, Шелл: для алгоритмов сортировки, перемещающих в последовательности
- 62. Пример работы сортировки Шелла На первом проходе выделим в подпоследовательности элементы, отстоящие друг от друга на
- 63. Пример работы сортировки Шелла, продолжение В результате 4-сортировки получим последовательность: _________________________________ | | | | 40
- 64. Выбор шага в сортировке Шелла В сортировке методом Шелла можно использовать любую убывающую последовательность шагов ht,
- 65. Анализ эффективности метода Утверждение Если k-отсортированная последовательность i-сортируется (k > i), то она остается k-отсортированной. →
- 66. Алгоритм процедура Вставка(b, h) // b — номер первого элемента последовательности // h – величина шага
- 67. Алгоритм, продолжение Основная программа: // Выбор начального шага: h = 1; пока h h = 3*h
- 68. Сортировка простым выбором Методы сортировки посредством выбора основаны на идее многократного выбора. На i-м шаге выбирается
- 69. Пример Проиллюстрируем этот метод на той же последовательности ⎪40 51 8 38 90 14 2 63.
- 70. Обсуждение Данный метод в некотором смысле противоположен сортировке простыми включениями. При сортировке простым выбором рассматриваются все
- 71. Алгоритм Условно разделить массив А на отсортированную и несортированную части. Сначала весь массив — это несортированная
- 72. Пирамидальная сортировка На каждом шаге сортировки первый элемент массива, минимальный элемент пирамиды, переносится в начало готовой
- 74. Скачать презентацию