Тема 4. Сортировка массивов

Содержание

Слайд 2

© С.В.Кухта, 2009 Постановка задачи сортировки Простые алгоритмы сортировки Быстрые алгоритмы сортировки Алгоритмы поиска Содержание

© С.В.Кухта, 2009

Постановка задачи сортировки
Простые алгоритмы сортировки
Быстрые алгоритмы сортировки
Алгоритмы поиска

Содержание

Слайд 3

© С.В.Кухта, 2009 1. Постановка задачи сортировки

© С.В.Кухта, 2009

1. Постановка задачи сортировки

Слайд 4

© С.В.Кухта, 2009 Эта Тема посвящена сугубо алгоритмической проблеме упорядочения данных.

© С.В.Кухта, 2009

Эта Тема посвящена сугубо алгоритмической проблеме упорядочения данных.
Необходимость отсортировать

какие-либо величины возникает в программировании очень часто. К примеру, входные данные подаются "вперемешку", а вашей программе удобнее обрабатывать упорядоченную последовательность.
Существуют ситуации, когда предварительная сортировка данных позволяет сократить содержательную часть алгоритма в разы, а время его работы - в десятки раз.
Слайд 5

© С.В.Кухта, 2009 Однако верно и обратное. Сколь бы хорошим и

© С.В.Кухта, 2009

Однако верно и обратное. Сколь бы хорошим и эффективным

ни был выбранный вами алгоритм, но если в качестве подзадачи он использует "плохую" сортировку, то вся работа по его оптимизации оказывается бесполезной.
Неудачно реализованная сортировка входных данных способна заметно понизить эффективность алгоритма в целом.
Слайд 6

© С.В.Кухта, 2009 Методы упорядочения подразделяются на внутренние (обрабатывающие массивы) и

© С.В.Кухта, 2009

Методы упорядочения подразделяются на
внутренние (обрабатывающие массивы)
и внешние

(занимающиеся только файлами).
В этой Теме рассматриваются только внутренние методы сортировки.
Их важная особенность состоит в том, что эти алгоритмы не требуют дополнительной памяти:
вся работа по упорядочению производится внутри одного и того же массива.
Слайд 7

© С.В.Кухта, 2009 Под сортировкой последовательности понимают процесс перестановки элементов последовательности

© С.В.Кухта, 2009

Под сортировкой последовательности понимают процесс перестановки элементов последовательности в

определенном порядке: по возрастанию, убыванию, последней цифре, сумме делителей, … .

Под сортировкой последовательности понимают процесс перестановки элементов последовательности в определенном порядке: по возрастанию, убыванию, последней цифре, сумме делителей, … .

Пусть дана последовательность элементов a1, a2, ... , an.
Элементы этой последовательности – данные произвольного типа, на котором определено отношение порядка “<” (меньше) такое, что любые два различных элемента сравнимы между собой.
Сортировка означает перестановку элементов последовательности ak1, ak2, ... , akn такую, что
ak1 < ak2 < ... < akn.

Слайд 8

© С.В.Кухта, 2009 Основными требованиями к программе сортировки массива являются эффективность

© С.В.Кухта, 2009

Основными требованиями к программе сортировки массива являются эффективность по

