Презентация "Сортировка массивов"
Подписи к слайдам:
Сортировка массивов
- <number>
- Тема 4.
- <number>
- Постановка задачи сортировки
- Простые алгоритмы сортировки
- Быстрые алгоритмы сортировки
- Алгоритмы поиска
- Содержание
- <number>
- 1. Постановка задачи сортировки
- <number>
- Эта Тема посвящена сугубо алгоритмической проблеме упорядочения данных.
- Необходимость отсортировать какие-либо величины возникает в программировании очень часто. К примеру, входные данные подаются "вперемешку", а вашей программе удобнее обрабатывать упорядоченную последовательность.
- Существуют ситуации, когда предварительная сортировка данных позволяет сократить содержательную часть алгоритма в разы, а время его работы - в десятки раз.
- <number>
- Однако верно и обратное. Сколь бы хорошим и эффективным ни был выбранный вами алгоритм, но если в качестве подзадачи он использует "плохую" сортировку, то вся работа по его оптимизации оказывается бесполезной.
- Неудачно реализованная сортировка входных данных способна заметно понизить эффективность алгоритма в целом.
- <number>
- Методы упорядочения подразделяются на
- внутренние (обрабатывающие массивы)
- и внешние (занимающиеся только файлами).
- В этой Теме рассматриваются только внутренние методы сортировки.
- Их важная особенность состоит в том, что эти алгоритмы не требуют дополнительной памяти:
- вся работа по упорядочению производится внутри одного и того же массива.
- <number>
- Под сортировкой последовательности понимают процесс перестановки элементов последовательности в определенном порядке: по возрастанию, убыванию, последней цифре, сумме делителей, … .
- Под сортировкой последовательности понимают процесс перестановки элементов последовательности в определенном порядке: по возрастанию, убыванию, последней цифре, сумме делителей, … .
- Пусть дана последовательность элементов a1, a2, ... , an.
- Элементы этой последовательности – данные произвольного типа, на котором определено отношение порядка “<” (меньше) такое, что любые два различных элемента сравнимы между собой.
- Сортировка означает перестановку элементов последовательности ak1, ak2, ... , akn такую, что
- ak1 < ak2 < ... < akn.
- <number>
- Основными требованиями к программе сортировки массива являются эффективность по времени и экономное использование памяти.
- Это означает, что алгоритм не должен использовать дополнительных массивов и пересылок из массива a в эти массивы.
- Постановка задачи сортировки в общем виде предполагает, что существуют только два типа действий с данными сортируемого типа:
- сравнение двух элементов (x<y)
- и пересылка элемента (x:=y).
- Поэтому удобная мера сложности алгоритма сортировки массива a[1..n]:
- по времени – количество сравнений C(n)
- и количество пересылок M(n).
- <number>
- К простым внутренним сортировкам относят методы, сложность которых пропорциональна квадрату размерности входных данных.
- Иными словами, при сортировке массива, состоящего из N компонент, такие алгоритмы будут выполнять С*N2 действий, где С - некоторая константа. Этот факт принято обозначать следующей символикой: O(N2).
- Простые сортировки
- <number>
- Сортировка
- Алгоритмы:
- простые и понятные, но неэффективные для больших массивов
- метод пузырька
- метод выбора
- сложные, но эффективные
- «быстрая сортировка» (Quick Sort)
- сортировка «кучей» (Heap Sort)
- сортировка слиянием
- пирамидальная сортировка
- сложность O(N2)
- сложность O(N·logN)
- O(N2)
- время
- N
- O(N·logN)
- <number>
- Количество действий, необходимых для упорядочения некоторой последовательности данных, конечно же, зависит не только от длины этой последовательности, но и от ее структуры.
- Например, если на вход подается уже упорядоченная последовательность (о чем программа, понятно, не знает), то количество действий будет значительно меньше, чем в случае перемешанных входных данных.
- Простые сортировки
- <number>
- Как правило, сложность алгоритмов подсчитывают раздельно по количеству сравнений и по количеству перемещений данных в памяти (пересылок), поскольку выполнение этих операций занимает различное время.
- Однако точные значения удается найти редко, поэтому для оценки алгоритмов ограничиваются лишь понятием "пропорционально", которое не учитывает конкретные значения констант, входящих в итоговую формулу.
- Общую же эффективность алгоритма обычно оценивают "в среднем": как среднее арифметическое от сложности алгоритма "в лучшем случае" и "в худшем случае", то есть
- (Eff_best + Eff_worst)/2.
- Простые сортировки
- <number>
- 2. Простые алгоритмы сортировки
- <number>
- Метод пузырька
- Идея – пузырек воздуха в стакане воды поднимается со дна вверх.
- Для массивов – самый маленький («легкий» элемент перемещается вверх («всплывает»).
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
- начиная снизу, сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами
- за 1 проход по массиву один элемент (самый маленький) становится на свое место
|
|
|
|
|
|
|
|
|
|
|
|
- 1-ый проход
- 2-ой проход
- 3-ий проход
|
|
|
|
|
|
|
|
- Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов).
- <number>
- Программа
- 1-ый проход:
|
|
|
|
|
|
|
|
|
|
- сравниваются пары
- A[N-1] и A[N], A[N-2] и A[N-1]
- …
- A[1] и A[2]
- A[j] и A[j+1]
- 2-ой проход
- A[1] уже на своем месте!
- !
- for j:=N-1 downto 2 do
- if A[j] > A[j+1] then begin
- c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c;
- end;
- 2
- for j:=N-1 downto 1 do
- if A[j] > A[j+1] then begin
- c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c;
- end;
- 1
- i-ый проход
- for j:=N-1 downto i do
- ...
- i
|
|
|
|
|
|
|
|
|
|
- <number>
- Программа
- program qq;
- const N = 10;
- var A: array[1..N] of integer;
- i, j, c: integer;
- begin
- { заполнить массив }
- { вывести исходный массив }
- { вывести полученный массив }
- end.
- for i:=1 to N-1 do begin
- for j:=N-1 downto i do
- if A[j] > A[j+1] then begin
- с := A[j];
- A[j] := A[j+1];
- A[j+1] := с;
- end;
- end;
- Почему цикл по i до N-1?
- ?
- i
- элементы выше A[i] уже поставлены
- <number>
- Внешний цикл выполнился n–1 раз. Внутренний цикл выполняется j раз (K = n–2, n–1, ..., 1).
- Каждое выполнение тела внутреннего цикла заключается в одном сравнении и, возможно, в одной перестановке. Поэтому
- C(n) =1+2+ ...+n–1 = n*(n–1)/2,
- M(n) = n*(n–1)/2.
- В худшем случае (когда элементы исходного массива расположены в порядке убывания)
- C(n) =n*(n–1)/2= O(n2),
- M(n) = n*(n–1)/2= O(n2).
- Эффективность метода пузырька
- <number>
- Метод пузырька с флажком
- Идея – если при выполнении метода пузырька не было обменов, массив уже отсортирован и остальные проходы не нужны.
- Реализация: переменная-флаг, показывающая, был ли обмен; если она равна False, то выход.
- repeat
- flag := False; { сбросить флаг }
- for j:=N-1 downto 1 do
- if A[j] > A[j+1] then begin
- с := A[j];
- A[j] := A[j+1];
- A[j+1] := с;
- flag := True; { поднять флаг }
- end;
- until not flag; { выход при flag=False }
- flag := False;
- flag := True;
- not flag;
- var flag: boolean;
|
|
|
|
|
|
|
|
- Как улучшить?
- ?
- <number>
- Метод пузырька с флажком
- i := 0;
- repeat
- i := i + 1;
- flag := False; { сбросить флаг }
- for j:=N-1 downto 1 do
- if A[j] > A[j+1] then begin
- с := A[j];
- A[j] := A[j+1];
- A[j+1] := с;
- flag := True; { поднять флаг }
- end;
- until not flag; { выход при flag=False }
- i := 0;
- i
- i := i + 1;
- <number>
- Метод выбора
- Идея:
- найти минимальный элемент и поставить на первое место (поменять местами с A[1])
- из оставшихся найти минимальный элемент и поставить на второе место (поменять местами с A[2]), и т.д.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
- <number>
- Метод выбора
- for i := 1 to N-1 do begin
- nMin = i ;
- for j:= i+1 to N do
- if A[j] < A[nMin] then nMin:=j;
- if nMin <> i then begin
- c:=A[i];
- A[i]:=A[nMin];
- A[nMin]:=c;
- end;
- end;
- N-1
- N
- нужно N-1 проходов
- поиск минимального от A[i] до A[N]
- если нужно, переставляем
- Можно ли убрать if?
- ?
- i+1
- i
- <number>
- Самый простой способ сортировки, который приходит в голову, - это упорядочение данных по мере их поступления.
- В этом случае при вводе каждого нового значения можно опираться на тот факт, что все предыдущие элементы уже образуют отсортированную последовательность.
- При этом, разумеется, можно прочитать все вводимые элементы одновременно, записать их в массив, а потом "воображать", что каждый очередной элемент был введен только что. На суть и структуру алгоритма это не повлияет.
- Сортировка простыми вставками
- <number>
- Алгоритм ПрВст
- Первый элемент записать "не раздумывая".
- Пока не закончится последовательность вводимых данных, для каждого нового ее элемента выполнять следующие действия:
- начав с конца уже существующей упорядоченной последовательности, все ее элементы, которые больше, чем вновь вводимый элемент, сдвинуть на 1 шаг назад;
- записать новый элемент на освободившееся место.
- Сортировка простыми вставками
- <number>
- Фрагмент программы:
- Сортировка простыми вставками
- for i:= 2 to N do
- if a[i-1]>a[i] then begin {*}
- x:= a[i];
- j:= i-1;
- while (j>0) and (a[j]>x) do begin {**}
- a[j+1]:= a[j];
- j:= j-1;
- end;
- a[j+1]:= x;
- end;
- <number>
- Чтобы сократить количество сравнений, производимых нашей программой, дополним сортируемый массив нулевой компонентой (это следует сделать в разделе описаний var) и будем записывать в нее поочередно каждый вставляемый элемент (сравните строки {*} и {**} в приведенных вариантах программы).
- В тех случаях, когда вставляемое значение окажется меньше, чем a[1], компонента a[0] будет работать как "барьер", не дающий индексу j выйти за нижнюю границу массива.
- Кроме того, компонента a[0] может заменить собою и дополнительную переменную х.
- Метод прямых вставок с барьером
- <number>
- Фрагмент программы:
- for i:= 2 to N do
- if a[i-1]>a[i] then begin
- a[0]:= a[i]; {*}
- j:= i-1;
- while a[j]>a[0] do begin {**}
- a[j+1]:= a[j];
- j:= j-1;
- end;
- a[j+1]:= a[0];
- end;
- Метод прямых вставок с барьером
- <number>
- Эффективность алгоритма.
- Понятно, что для этой сортировки наилучшим будет случай, когда на вход подается уже упорядоченная последовательность данных. Тогда алгоритм совершит
- N-1 сравнение
- и 0 пересылок данных.
- В худшем же случае - когда входная последовательность упорядочена "наоборот" будет
- сравнений (N+1)*N/2,
- а пересылок (N-1)*(N+3).
- Таким образом, этот алгоритм имеет сложность О(N2) по обоим параметрам.
- Метод прямых вставок с барьером
- <number>
- Пример сортировки.
- Предположим, что нужно отсортировать следующий набор чисел:
- 5 3 4 3 6 2 1
- Выполняя алгоритм, получим такие результаты (подчеркнута уже отсортированная часть массива, полужирным выделена сдвигаемая последовательность, а квадратиком выделен вставляемый элемент):
- Метод прямых вставок с барьером
- <number>
- Сортировку простыми вставками можно немного улучшить:
- поиск "подходящего места" в упорядоченной последовательности можно вести более экономичным способом, который называется Двоичный поиск в упорядоченной последовательности.
- Он напоминает детскую игру "больше-меньше": после каждого сравнения обрабатываемая последовательность сокращается в два раза.
- Сортировка бинарными вставками
- <number>
- Пусть, к примеру, нужно найти место для элемента 7 в таком массиве:
- [2 4 6 8 10 12 14 16 18]
- Найдем средний элемент этой последовательности (10) и сравним с ним семерку. После этого все, что больше 10 (да и саму десятку тоже), можно смело исключить из дальнейшего рассмотрения:
- [2 4 6 8] 10 12 14 16 18
- Снова возьмем середину в отмеченном куске последовательности, чтобы сравнить ее с семеркой.
- Однако здесь нас поджидает небольшая проблема: точной середины у новой последовательности нет, поэтому нужно решить, который из двух центральных элементов станет этой "серединой". От того, к какому краю будет смещаться выбор в таких "симметричных" случаях, зависит окончательная реализация нашего алгоритма.
- Сортировка бинарными вставками
- <number>
- Давайте договоримся, что новой "серединой" последовательности всегда будет становиться левый центральный элемент. Это соответствует вычислению номера "середины" по формуле
- nomer_sred:= (nomer_lev + nomer_prav) div 2
- Итак, отсечем половину последовательности:
- 2 4 [6 8] 10 12 14 16 18
- И снова:
- 2 4 6 [8] 10 12 14 16 18
- 2 4 6] [8 10 12 14 16 18
- Таким образом, мы нашли в исходной последовательности место, "подходящее" для нового элемента.
- Сортировка бинарными вставками
- <number>
- Если бы в той же самой последовательности нужно было найти позицию не для семерки, а для девятки, то последовательность границ рассматриваемых промежутков была бы такой:
- [2 4 6 8] 10 12 14 16 18
- 2 4 [6 8] 10 12 14 16 18
- 2 4 6 [8] 10 12 14 16 18
- 2 4 6 8] [10 12 14 16 18
- Сортировка бинарными вставками
- <number>
- Из приведенных примеров уже видно, что поиск ведется до тех пор, пока левая граница не окажется правее (!) правой границы.
- Кроме того, по завершении этого поиска последней левой границей окажется как раз тот элемент, на котором необходимо закончить сдвиг "хвоста" последовательности.
- Сортировка бинарными вставками
- <number>
- Будет ли такой алгоритм универсальным?
- Давайте проверим, что же произойдет, если мы станем искать позицию для единицы:
- [2 4 6 8] 10 12 14 16 18
- [2] 4 6 8 10 12 14 16 18]
- [2 4 6 8 10 12 14 16 18
- Как видим, правая граница становится неопределенной - выходит за пределы массива.
- Будет ли этот факт иметь какие-либо неприятные последствия?
- Очевидно, нет, поскольку нас интересует не правая, а левая граница.
- Сортировка бинарными вставками
- <number>
- Добавим число 21 в последовательность.
- 2 4 6 8 10 [12 14 16 18]
- 2 4 6 8 10 12 14 [16 18]
- 2 4 6 8 10 12 14 16 [18]
- 2 4 6 8 10 12 14 16 18][
- Кажется, будто все плохо: левая граница вышла за пределы массива; непонятно, что нужно сдвигать...
- Вспомним, однако, что в реальности на (N+1)-й позиции как раз и находится вставляемый элемент (21).
- Таким образом, если левая граница вышла за рассматриваемый диапазон, получается, что ничего сдвигать не нужно.
- Вообще же такие действия выглядят явно лишними, поэтому от них стоит застраховаться, введя одну дополнительную проверку в текст алгоритма.
- Сортировка бинарными вставками
- <number>
- Фрагмент программы:
- for i:= 2 to n do
- if a[i-1]>a[i] then begin
- x:= a[i];
- left:= 1; right:= i-1;
- repeat
- sred:= (left+right) div 2;
- if a[sred]<x then
- left:= sred+1
- else right:= sred-1;
- until left>right;
- for j:=i-1 downto left do
- a[j+1]:= a[j];
- a[left]:= x;
- end;
- Сортировка бинарными вставками
- <number>
- Эффективность алгоритма.
- Теперь на каждом шаге выполняется не N, а log2N проверок, что уже значительно лучше (для примера, сравните 1000 и 10= log21024).
- Следовательно, всего будет совершено N* log2N сравнений.
- По количеству пересылок алгоритм по-прежнему имеет сложность О(N2).
- Сортировка бинарными вставками
- <number>
- 3. Быстрые алгоритмы сортировки
- <number>
- В отличие от простых сортировок, имеющих сложность O(N2), к улучшенным сортировкам относятся алгоритмы с общей сложностью O(N*logN).
- Необходимо, однако, отметить, что на небольших наборах сортируемых данных (N<100) эффективность быстрых сортировок не столь очевидна:
- выигрыш становится заметным только при больших N.
- Следовательно, если необходимо отсортировать маленький набор данных, то выгоднее взять одну из простых сортировок.
- <number>
- Эта сортировка базируется на уже известном нам алгоритме простых вставок.
- Смысл ее состоит в раздельной сортировке методом простых вставок нескольких частей, на которые разбивается исходный массив.
- Эти разбиения помогают сократить количество пересылок:
- для того, чтобы освободить "правильное" место для очередного элемента, приходится уже сдвигать меньшее количество элементов.
- Сортировка Шелла
- <number>
- Сортировку Шелла придумал Дональд Л. Шелл.
- Ее необычность состоит в том, что она рассматривает весь список как совокупность перемешанных подсписков.
- На первом шаге эти подсписки представляют собой просто пары элементов.
- На втором шаге в каждой группе по четыре элемента.
- При повторении процесса число элементов в каждом подсписке увеличивается, а число подсписков, соответственно, падает.
- Сортировка Шелла
- <number>
- Сортирует элементы массива А[1..n] следующим образом:
- на первом шаге упорядочиваются элементы n/2 пар (A[i], А[n/2 + i]) для 1 < i < n/2,
- на втором шаге упорядочиваются элементы в n/4 группах из четырех элементов ( A[i], A[n/4 + i], A[n/2 + i], A[3n/4 + i]) для 1 < i < n/4,
- на третьем шаге упорядочиваются элементы в n/8 группах из восьми элементов и т.д.;
- на последнем шаге упорядочиваются элементы сразу во всем массиве А.
- На каждом шаге для упорядочивания элементов используется метод сортировки вставками.
- Сортировка Шелла
- <number>
- На рис. а изображены восемь подсписков, по два элемента в каждом, в которых
- первый подсписок содержит первый и девятый элементы,
- второй подсписок — второй и десятый элементы,
- и так далее.
- Сортировка Шелла
- <number>
- На рис. б мы видим уже четыре подсписка по четыре элемента в каждом:
- первый подсписок на этот раз содержит первый, пятый, девятый и тринадцатый элементы.
- второй подсписок состоит из второго, шестого, десятого и четырнадцатого элементов.
- Сортировка Шелла
- <number>
- На рис. в показаны два подсписка, состоящие из элементов с нечетными и четными номерами соответственно.
- Сортировка Шелла
- <number>
- На рис. г мы вновь возвращаемся к одному списку.
- Сортировка Шелла
- <number>
- Фрагмент программы:
- incr:= n div 2;
- while incr>0 do begin
- for i:=incr+1 to n do begin
- j:= i-incr;
- while j>0 do
- if A[j]>A[j+incr] then begin
- c:= A[j]; A[j]:=A[j+incr];
- A[j+incr]:=A[j];
- j:=j-incr
- end
- else j:=0 { останов проверки}
- end;
- incr:= incr div 2
- end;
- Сортировка Шелла
- <number>
- Полный анализ сортировки Шелла чрезвычайно сложен, и мы не собираемся на нем останавливаться.
- Было доказано, что сложность этого алгоритма в наихудшем случае при выбранных нами значениях шага равна O(n3/2).
- Полный анализ сортировки Шелла и влияния на сложность последовательности шагов можно найти в третьем томе книги Д. Кнута Искусство программирования, М., Мир.
- Сортировка Шелла
- <number>
- Попытаемся теперь усовершенствовать другой рассмотренный выше простой алгоритм: сортировку простым выбором.
- Р.Флойд предложил перестроить линейный массив в пирамиду - своеобразное бинарное дерево, - а затем искать минимум только среди тех элементов, которые находятся непосредственно "под" текущим вставляемым.
- Пирамидальная сортировка
- <number>
- Для начала необходимо перестроить исходный массив так, чтобы он превратился в пирамиду, где каждый элемент "опирается" на два меньших.
- Этот процесс назвали просеиванием, потому что он очень напоминает процесс разделения некоторой смеси (камней, монет, т.п.) на фракции в соответствии с размерам частиц:
- на нескольких грохотах последовательно задерживаются сначала крупные, а затем все более мелкие частицы.
- Пирамидальная сортировка: просеивание
- <number>
- Итак, будем рассматривать наш линейный массив как пирамидальную структуру:
|
|||||
|
|
||||
|
|
|
|
||
|
|
|
|
|
|
- Видно, что любой элемент a[i] (1<=i<=N div 2) "опирается" на элементы a[2*i] и a[2*i+1].
- И в каждой такой тройке максимальный элемент должен находится "сверху".
- Конечно, исходный массив может и не удовлетворять этому свойству, поэтому его потребуется немного перестроить.
- Пирамидальная сортировка: просеивание
- <number>
|
|||||
|
|
||||
|
|
|
|
||
|
|
|
|
|
|
- Начнем процесс просеивания "снизу". Половина элементов (с ((N div 2)+1)-го по N-й) являются основанием пирамиды, их просеивать не нужно.
- А для всех остальных элементов (двигаясь от конца массива к началу) проверяем тройки a[i] , a[2*i] и a[2*i+1] и перемещать максимум "наверх" - в элемент a[i]. При этом, если в результате одного перемещения нарушается пирамидальность в другой (ниже лежащей) тройке элементов, там снова необходимо "навести порядок" - и так до самого "низа" пирамиды.
- Пирамидальная сортировка: просеивание
- <number>
- Фрагмент программы алгоритма просеивания:
- for i:= (N div 2)downto 1 do begin
- j:=i;
- while j<=(N div 2) do begin
- k:=2*j;
- if (k+1<=N) and (a[k]<a[k+1]) then
- k:=k+1;
- if a[k]>a[j] then begin
- x:=a[j]; a[j]:=a[k]; a[k]:=x;
- j:=k end
- else break
- end
- end;
- Пирамидальная сортировка: просеивание
- <number>
- Пример результата просеивания
- Возьмем массив [1,7,5,4,9,8,12,11,2,10,3,6] (N = 12).
- Его исходное состояние таково (серым цветом выделено "основание" пирамиды, не требующее просеивания):
- Пирамидальная сортировка
|
|||||
|
|
||||
|
|
|
|
||
|
|
|
|
|
|
- Пирамидальная сортировка: просеивание
- <number>
|
|||||
|
|
||||
|
|
|
|
||
|
|
|
|
|
|
- перестановка не требуется
- Пирамидальная сортировка: просеивание
- <number>
|
|||||
|
|
||||
|
|
|
|
||
|
|
|
|
|
|
- перестановка элементов 9 и 10
|
|||||
|
|
||||
|
|
|
|
||
|
|
|
|
|
|
- Пирамидальная сортировка: просеивание
- <number>
|
|||||
|
|
||||
|
|
|
|
||
|
|
|
|
|
|
- перестановка элементов 4 и 11
|
|||||
|
|
||||
|
|
|
|
||
|
|
|
|
|
|
- Пирамидальная сортировка: просеивание
- <number>
|
|||||
|
|
||||
|
|
|
|
||
|
|
|
|
|
|
- перестановка элементов 5 и 12
|
|||||
|
|
||||
|
|
|
|
||
|
|
|
|
|
|
- элемент 5 сыновей не имеет, проверка вниз не производится
- Пирамидальная сортировка: просеивание
- <number>
|
|||||
|
|
||||
|
|
|
|
||
|
|
|
|
|
|
- перестановка элементов 7 и 11
|
|||||
|
|
||||
|
|
|
|
||
|
|
|
|
|
|
- производится проверка тройки элементов 7, 4 и 2; перестановка не требуется
- Пирамидальная сортировка: просеивание
- <number>
|
|||||
|
|
||||
|
|
|
|
||
|
|
|
|
|
|
|
|||||
|
|
||||
|
|
|
|
||
|
|
|
|
|
|
- производится проверка тройки элементов 1, 8 и 5; требуется перестановка 1 и 8
|
|||||
|
|
||||
|
|
|
|
||
|
|
|
|
|
|
- производится проверка пары элементов 1 и 6; требуется перестановка 1 и 6
|
|||||
|
|
||||
|
|
|
|
||
|
|
|
|
|
|
- перестановка элементов 1 и 12
- Пирамидальная сортировка: просеивание
- <number>
- Итак, мы превратили исходный массив в пирамиду:
- в любой тройке a[i], a[2*i] и a[2*i+1] максимум находится "сверху".
- Пирамидальная сортировка: просеивание
- <number>
- Для того чтобы отсортировать массив методом Пирамиды, необходимо выполнить такую последовательность действий:
- 0-й шаг: Превратить исходный массив в пирамиду (с помощью просеивания).
- 1-й шаг: Для N-1 элементов, начиная с последнего, производить следующие действия:
- поменять местами очередной "рабочий" элемент с первым;
- просеять (новый) первый элемент, не затрагивая, однако, уже отсортированный хвост последовательности (элементы с i-го по N-й).
- Пирамидальная сортировка: алгоритм
- <number>
- Часть программы, реализующая нулевой шаг алгоритма, приведена в пункте "Просеивание", поэтому здесь приведена только реализацией основного шага 1:
- for i:= N downto 2 do begin
- x:=a[1]; a[1]:=a[i]; a[i]:=x;
- j:= 1; flag:=true;
- while (j<=((i-1)div 2)) and flag do begin
- k:=2*j;
- if (k+1<=i-1) and (a[k]<a[k+1]) then
- k:= k+1;
- if a[k]>a[j] then begin
- x:=a[j]; a[j]:=a[k]; a[k]:= x;
- j:= k end
- else flag:=false
- end
- end;
- Пирамидальная сортировка
- <number>
- Продолжим сортировку массива, для которого мы уже построили пирамиду:
- [12, 11, 8, 7, 10, 6, 5, 4, 2, 9, 3, 1].
- С целью экономии места не будем далее прорисовывать структуру пирамиды.
- Подчеркивание будет отмечать элементы, участвовавшие в просеивании, а квадратными скобками – те элементы, которые участвуют в дальнейшей обработке.
- Пирамидальная сортировка: пример
- <number>
- 1) Меняем местами a[1] и a[12]:
- [1, 11, 8, 7, 10, 6, 5, 4, 2, 9, 3], 12;
- 2) Просеивая элемент a[1], последовательно получаем:
- [11, 1, 8, 7, 10, 6, 5, 4, 2, 9, 3], 12;
- [11, 10, 8, 7, 1, 6, 5, 4, 2, 9, 3], 12;
- [11, 10, 8, 7, 9, 6, 5, 4, 2, 1, 3], 12;
- 3) Меняем местами a[1] и a[11]:
- [3, 10, 8, 7, 9, 6, 5, 4, 2, 1], 11, 12;
- 4) Просеивая a[1], последовательно получаем:
- [10, 3, 8, 7, 9, 6, 5, 4, 2, 1], 11, 12;
- [10, 9, 8, 7, 3, 6, 5, 4, 2, 1], 11, 12;
- [10, 9, 8, 7, 3, 6, 5, 4, 2, 1], 11, 12;
- Пирамидальная сортировка: пример
- <number>
- 5) Меняем местами a[1] и a[10]:
- [1, 9, 8, 7, 3, 6, 5, 4, 2], 10, 11, 12;
- 6) Просеиваем элемент a[1]:
- [9, 1, 8, 7, 3, 6, 5, 4, 2], 10, 11, 12;
- [9, 7, 8, 1, 3, 6, 5, 4, 2], 10, 11, 12;
- [9, 7, 8, 4, 3, 6, 5, 1, 2], 10, 11, 12;
- 7) Меняем местами a[1] и a[9]:
- [2, 7, 8, 4, 3, 6, 5, 1], 9, 10, 11, 12;
- 8) Просеиваем элемент a[1]:
- [8, 7, 2, 4, 3, 6, 5, 1], 9, 10, 11, 12;
- [8, 7, 6, 4, 3, 2, 5, 1], 9, 10, 11, 12;
- Пирамидальная сортировка: пример
- <number>
- 5) Меняем местами a[1] и a[10]:
- [1, 9, 8, 7, 3, 6, 5, 4, 2], 10, 11, 12;
- 6) Просеиваем элемент a[1]:
- [9, 1, 8, 7, 3, 6, 5, 4, 2], 10, 11, 12;
- [9, 7, 8, 1, 3, 6, 5, 4, 2], 10, 11, 12;
- [9, 7, 8, 4, 3, 6, 5, 1, 2], 10, 11, 12;
- 7) Меняем местами a[1] и a[9]:
- [2, 7, 8, 4, 3, 6, 5, 1], 9, 10, 11, 12;
- 8) Просеиваем элемент a[1]:
- [8, 7, 2, 4, 3, 6, 5, 1], 9, 10, 11, 12;
- [8, 7, 6, 4, 3, 2, 5, 1], 9, 10, 11, 12;
- Пирамидальная сортировка: пример
- <number>
- 9) Меняем местами a[1] и a[8]:
- [1, 7, 6, 4, 3, 2, 5], 8, 9, 10, 11, 12;
- 10) Просеиваем элемент a[1]:
- [7, 1, 6, 4, 3, 2, 5], 8, 9, 10, 11, 12;
- [7, 4, 6, 1, 3, 2, 5], 8, 9, 10, 11, 12;
- 11) Меняем местами a[1] и a[7]:
- [5, 4, 6, 1, 3, 2], 7, 8, 9, 10, 11, 12;
- 12) Просеиваем элемент a[1]:
- [6, 4, 5, 1, 3, 2], 7, 8, 9, 10, 11, 12;
- Пирамидальная сортировка: пример
- <number>
- 13) Меняем местами a[1] и a[6]:
- [2, 4, 5, 1, 3], 6, 7, 8, 9, 10, 11, 12;
- 14) Просеиваем элемент a[1]:
- [5, 4, 2, 1, 3], 6, 7, 8, 9, 10, 11, 12;
- 15) Меняем местами a[1] и a[5]:
- [3, 4, 2, 1], 5, 6, 7, 8, 9, 10, 11, 12;
- 16) Просеиваем элемент a[1]:
- [4, 3, 2, 1], 5, 6, 7, 8, 9, 10, 11, 12;
- 17) Меняем местами a[1] и a[4]:
- [1, 3, 2], 4, 5, 6, 7, 8, 9, 10, 11, 12;
- 18) Просеиваем элемент a[1]:
- [3, 1, 2], 4, 5, 6, 7, 8, 9, 10, 11, 12;
- Пирамидальная сортировка: пример
- <number>
- 19) Меняем местами a[1] и a[3]:
- [2, 1], 3, 4, 5, 6, 7, 8, 9, 10, 11, 12;
- 20) Просеивать уже ничего не нужно;
- 21) Меняем местами a[1] и a[2]:
- [1], 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12;
- 22) Просеивать ничего не нужно, сортировка закончена.
- Пирамидальная сортировка: пример
- <number>
- Эффективность алгоритма
- Пирамидальная сортировка хорошо работает с большими массивами, однако на маленьких примерах (N<20) выгода от ее применения может быть не слишком очевидна.
- В среднем этот алгоритм имеет сложность O(N*log N).
- Пирамидальная сортировка
- <number>
- «Быстрая сортировка» (Quick Sort)
- Идея – более эффективно переставлять элементы, расположенные дальше друг от друга.
- Сколько перестановок нужно, если массив отсортирован по убыванию, а надо – по возрастанию?
- ?
- N div 2
- 2 шаг: переставить элементы так:
- при сортировке элементы не покидают « свою область»!
- 1 шаг: выбрать некоторый элемент массива X
|
|
- 3 шаг: так же отсортировать две получившиеся области
- Разделяй и властвуй (англ. divide and conquer)
- <number>
- «Быстрая сортировка» (Quick Sort)
- Медиана – такое значение X, что слева и справа от него в отсортированном массиве стоит одинаковое число элементов (для этого надо отсортировать массив…).
- Разделение:
- выбрать средний элемент массива (X=67)
- установить L:=1, R:=N
- увеличивая L, найти первый элемент A[L], который >= X (должен стоять справа)
- уменьшая R, найти первый элемент A[R], который <= X (должен стоять слева)
- если L<=R, поменять местами A[L] и A[R] и перейти к п. 3
|
|
|
|
|
|
|
- Как лучше выбрать X?
- ?
|
|
|
|
|
|
|
- <number>
- «Быстрая сортировка» (Quick Sort)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
- L > R : разделение закончено
- !
- <number>
- «Быстрая сортировка» (Quick Sort)
- procedure QSort ( first, last: integer);
- var L, R, c, X: integer;
- begin
- if first < last then begin
- X:= A[(first + last) div 2];
- L:= first; R:= last;
- QSort(first, R); QSort(L, last);
- end;
- end.
- ограничение рекурсии
- while L <= R do begin
- while A[L] < X do L:= L + 1;
- while A[R] > X do R:= R - 1;
- if L <= R then begin
- c:= A[L]; A[L]:= A[R]; A[R]:= c;
- L:= L + 1; R:= R - 1;
- end;
- end;
- разделение
- обмен
- двигаемся дальше
- сортируем две части
- <number>
- «Быстрая сортировка» (Quick Sort)
- program qq;
- const N = 10;
- var A: array[1..N] of integer;
- begin
- { заполнить массив }
- { вывести исходный массив на экран }
- Qsort ( 1, N ); { сортировка }
- { вывести результат }
- end.
- procedure QSort ( first, last: integer);
- ...
- Сложность (в среднем) !
- !
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
- <number>
- Количество перестановок
- (случайные данные)
- От чего зависит скорость?
- ?
- Как хуже всего выбирать X?
- ?
|
|
|
|
|
|
|
- <number>
- 4. Поиск в массиве
- <number>
- Поиск в массиве
- Задача – найти в массиве элемент, равный X, или установить, что его нет.
- Решение: для произвольного массива: линейный поиск (перебор)
- недостаток: низкая скорость
- Как ускорить? – заранее подготовить массив для поиска
- как именно подготовить?
- как использовать «подготовленный массив»?
- <number>
- Линейный поиск
- nX := 0;
- for i:=1 to N do
- if A[i] = X then begin
- nX := i;
- break; {выход из цикла}
- end;
- nX := 0; { пока не нашли ...}
- if nX < 1 then writeln('Не нашли...')
- else writeln('A[', nX, ']=', X);
- nX – номер нужного элемента в массиве
- Что плохо?
- ?
- Улучшение: после того, как нашли X, выходим из цикла.
- for i:=1 to N do { цикл по всем элементам }
- if A[i] = X then { если нашли, то ... }
- nX := i; { ... запомнили номер}
- nX := 0; i := 1;
- while i <= N do begin
- if A[i] = X then begin
- nX := i; i := N;
- end;
- i := i + 1;
- end;
- break;
- i := N;
- <number>
- Двоичный поиск
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
- X = 7
- X < 8
- 8
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
- 4
- X > 4
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
- 6
- X > 6
- Выбрать средний элемент A[c] и сравнить с X.
- Если X = A[c], нашли (выход).
- Если X < A[c], искать дальше в первой половине.
- Если X > A[c], искать дальше во второй половине.
- <number>
- Двоичный поиск
- nX := 0;
- L := 1; R := N; {границы: ищем от A[1] до A[N] }
- if nX < 1 then writeln('Не нашли...')
- else writeln('A[', nX, ']=', X);
- while R >= L do begin
- c := (R + L) div 2;
- if X < A[c] then R := c - 1;
- if X > A[c] then L := c + 1;
- end;
- номер среднего элемента
- if X = A[c] then begin
- nX := c;
- R := L - 1; { break; }
- end;
- нашли
- Почему нельзя while R > L do begin … end; ?
- ?
- выйти из цикла
- сдвигаем границы
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
- <number>
- Сравнение методов поиска
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Информатика - еще материалы к урокам:
- Презентация "Программирование циклических алгоритмов начала программирования" 9 класс
- Презентация "Этапы создания (разработки) web-сайта"
- Презентация "Основные элементы языка Паскаль"
- Презентация "История создания и развития систем программирования"
- Презентация "Жизненный цикл программного обеспечения"
- Презентация "Графика в Pascal ABC.NET"