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

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

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

Рассмотрим действия на i-м шаге алгоритма. Последовательность к этому моменту

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

0

1

4

3

2

7

9

0

1

4

3

2

7

9

0

1

2

3

4

7

9

0

1

2

3

4

7

9

0

1

3

2

4

7

9

0

1

3

2

4

7

9

сравнение

сравнение

сравнение

перемещение

перемещение

завершение шага

В процессе вставки "просеиваем" элемент a[i] к началу массива, останавливаясь в

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

Сортировка Шелла является модификацией алгоритма сортировки простыми вставками.
Исходный массив
Объединение

Объединение «четвёрками»

5

11

3

4

1

8

3

12

6

9

9

18

14

10

13

8

Сортировка внутри «четвёрок» вставками

5

11

3

4

1

8

3

12

6

9

9

18

14

10

13

8

Объединение «восьмерками»
Сортировка внутри «восьмерок» вставками
Объединение заключительное

3

1

5

12

10

6

3

4

8

9

9

18

11

14

13

8

3

1

5

12

10

6

3

4

8

9

9

18

11

14

13

8

3

4

5

10

11

6

3

1

8

9

9

14

13

18

12

8

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

3

4

5

10

11

6

3

1

8

9

9

14

13

18

12

8

3

4

5

10

11

6

3

1

8

9

9

14

13

18

12

8

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

Отсортированная последовательность создается путем присоединения к ней одного элемента за

Шаг-1 (Исходная последовательность )
Нахождение минимального a[m1] элемента из последовательности a[1] ÷

Шаг-2
Нахождение минимального a[m2] элемента из последовательности a[2] ÷ a[n].
Меняем местами a[2]

Шаг-3
Нахождение минимального a[m3] элемента из последовательности a[3] ÷ a[n].
Меняем местами a[3]

Шаг-4
Нахождение минимального a[m4] элемента из последовательности a[4] ÷ a[n].
Меняем местами a[4]

Вне зависимости от номера текущего шага i, последовательность a[1]...a[i] является упорядоченной.

Алгоритм не использует дополнительной памяти: все операции происходят "на месте".
Метод

  Сортировка пузырьком

Расположим массив сверху вниз, от нулевого элемента - к

Нулевой проход
Нет
обмена 2 6 2 7 2 9 2

После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент -

2

4

9

7

6

3

2

3

4

9

7

6

2

3

4

9

7

6

2

3

4

6

9

7

2

3

4

6

7

9

Дополнительная памятьне требуется.
Поведение усовершенствованного (но не начального) метода довольно естественное,

Шейкер-сортировка

Улучшение алгоритма можно получить из следующего наблюдения. Легкий пузырек снизу

2

4

9

7

6

3

9

3

6

7

4

2

Номер
прохода i=0 i=1 i=2 i=3 i=4 i=5