времени и экономное использование памяти.
Это означает, что алгоритм не должен использовать дополнительных массивов и пересылок из массива a в эти массивы.
Постановка задачи сортировки в общем виде предполагает, что существуют только два типа действий с данными сортируемого типа:
сравнение двух элементов (xи пересылка элемента (x:=y).
Поэтому удобная мера сложности алгоритма сортировки массива a[1..n]:
по времени – количество сравнений C(n)
и количество пересылок M(n).
Слайд 9

© С.В.Кухта, 2009 К простым внутренним сортировкам относят методы, сложность которых

© С.В.Кухта, 2009

К простым внутренним сортировкам относят методы, сложность которых пропорциональна

квадрату размерности входных данных.
Иными словами, при сортировке массива, состоящего из N компонент, такие алгоритмы будут выполнять С*N2 действий, где С - некоторая константа. Этот факт принято обозначать следующей символикой: O(N2).

Простые сортировки

Слайд 10

© С.В.Кухта, 2009 Сортировка Алгоритмы: простые и понятные, но неэффективные для

© С.В.Кухта, 2009

Сортировка

Алгоритмы:
простые и понятные, но неэффективные для больших массивов
метод пузырька
метод

выбора
сложные, но эффективные
«быстрая сортировка» (Quick Sort)
сортировка «кучей» (Heap Sort)
сортировка слиянием
пирамидальная сортировка

сложность O(N2)

сложность O(N·logN)

Слайд 11

© С.В.Кухта, 2009 Количество действий, необходимых для упорядочения некоторой последовательности данных,

© С.В.Кухта, 2009

Количество действий, необходимых для упорядочения некоторой последовательности данных, конечно

же, зависит не только от длины этой последовательности, но и от ее структуры.
Например, если на вход подается уже упорядоченная последовательность (о чем программа, понятно, не знает), то количество действий будет значительно меньше, чем в случае перемешанных входных данных.

Простые сортировки

Слайд 12

© С.В.Кухта, 2009 Как правило, сложность алгоритмов подсчитывают раздельно по количеству

© С.В.Кухта, 2009

Как правило, сложность алгоритмов подсчитывают раздельно по количеству сравнений

и по количеству перемещений данных в памяти (пересылок), поскольку выполнение этих операций занимает различное время.
Однако точные значения удается найти редко, поэтому для оценки алгоритмов ограничиваются лишь понятием "пропорционально", которое не учитывает конкретные значения констант, входящих в итоговую формулу.
Общую же эффективность алгоритма обычно оценивают "в среднем": как среднее арифметическое от сложности алгоритма "в лучшем случае" и "в худшем случае", то есть
(Eff_best + Eff_worst)/2.

Простые сортировки

Слайд 13

© С.В.Кухта, 2009 2. Простые алгоритмы сортировки

© С.В.Кухта, 2009

2. Простые алгоритмы сортировки

Слайд 14

© С.В.Кухта, 2009 Метод пузырька Идея – пузырек воздуха в стакане

© С.В.Кухта, 2009

Метод пузырька

Идея – пузырек воздуха в стакане воды поднимается

со дна вверх.
Для массивов – самый маленький («легкий» элемент перемещается вверх («всплывает»).

начиная снизу, сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами
за 1 проход по массиву один элемент (самый маленький) становится на свое место

1-ый проход

2-ой проход

3-ий проход

Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов).

Слайд 15

© С.В.Кухта, 2009 Программа 1-ый проход: сравниваются пары A[N-1] и A[N],

© С.В.Кухта, 2009

Программа

1-ый проход:

сравниваются пары
A[N-1] и A[N], A[N-2] и A[N-1]

…
A[1] и A[2]

A[j] и A[j+1]

2-ой проход

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

Слайд 16

© С.В.Кухта, 2009 Программа program qq; const N = 10; var

© С.В.Кухта, 2009

Программа

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

элементы выше A[i] уже поставлены

Слайд 17

© С.В.Кухта, 2009 Внешний цикл выполнился n–1 раз. Внутренний цикл выполняется

© С.В.Кухта, 2009

Внешний цикл выполнился 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).

Эффективность метода пузырька

Слайд 18

© С.В.Кухта, 2009 Метод пузырька с флажком Идея – если при

© С.В.Кухта, 2009

Метод пузырька с флажком

Идея – если при выполнении метода

пузырька не было обменов, массив уже отсортирован и остальные проходы не нужны.
Реализация: переменная-флаг, показывающая, был ли обмен; если она равна 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;

Слайд 19

© С.В.Кухта, 2009 Метод пузырька с флажком i := 0; repeat

© С.В.Кухта, 2009

Метод пузырька с флажком

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;

Слайд 20

© С.В.Кухта, 2009 Метод выбора Идея: найти минимальный элемент и поставить

© С.В.Кухта, 2009

Метод выбора

Идея:
найти минимальный элемент и поставить на первое место

(поменять местами с A[1])
из оставшихся найти минимальный элемент и поставить на второе место (поменять местами с A[2]), и т.д.
Слайд 21

© С.В.Кухта, 2009 Метод выбора for i := 1 to N-1

© С.В.Кухта, 2009

Метод выбора

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]

если нужно, переставляем

i+1

i

Слайд 22

© С.В.Кухта, 2009 Самый простой способ сортировки, который приходит в голову,

© С.В.Кухта, 2009

