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

Находим в массиве наибольший элемент и помещаем его в буфер
Сдвигаем правую

Находим в массиве второй по величине элемент и помещаем его в

К-ый элемент

Далее процесс повторяется до расположения к-го по величине элемента на

В массиве задаем опорный элемент “P1”
Просматриваем массив слева направо, располагая элементы

В оставшейся части массива задаем опорный элемент “P2”
Просматриваем массив слева направо,

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

Алгоритмы сортировки

Есть последовательность , ...
и функция сравнения, которая на

Возможна ситуация, когда элементы состоят из нескольких полей:
Если значение функции сравнения

Критерии эффективности работы алгоритмов

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

Устойчивость - устойчивая сортировка не меняет взаимного расположения равных элементов.
Расположение дополнительных

Естественность поведения - эффективность метода при обработке уже отсортированных, или частично

Сравнение времени сортировок

коричневая линия: сортировка пузырьком;
синяя линия: шейкер-сортировка;
розовая линия:

Быстрая сортировка

Метод основан на подходе "разделяй-и-властвуй". Общая схема такова:
из массива

Разделение массива
На входе массив a[0]...a[N] и опорный элемент p, по которому

Исходный массив
Первый обмен
Второй обмен

6

5

3

9

1

8

4

5

7

4

3

7

1

9

2

4

3

6

5

3

9

1

8

4

5

7

4

3

7

1

9

2

4

3

6

5

3

9

1

8

4

9

7

4

3

7

1

5

2

4

3

Третий обмен
Четвертый обмен
Конечный результат

6

5

3

9

1

8

7

9

7

4

3

4

1

5

2

4

3

1

5

3

9

6

8

7

9

7

4

3

4

1

5

2

4

3

1

5

3

6

9

8

7

9

7

4

3

4

1

5

2

4

3

Конечный результат
Разделённые массивы
Для разделённых массивов процедура повторяется

1

5

3

6

9

8

7

9

7

4

3

4

1

5

2

4

3

1

5

3

6

9

8

7

9

7

4

3

4

1

5

2

4

3

Первый массив

Второй массив

Общее быстродействие метода - хорошее.
Метод неустойчив.
Поведение довольно естественно, если

Сортировка слиянием

Сортировка слиянием также построена на принципе "разделяй-и-властвуй", однако реализует его

Рекурсивный алгоритм обходит получившееся дерево слияния в прямом порядке. Каждый уровень

Исходный массив
Первый проход – пары
Второй проход – четвёрки

3

7

2

8

4

6

1

5

3

7

8

2

4

6

1

5

Третий проход – восьмёрки
Процесс слияния в буфер

2

3

7

8

1

4

5

6

1

4

5

6

2

3

7

8