Презентация на тему Простые сортировки

N объектов a1, ... , аN:
переставить их

в такой последовательности аp1 , ..., apN ,
чтобы их ключи расположились в неубывающем порядке
kp1 < kp2 < ... < kpN.

условию, согласно которому записи с одинаковыми ключами остаются в

прежнем порядке:
kРi = kРj и i < j, то pi < pj

При устойчивой сортировке относительный порядок элементов с одинаковыми ключами не меняется.

внутреннюю сортировку массивов и
внешнюю — сортировку файлов.

Методы сортировки можно разбить на несколько основных классов в зависимости от лежащего в их основе приема сортировки:
включения;
выбора;
обмена;
подсчета;
разделения;
слияния.

две последовательности:
входную ai, ... , аN
и готовую

последовательность a1, ... , аi-1
элементы которой уже отсортированы.
В алгоритмах, основанных на методе включения, на каждом i-м шаге i-й элемент входной последовательности вставляется в подходящее место готовой последовательности.
Сортировка простыми включениями наиболее очевидна.
Пусть 2 < i < N, a1, ... , аi-1 уже отсортированы:
a1 ≤ а2 ≤ ... ≤ ai-1.
Будем сравнивать по очереди аi с ai-1, аi-2, ... до тех пор, пока не обнаружим, что элемент аi следует вставить между aj и aj+1 (0 ≤ j ≤ i − 1) элементами.
После этого или в процессе поиска подвинем записи aj+1, ..., ai-1 на одно место вправо и переместим запись аi в позицию j + 1.

из восьми ключей:
i = 1 40 | 51

8 38 90 14 2 63
i = 2 40 51 | 8 38 90 14 2 63
i = 3 8 40 51 | 38 90 14 2 63
i = 4 8 38 40 51 | 90 14 2 63
i = 5 8 38 40 51 90 | 14 2 63
i = 6 8 14 38 40 51 90 | 2 63
i = 7 2 8 14 38 40 51 90 | 63
i = 8 2 8 14 38 40 51 63 90 |

части. К сортированной части сначала относится только первый элемент.
 цикл

по i от 2 до N с шагом 1 выполнять
// i – номер первого элемента в несортированной части массива
x:= A[i];
j := i – 1;
// Все элементы из отсортированной части, большие,
// чем x, сдвинуть на одну позицию вправо:
пока j>0 и A[j]>x выполнять
A[j+1] := A[j];
j := j – 1;
конец пока
// Элемент x поставить на свое место по порядку:
A[j+1] := x;
конец цикла

Сi во внутреннем цикле равно i -1;
если предположить,

что все перестановки N ключей равновероятны, число сравнений в среднем равно i/2.
Для Mi, количества пересылок на i-м шаге,
максимальное Мi = Сi + 2.
Всего шагов N - 1.
Следовательно, количество сравнений и пересылок в худшем и лучшем случаях:

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

в котором на i-ом шаге выполняется ~ log2i сравнений.
Поэтому всего будет произведено ~ N⋅log2N сравнений.
Но количество пересылок в этом методе не изменится

идее многократного выбора.

На i-м шаге выбирается наименьший элемент

из входной последовательности ai, ..., an и меняется местами с ai-м.
Таким образом, после шага i на первом месте во входной последовательности будет находиться наименьший элемент.
Затем этот элемент перемещается из входной в готовую последовательность.

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

51 8 38 90 14 2 63.
На первом шаге

находим наименьший элемент 2, обмениваем его с первым элементом 40 и перемещаем в готовую последовательность:
2 ⎪ 51 8 38 90 14 40 63
2 8 ⎪ 51 38 90 14 40 63
2 8 14 ⎪ 38 90 51 40 63
2 8 14 38 ⎪ 90 51 40 63
2 8 14 38 40 ⎪ 51 90 63
2 8 14 38 40 51 ⎪ 90 63
2 8 14 38 40 51 63 ⎪ 90

включениями.

При сортировке простым выбором рассматриваются все элементы входной

последовательности и для фиксированного места из нее выбирается наименьший элемент.

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

части. Сначала весь массив — это несортированная часть.
цикл

по i от 1 до N–1 с шагом 1 выполнять
// i – номер первого элемента в несортированной части массива
r:= i;
// Найти минимальный элемент в несортированной части массива:
цикл по j от i+1 до N с шагом 1 выполнять
если А[j] < A[r] то r:= j;
конец цикла
// Найденный минимальный элемент поменять местами с
// первым элементом несортированной части:
если i ≠ r то Обмен (i, r);
// Он будет последним элементом новой сортированной
// части массива A.
конец цикла