Самый простой способ сортировки, который приходит в голову, -

это упорядочение данных по мере их поступления.
В этом случае при вводе каждого нового значения можно опираться на тот факт, что все предыдущие элементы уже образуют отсортированную последовательность.
При этом, разумеется, можно прочитать все вводимые элементы одновременно, записать их в массив, а потом "воображать", что каждый очередной элемент был введен только что. На суть и структуру алгоритма это не повлияет.

Сортировка простыми вставками

Слайд 23

© С.В.Кухта, 2009 Алгоритм ПрВст Первый элемент записать "не раздумывая". Пока

© С.В.Кухта, 2009

Алгоритм ПрВст
Первый элемент записать "не раздумывая".
Пока не закончится

последовательность вводимых данных, для каждого нового ее элемента выполнять следующие действия:
начав с конца уже существующей упорядоченной последовательности, все ее элементы, которые больше, чем вновь вводимый элемент, сдвинуть на 1 шаг назад;
записать новый элемент на освободившееся место.

Сортировка простыми вставками

Слайд 24

© С.В.Кухта, 2009 Фрагмент программы: Сортировка простыми вставками for i:= 2

© С.В.Кухта, 2009

Фрагмент программы:

Сортировка простыми вставками

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;
Слайд 25

© С.В.Кухта, 2009 Чтобы сократить количество сравнений, производимых нашей программой, дополним

© С.В.Кухта, 2009

Чтобы сократить количество сравнений, производимых нашей программой, дополним сортируемый

массив нулевой компонентой (это следует сделать в разделе описаний var) и будем записывать в нее поочередно каждый вставляемый элемент (сравните строки {*} и {**} в приведенных вариантах программы).
В тех случаях, когда вставляемое значение окажется меньше, чем a[1], компонента a[0] будет работать как "барьер", не дающий индексу j выйти за нижнюю границу массива.
Кроме того, компонента a[0] может заменить собою и дополнительную переменную х.

Метод прямых вставок с барьером

Слайд 26

© С.В.Кухта, 2009 Фрагмент программы: for i:= 2 to N do

© С.В.Кухта, 2009

Фрагмент программы:

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;

Метод прямых вставок с барьером

Слайд 27

© С.В.Кухта, 2009 Эффективность алгоритма. Понятно, что для этой сортировки наилучшим

© С.В.Кухта, 2009

Эффективность алгоритма.
Понятно, что для этой сортировки наилучшим будет случай,

когда на вход подается уже упорядоченная последовательность данных. Тогда алгоритм совершит
N-1 сравнение
и 0 пересылок данных.
В худшем же случае - когда входная последовательность упорядочена "наоборот" будет
сравнений (N+1)*N/2,
а пересылок (N-1)*(N+3).
Таким образом, этот алгоритм имеет сложность О(N2) по обоим параметрам.

Метод прямых вставок с барьером

Слайд 28

© С.В.Кухта, 2009 Пример сортировки. Предположим, что нужно отсортировать следующий набор

© С.В.Кухта, 2009

Пример сортировки.
Предположим, что нужно отсортировать следующий набор чисел:
5 3

4 3 6 2 1
Выполняя алгоритм, получим такие результаты (подчеркнута уже отсортированная часть массива, полужирным выделена сдвигаемая последовательность, а квадратиком выделен вставляемый элемент):

Метод прямых вставок с барьером

Слайд 29

© С.В.Кухта, 2009 Сортировку простыми вставками можно немного улучшить: поиск "подходящего

© С.В.Кухта, 2009

Сортировку простыми вставками можно немного улучшить:
поиск "подходящего места"

в упорядоченной последовательности можно вести более экономичным способом, который называется Двоичный поиск в упорядоченной последовательности.
Он напоминает детскую игру "больше-меньше": после каждого сравнения обрабатываемая последовательность сокращается в два раза.

Сортировка бинарными вставками

Слайд 30

© С.В.Кухта, 2009 Пусть, к примеру, нужно найти место для элемента

© С.В.Кухта, 2009

Пусть, к примеру, нужно найти место для элемента 7

