Большие списки

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








1


11
13
12
112
111
122
121
132
131

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



Наибольший элемент из буфера

перемещаем в конец массива

в буфер


Сдвигаем правую часть массива на одну ячейку влево (кроме

последнего элемента)



Второй по величине элемент из буфера перемещаем в конец массива на освободившееся место

на нужном месте








К-ый элемент

располагая элементы меньшие P1 слева от него, а большие элементы

- справа от него


Исключаем из рассмотрения левую часть массива

P1

К-ый

P1

К-ый

P1

К-ый

Э-ты

Э-ты>P1

слева направо, располагая элементы меньшие P2 слева от него, а

большие элементы - справа от него


Исключаем из рассмотрения правую часть массива

P2

К-ый

Э-ты

Э-ты>P2

элемент Pi располагается на К-ой позиции.
Процесс сокращения интервала идет до

логического конца – остается подинтервал из двух элементов, один из которых располагается на К-ой позиции.

и функция сравнения, которая

на любых двух элементах последовательности принимает одно из трех значений: меньше, больше или равно.
Задача сортировки состоит в перестановке членов последовательности таким образом, чтобы выполнялось условие:
для всех i от 0 до n.

сравнения зависит только от поля x , то x называют

ключом, по которому производится сортировка.
На практике, в качестве x часто выступает число, а поле y хранит какие-либо данные, никак не влияющие на работу алгоритма.

x

y

алгоритма.
Память - ряд алгоритмов требует выделения дополнительной памяти под временное

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

Расположение дополнительных полей "a", "b", "c" осталось прежним


Взаимное расположение

равных элементов с ключом 1 и дополнительными полями "a", "b", "c" изменилось

частично отсортированных данных.
Алгоритм ведет себя естественно, если учитывает эту

характеристику входной последовательности.

синяя линия: шейкер-сортировка;
розовая линия: сортировка выбором;
желтая линия: сортировка

вставками;
голубая линия: сортировка вставками со сторожевым элементом;
фиолетовая линия: сортировка Шелла.

массива выбирается некоторый опорный элемент a[i],
запускается процедура разделения массива,

которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] - вправо,
теперь массив состоит из двух подмножеств, причем левое меньше (либо равно) правого,


для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.

которому будет производиться разделение.
Введем два указателя: i и j.

В начале алгоритма они указывают, соответственно, на левый и правый конец последовательности.
Будем двигать указатель i с шагом в 1 элемент по направлению к концу массива, пока не будет найден элемент a[i] >= p. Затем аналогичным образом начнем двигать указатель j от конца массива к началу, пока не будет найден a[j] <= p.
Далее, если i <= j, меняем a[i] и a[j] местами и продолжаем двигать i, j по тем же правилам...
Повторяем шаг 3, пока i <= j.

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

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

его несколько по-другому, нежели быстрая сортировка.
Вместо разделения по опорному

элементу массив просто делится пополам.

уровень представляет собой проход сортировки слияния - операцию, полностью переписывающую

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

метода (которой нет у быстрой сортировки).
Сортировка слиянием является одним из

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