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

информацию. Целые числа могут быть со знаком и без него,

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

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

слово можно разделить по буквам, число - по цифрам...
До сортировки необходимо знать два параметра: k и m, где
k - количество разрядов в самом длинном ключе
m - разрядность данных: количество возможных значений разряда ключа
При сортировки чисел m = 10 (0.1 . . 9) , k = наибольшему количеству цифр в числах )
Эти параметры нельзя изменять в процессе работы алгоритма.

моменту разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n].
На

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

в случае, когда
1. Hайден элемент,

меньший a[i],
2. Достигнуто начало последовательности.
Дополнительная память не используется.
Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет досортирован очень быстро.
Метод устойчив.

массив


Объединение парами


Сортировка внутри пар вставками
8
14
9
4
1
8
6
12
3
9
3
18
11
10
13
5
8
14
9
4
1
8
6
12
3
9
3
18
11
10
13
5




8
14
9
4
1
8
6
12
3
9
3
18
11
10
13
5

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

левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от первого и заканчивая (n-1)-м.
На i-м шаге выбираем наименьший из элементов a[i] ... a[n] и меняем его местами с a[i].

÷ a[n].


Меняем местами a[1] и a[m1].
4
9
7
6
2
3
4
9
7
6
2
3
4
9
7
6
2
3

a[2] и a[m2].
2
9
7
6
4
3
2
9
7
6
4
3
2
9
7
6
4
3

a[3] и a[m3].
2
3
7
6
4
9
2
3
7
6
4
9
2
3
7
6
4
9

a[4] и a[m4]. (в данном случае элемент не смещается)
2
3
4
6
7
9
2
3
4
6
7
9
2
3
4
6
7
9

упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n]

оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.
Для нахождения наименьшего элемента из n рассматриваемых алгоритм совершает n сравнений. С учетом того, что количество рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций:
n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n2+n )
Таким образом, так как число обменов всегда будет меньше числа сравнений, время сортировки растет квадратично относительно количества элементов.

Метод неустойчив.
Если входная последовательность почти упорядочена, то сравнений будет столько

же, значит алгоритм ведет себя неестественно.

к последнему.
Идея метода: шаг сортировки состоит в проходе снизу вверх

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

2 6 2

7 2 9 2 4

4

9

7

6

2

3

4

9

7

2

6

3

4

9

2

7

6

3

4

2

9

7

6

3

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

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

i=1 i=2

i=3 i=4 i=5

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

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

пузырьком устойчива, однако шейкер-сортировка утрачивает это качество.

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

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

i=1 i=2 i=3

i=4 i=5