в таком массиве:
[2 4 6 8 10 12 14 16 18]
Найдем средний элемент этой последовательности (10) и сравним с ним семерку. После этого все, что больше 10 (да и саму десятку тоже), можно смело исключить из дальнейшего рассмотрения:
[2 4 6 8] 10 12 14 16 18
Снова возьмем середину в отмеченном куске последовательности, чтобы сравнить ее с семеркой.
Однако здесь нас поджидает небольшая проблема: точной середины у новой последовательности нет, поэтому нужно решить, который из двух центральных элементов станет этой "серединой". От того, к какому краю будет смещаться выбор в таких "симметричных" случаях, зависит окончательная реализация нашего алгоритма.

Сортировка бинарными вставками

Слайд 31

© С.В.Кухта, 2009 Давайте договоримся, что новой "серединой" последовательности всегда будет

© С.В.Кухта, 2009

Давайте договоримся, что новой "серединой" последовательности всегда будет становиться

левый центральный элемент. Это соответствует вычислению номера "середины" по формуле
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
Таким образом, мы нашли в исходной последовательности место, "подходящее" для нового элемента.

Сортировка бинарными вставками

Слайд 32

© С.В.Кухта, 2009 Если бы в той же самой последовательности нужно

© С.В.Кухта, 2009

Если бы в той же самой последовательности нужно было

найти позицию не для семерки, а для девятки, то последовательность границ рассматриваемых промежутков была бы такой:
[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

Сортировка бинарными вставками

Слайд 33

© С.В.Кухта, 2009 Из приведенных примеров уже видно, что поиск ведется

© С.В.Кухта, 2009

Из приведенных примеров уже видно, что поиск ведется до

тех пор, пока левая граница не окажется правее (!) правой границы.
Кроме того, по завершении этого поиска последней левой границей окажется как раз тот элемент, на котором необходимо закончить сдвиг "хвоста" последовательности.

Сортировка бинарными вставками

Слайд 34

© С.В.Кухта, 2009 Будет ли такой алгоритм универсальным? Давайте проверим, что

© С.В.Кухта, 2009

Будет ли такой алгоритм универсальным?
Давайте проверим, что же

произойдет, если мы станем искать позицию для единицы:
[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
Как видим, правая граница становится неопределенной - выходит за пределы массива.
Будет ли этот факт иметь какие-либо неприятные последствия?
Очевидно, нет, поскольку нас интересует не правая, а левая граница.

Сортировка бинарными вставками

Слайд 35

© С.В.Кухта, 2009 Добавим число 21 в последовательность. 2 4 6

© С.В.Кухта, 2009

Добавим число 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).
Таким образом, если левая граница вышла за рассматриваемый диапазон, получается, что ничего сдвигать не нужно.
Вообще же такие действия выглядят явно лишними, поэтому от них стоит застраховаться, введя одну дополнительную проверку в текст алгоритма.

Сортировка бинарными вставками

Слайд 36

© С.В.Кухта, 2009 Фрагмент программы: for i:= 2 to n do

© С.В.Кухта, 2009

Фрагмент программы:

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] 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;

Сортировка бинарными вставками

Слайд 37

© С.В.Кухта, 2009 Эффективность алгоритма. Теперь на каждом шаге выполняется не

© С.В.Кухта, 2009

Эффективность алгоритма.
Теперь на каждом шаге выполняется не N, а

log2N проверок, что уже значительно лучше (для примера, сравните 1000 и 10= log21024).
Следовательно, всего будет совершено N* log2N сравнений.
По количеству пересылок алгоритм по-прежнему имеет сложность О(N2).

Сортировка бинарными вставками

Слайд 38

© С.В.Кухта, 2009 3. Быстрые алгоритмы сортировки

© С.В.Кухта, 2009

3. Быстрые алгоритмы сортировки

Слайд 39

© С.В.Кухта, 2009 В отличие от простых сортировок, имеющих сложность O(N2),

© С.В.Кухта, 2009

В отличие от простых сортировок, имеющих сложность O(N2), к

улучшенным сортировкам относятся алгоритмы с общей сложностью O(N*logN).
Необходимо, однако, отметить, что на небольших наборах сортируемых данных (N<100) эффективность быстрых сортировок не столь очевидна:
выигрыш становится заметным только при больших N.
Следовательно, если необходимо отсортировать маленький набор данных, то выгоднее взять одну из простых сортировок.
Слайд 40

© С.В.Кухта, 2009 Эта сортировка базируется на уже известном нам алгоритме

© С.В.Кухта, 2009