от начального порядка
элементов.
На первом шаге первый элемент сравнивается

с остальными N - 1
элементами, на втором шаге число сравнений будет — N - 2 и т. д.

Поэтому число сравнений есть
С = (N – 1) + (N – 2) + ... + 1 = N * (N - 1)/2

Максимальное число пересылок Мmах = N -1 так как на каждом
проходе выполняется обмен найденного минимального элемента с i-м.

Вероятность того, что i-й элемент уже стоит на месте, невелика, поэтому средняя оценка М близка к максимальной.

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

включений, в то время как число перемещений, наоборот, минимально.

Если вспомнить, что сравниваются ключи позиций, а перемещаются записи целиком, то метод выбора, экономящий число перемещений может на практике оказаться предпочтительней.

и обмена пар соседних элементов.
На первом шаге сравним

последний и предпоследний элементы, если они не упорядочены, поменяем их местами.
Далее проделаем то же со вторым и третьим элементами от конца массива, третьим и четвертым и т. д. до первого и второго с начала массива.
При выполнении этой последовательности операций меньшие элементы в каждой паре продвинутся влево, наименьший займет первое место в массиве.
Повторим этот же процесс от N-го до 2-го элемента, потом от N-го до 3-го и т. д.

i-й проход по массиву приводит к «всплыванию» наименьшего элемента из входной последовательности на i-e место в готовую последовательность.

же последовательности, состоящей из восьми ключей:
i = 0 40

51 8 38 90 14 2 63
i = 1 2 40 51 8 38 90 14 63
i = 2 2 8 40 51 14 38 90 63
i = 3 2 8 14 40 51 38 63 90
i = 4 2 8 14 38 40 51 63 90
i = 5 2 8 14 38 40 51 63 90
i = 6 2 8 14 38 40 51 63 90
i = 7 2 8 14 38 40 51 63 90

N с шагом 1 выполнять
// проход от конца

массива к началу:
цикл по j от N до i с шагом -1 выполнять
// если два рядом стоящих элемента нарушают
// порядок по возрастанию, то их поменять местами.
если A[j] < A[j–1]
то Обмен(j, j–1);
конец цикла
конец цикла

равно N - i, что приводит к уже известному

выражению для С:

С = (N - 1) + (N - 2) + ... + 1 = N∙(N - 1)/2

Минимальное количество пересылок Mmin= 0,
если массив уже упорядочен,
максимальное Мтах = С, если массив упорядочен по убыванию.

проходы сортировки простым обменом работают «вхолостую», так как элементы

уже упорядочены.
Один из способов улучшения алгоритма сортировки пузырьком состоит в том, чтобы запомнить, производился ли на очередном проходе какой-либо обмен.
Если ни одного обмена не было, то алгоритм может закончить работу.
2) Асимметрия метода: один неправильно расположенный «пузырек» на «тяжелом» конце почти отсортированного массива «всплывет» на место за один проход:
8 14 38 40 51 63 90 2

Неправильно расположенный «камень» на «легком» конце будет «опускаться» на правильное место только только по одному шажку на каждом проходе:
90 2 8 14 40 51 63

значение, если во время прохода по массиву были обмены

двух рядом стоящих элементов, left – левая граница несортированной части массива, а right – ее правая граница.
left := 1; right := N;
F := истина;
пока F выполнять
F:= ложь;
i:= left;
//Проход по массиву от начала к концу:
пока i < right выполнять
если A[i] > A[i + 1] то
// переставить два рядом стоящих элемента, нарушающие порядок:
начало
Обмен (i, i+1);
F := истина;
конец
i := i + 1;
конец пока
// Сдвинуть правую границу влево на одну позицию:
right := right – 1;

предыдущего прохода,
если F
то // совершить проход по массиву

от конца к началу:
начало
F := ложь;
i:= right;
пока i > left выполнять
если A[i] < A[i – 1]
то // переставить рядом стоящие элементы,
// нарушающие порядок:
начало
Обмен (i, i–1);
F := истина;
конец
i := i – 1;
конец пока
конец
// Сдвинуть левую границу вправо на одну позицию:
left := left + 1;
конец пока // Цикл повторять до тех пор, пока F не
//останется равной значению ложь.
 

сравнений пропорционально
N2 - N.
Но все предложенные улучшения

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

Сортировка обменом и ее улучшенная сортировка хуже, чем сортировка включениями и выбором.

Шейкер-сортировку выгодно использовать тогда, когда массив
почти упорядочен.

сравнивается со всеми остальными и подсчитывается количество элементов, которые

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