Эта сортировка базируется на уже известном нам алгоритме простых

вставок.
Смысл ее состоит в раздельной сортировке методом простых вставок нескольких частей, на которые разбивается исходный массив.
Эти разбиения помогают сократить количество пересылок:
для того, чтобы освободить "правильное" место для очередного элемента, приходится уже сдвигать меньшее количество элементов.

Сортировка Шелла

Слайд 41

© С.В.Кухта, 2009 Сортировку Шелла придумал Дональд Л. Шелл. Ее необычность

© С.В.Кухта, 2009

Сортировку Шелла придумал Дональд Л. Шелл.
Ее необычность состоит

в том, что она рассматривает весь список как совокупность перемешанных подсписков.
На первом шаге эти подсписки представляют собой просто пары элементов.
На втором шаге в каждой группе по четыре элемента.
При повторении процесса число элементов в каждом подсписке увеличивается, а число подсписков, соответственно, падает.

Сортировка Шелла

Слайд 42

© С.В.Кухта, 2009 Сортирует элементы массива А[1..n] следующим образом: на первом

© С.В.Кухта, 2009

Сортирует элементы массива А[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 группах из восьми элементов и т.д.;
на последнем шаге упорядочиваются элементы сразу во всем массиве А.
На каждом шаге для упорядочивания элементов используется метод сортировки вставками.

Сортировка Шелла

Слайд 43

© С.В.Кухта, 2009 На рис. а изображены восемь подсписков, по два

© С.В.Кухта, 2009

На рис. а изображены восемь подсписков, по два элемента

в каждом, в которых
первый подсписок содержит первый и девятый элементы,
второй подсписок — второй и десятый элементы,
и так далее.

Сортировка Шелла

Слайд 44

© С.В.Кухта, 2009 На рис. б мы видим уже четыре подсписка

© С.В.Кухта, 2009

На рис. б мы видим уже четыре подсписка по

четыре элемента в каждом:
первый подсписок на этот раз содержит первый, пятый, девятый и тринадцатый элементы.
второй подсписок состоит из второго, шестого, десятого и четырнадцатого элементов.

Сортировка Шелла

Слайд 45

© С.В.Кухта, 2009 На рис. в показаны два подсписка, состоящие из

© С.В.Кухта, 2009

На рис. в показаны два подсписка, состоящие из элементов

с нечетными и четными номерами соответственно.

Сортировка Шелла

Слайд 46

© С.В.Кухта, 2009 На рис. г мы вновь возвращаемся к одному списку. Сортировка Шелла

© С.В.Кухта, 2009

На рис. г мы вновь возвращаемся к одному списку.

Сортировка

Шелла
Слайд 47

© С.В.Кухта, 2009 Фрагмент программы: incr:= n div 2; while incr>0

© С.В.Кухта, 2009

Фрагмент программы:

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;

Сортировка Шелла

Слайд 48

© С.В.Кухта, 2009 Полный анализ сортировки Шелла чрезвычайно сложен, и мы

© С.В.Кухта, 2009

Полный анализ сортировки Шелла чрезвычайно сложен, и мы не

собираемся на нем останавливаться.
Было доказано, что сложность этого алгоритма в наихудшем случае при выбранных нами значениях шага равна O(n3/2).
Полный анализ сортировки Шелла и влияния на сложность последовательности шагов можно найти в третьем томе книги Д. Кнута Искусство программирования, М., Мир.

Сортировка Шелла

Слайд 49

© С.В.Кухта, 2009 Попытаемся теперь усовершенствовать другой рассмотренный выше простой алгоритм:

© С.В.Кухта, 2009

Попытаемся теперь усовершенствовать другой рассмотренный выше простой алгоритм: сортировку

простым выбором.
Р.Флойд предложил перестроить линейный массив в пирамиду - своеобразное бинарное дерево, - а затем искать минимум только среди тех элементов, которые находятся непосредственно "под" текущим вставляемым.

Пирамидальная сортировка

Слайд 50

© С.В.Кухта, 2009 Для начала необходимо перестроить исходный массив так, чтобы

© С.В.Кухта, 2009

Для начала необходимо перестроить исходный массив так, чтобы он

превратился в пирамиду, где каждый элемент "опирается" на два меньших.
Этот процесс назвали просеиванием, потому что он очень напоминает процесс разделения некоторой смеси (камней, монет, т.п.) на фракции в соответствии с размерам частиц:
на нескольких грохотах последовательно задерживаются сначала крупные, а затем все более мелкие частицы.

Пирамидальная сортировка: просеивание

Слайд 51

© С.В.Кухта, 2009 Итак, будем рассматривать наш линейный массив как пирамидальную

© С.В.Кухта, 2009

Итак, будем рассматривать наш линейный массив как пирамидальную структуру:


Видно, что любой элемент a[i] (1<=i<=N div 2) "опирается" на элементы a[2*i] и a[2*i+1].
И в каждой такой тройке максимальный элемент должен находится "сверху".
Конечно, исходный массив может и не удовлетворять этому свойству, поэтому его потребуется немного перестроить.

Пирамидальная сортировка: просеивание

Слайд 52

© С.В.Кухта, 2009 Начнем процесс просеивания "снизу". Половина элементов (с ((N

© С.В.Кухта, 2009

Начнем процесс просеивания "снизу". Половина элементов (с ((N div

2)+1)-го по N-й) являются основанием пирамиды, их просеивать не нужно.
А для всех остальных элементов (двигаясь от конца массива к началу) проверяем тройки a[i] , a[2*i] и a[2*i+1] и перемещать максимум "наверх" - в элемент a[i]. При этом, если в результате одного перемещения нарушается пирамидальность в другой (ниже лежащей) тройке элементов, там снова необходимо "навести порядок" - и так до самого "низа" пирамиды.

Пирамидальная сортировка: просеивание

Слайд 53

© С.В.Кухта, 2009 Фрагмент программы алгоритма просеивания: for i:= (N div

© С.В.Кухта, 2009

Фрагмент программы алгоритма просеивания:

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] 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;

Пирамидальная сортировка: просеивание

Слайд 54

© С.В.Кухта, 2009 Пример результата просеивания Возьмем массив [1,7,5,4,9,8,12,11,2,10,3,6] (N =

© С.В.Кухта, 2009

Пример результата просеивания
Возьмем массив [1,7,5,4,9,8,12,11,2,10,3,6] (N = 12).
Его исходное

состояние таково (серым цветом выделено "основание" пирамиды, не требующее просеивания):

Пирамидальная сортировка

Пирамидальная сортировка: просеивание

Слайд 55

© С.В.Кухта, 2009 перестановка не требуется Пирамидальная сортировка: просеивание

© С.В.Кухта, 2009

перестановка не требуется

Пирамидальная сортировка: просеивание

Слайд 56

© С.В.Кухта, 2009 перестановка элементов 9 и 10 Пирамидальная сортировка: просеивание

© С.В.Кухта, 2009

перестановка элементов 9 и 10

Пирамидальная сортировка: просеивание

Слайд 57

© С.В.Кухта, 2009 перестановка элементов 4 и 11 Пирамидальная сортировка: просеивание

© С.В.Кухта, 2009

перестановка элементов 4 и 11

Пирамидальная сортировка: просеивание

Слайд 58

© С.В.Кухта, 2009 перестановка элементов 5 и 12 элемент 5 сыновей

© С.В.Кухта, 2009

перестановка элементов 5 и 12

элемент 5 сыновей не имеет,

проверка вниз не производится

Пирамидальная сортировка: просеивание

Слайд 59

© С.В.Кухта, 2009 перестановка элементов 7 и 11 производится проверка тройки

© С.В.Кухта, 2009

перестановка элементов 7 и 11

производится проверка тройки элементов 7,

4 и 2; перестановка не требуется

Пирамидальная сортировка: просеивание

Слайд 60

© С.В.Кухта, 2009 производится проверка тройки элементов 1, 8 и 5;

© С.В.Кухта, 2009

производится проверка тройки элементов 1, 8 и 5; требуется

перестановка 1 и 8

производится проверка пары элементов 1 и 6; требуется перестановка 1 и 6

перестановка элементов 1 и 12

Пирамидальная сортировка: просеивание

Слайд 61

© С.В.Кухта, 2009 Итак, мы превратили исходный массив в пирамиду: в

© С.В.Кухта, 2009

Итак, мы превратили исходный массив в пирамиду:
в любой тройке

a[i], a[2*i] и a[2*i+1] максимум находится "сверху".

Пирамидальная сортировка: просеивание

Слайд 62

© С.В.Кухта, 2009 Для того чтобы отсортировать массив методом Пирамиды, необходимо

© С.В.Кухта, 2009

Для того чтобы отсортировать массив методом Пирамиды, необходимо выполнить

такую последовательность действий:
0-й шаг: Превратить исходный массив в пирамиду (с помощью просеивания).
1-й шаг: Для N-1 элементов, начиная с последнего, производить следующие действия:
поменять местами очередной "рабочий" элемент с первым;
просеять (новый) первый элемент, не затрагивая, однако, уже отсортированный хвост последовательности (элементы с i-го по N-й).

Пирамидальная сортировка: алгоритм

Слайд 63

© С.В.Кухта, 2009 Часть программы, реализующая нулевой шаг алгоритма, приведена в

© С.В.Кухта, 2009

Часть программы, реализующая нулевой шаг алгоритма, приведена в пункте

"Просеивание", поэтому здесь приведена только реализацией основного шага 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] 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;

Пирамидальная сортировка

Слайд 64

© С.В.Кухта, 2009 Продолжим сортировку массива, для которого мы уже построили

© С.В.Кухта, 2009

Продолжим сортировку массива, для которого мы уже построили пирамиду:


[12, 11, 8, 7, 10, 6, 5, 4, 2, 9, 3, 1].
С целью экономии места не будем далее прорисовывать структуру пирамиды.
Подчеркивание будет отмечать элементы, участвовавшие в просеивании, а квадратными скобками – те элементы, которые участвуют в дальнейшей обработке.

Пирамидальная сортировка: пример

Слайд 65

© С.В.Кухта, 2009 1) Меняем местами a[1] и a[12]: [1, 11,

© С.В.Кухта, 2009

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;

Пирамидальная сортировка: пример

Слайд 66

© С.В.Кухта, 2009 5) Меняем местами a[1] и a[10]: [1, 9,

© С.В.Кухта, 2009

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;

Пирамидальная сортировка: пример

Слайд 67

© С.В.Кухта, 2009 5) Меняем местами a[1] и a[10]: [1, 9,

© С.В.Кухта, 2009

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;

Пирамидальная сортировка: пример

Слайд 68

© С.В.Кухта, 2009 9) Меняем местами a[1] и a[8]: [1, 7,

© С.В.Кухта, 2009

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;

Пирамидальная сортировка: пример

Слайд 69

© С.В.Кухта, 2009 13) Меняем местами a[1] и a[6]: [2, 4,

© С.В.Кухта, 2009

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;

Пирамидальная сортировка: пример

Слайд 70

© С.В.Кухта, 2009 19) Меняем местами a[1] и a[3]: [2, 1],

© С.В.Кухта, 2009

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) Просеивать ничего не нужно, сортировка закончена.

Пирамидальная сортировка: пример

Слайд 71

© С.В.Кухта, 2009 Эффективность алгоритма Пирамидальная сортировка хорошо работает с большими

© С.В.Кухта, 2009

Эффективность алгоритма
Пирамидальная сортировка хорошо работает с большими массивами,

однако на маленьких примерах (N<20) выгода от ее применения может быть не слишком очевидна.
В среднем этот алгоритм имеет сложность O(N*log N).

Пирамидальная сортировка

Слайд 72

© С.В.Кухта, 2009 «Быстрая сортировка» (Quick Sort) Идея – более эффективно

© С.В.Кухта, 2009

«Быстрая сортировка» (Quick Sort)

Идея – более эффективно переставлять элементы,

расположенные дальше друг от друга.

N div 2

2 шаг: переставить элементы так:
при сортировке элементы не покидают « свою область»!

1 шаг: выбрать некоторый элемент массива X

3 шаг: так же отсортировать две получившиеся области

Разделяй и властвуй (англ. divide and conquer)

Слайд 73

© С.В.Кухта, 2009 «Быстрая сортировка» (Quick Sort) Медиана – такое значение

© С.В.Кухта, 2009

«Быстрая сортировка» (Quick Sort)

Медиана – такое значение X, что

слева и справа от него в отсортированном массиве стоит одинаковое число элементов (для этого надо отсортировать массив…).

Разделение:
выбрать средний элемент массива (X=67)
установить L:=1, R:=N
увеличивая L, найти первый элемент A[L], который >= X (должен стоять справа)
уменьшая R, найти первый элемент A[R], который <= X (должен стоять слева)
если L<=R, поменять местами A[L] и A[R] и перейти к п. 3

Слайд 74

© С.В.Кухта, 2009 «Быстрая сортировка» (Quick Sort)

© С.В.Кухта, 2009

«Быстрая сортировка» (Quick Sort)

Слайд 75

© С.В.Кухта, 2009 «Быстрая сортировка» (Quick Sort) procedure QSort ( first,

© С.В.Кухта, 2009

«Быстрая сортировка» (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;

разделение

обмен

двигаемся дальше

сортируем две части

Слайд 76

© С.В.Кухта, 2009 «Быстрая сортировка» (Quick Sort) program qq; const N

© С.В.Кухта, 2009

«Быстрая сортировка» (Quick Sort)

program qq;
const N = 10;
var A:

array[1..N] of integer;
begin
{ заполнить массив }
{ вывести исходный массив на экран }
Qsort ( 1, N ); { сортировка }
{ вывести результат }
end.

procedure QSort ( first, last: integer);
...

Слайд 77

© С.В.Кухта, 2009 Количество перестановок (случайные данные)

© С.В.Кухта, 2009

Количество перестановок

(случайные данные)

Слайд 78

© С.В.Кухта, 2009 4. Поиск в массиве

© С.В.Кухта, 2009

4. Поиск в массиве

Слайд 79

© С.В.Кухта, 2009 Поиск в массиве Задача – найти в массиве

© С.В.Кухта, 2009

Поиск в массиве

Задача – найти в массиве элемент, равный

X, или установить, что его нет.
Решение: для произвольного массива: линейный поиск (перебор)
недостаток: низкая скорость
Как ускорить? – заранее подготовить массив для поиска
как именно подготовить?
как использовать «подготовленный массив»?
Слайд 80

© С.В.Кухта, 2009 Линейный поиск nX := 0; for i:=1 to

© С.В.Кухта, 2009

Линейный поиск

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;

Слайд 81

© С.В.Кухта, 2009 Двоичный поиск X = 7 X 8 4

© С.В.Кухта, 2009

Двоичный поиск

X = 7

X < 8

8

4

X > 4

6

X >

6

Выбрать средний элемент A[c] и сравнить с X.
Если X = A[c], нашли (выход).
Если X < A[c], искать дальше в первой половине.
Если X > A[c], искать дальше во второй половине.

Слайд 82

© С.В.Кухта, 2009 Двоичный поиск nX := 0; L := 1;

© С.В.Кухта, 2009

Двоичный поиск

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;

нашли

выйти из цикла

сдвигаем границы

- Предыдущая
Виталий агапов - копия
Следующая -
Истоки современной архитектуры

Похожие презентации

Презентация "Эмигранты и аборигены цифрового мира" - скачать презентации по Информатике
Организация сети передачи данных по энергосетям с применением PLC технологии
Подходы к измерению информации
Сжатие информации
Technical Notification HDV130 and HDV100 upgrade to Firmware V02.081
Польза и вред интернета для учащихся и дошкольников
Установка редактора Sublime Text3
Применение электронных ресурсов при проведении уроков информатики
Киберспорт в жизни школьников
Ввод–вывод с квитированием по прерыванию
Опыт внедрения подсистемы кадрового учета и расчета заработной платы в 1С:ERP Управление предприятием 2
Reveal the halloween picture (game)
Найти корни квадратного уравнения Ax2+Bx+C=0
Информатика
Початки алгоритмізації та процедурного програмування. Циклічні програми
Презентация "Повторение" - скачать презентации по Информатике
Базы данных. Лекция 7
История развития информационных технологий
Язык описания данных ORACLE. Типы данных ORACLE. Таблицы. Представления
Электронный сертификат – новый механизм обеспечения техническими средствами реабилитации
Коммерческое предложение по разработке корпоративного сайта для ООО Империя Строй
Схемы программ (часть 1)
Компьютерные коммуникации
Советы новичку: как пробиться в геймдев и пройти испытательный срок
Файл и файловая система. Решение задач
Александр Шаповал Microsoft
Ввод и обработка цифровой информации
История развития ЭВМ
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть