Челночная сортировка

К(2) К(4) К(6) К(8)

K(3) K(7)

K(1) K(5) K(9)

12 1 7

K(2) K(6)

5 9

4 8

K(4) K(8)

3 6

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

набор данных будет иметь следующий вид:

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8) K(9)

1 5 4 3 7 9 8 6 12.

Затем шаг J сокращается вдвое и становится равным 2. Образуются

следующие 2 последовательности элементов, отстоящих друг от друга

на 2 элемента

K(1) K(3) K(5) K(7) K(9)

1 4 7 8 12

5 3 9 6

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

набор данных будет иметь следующий вид:

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8) K(9)

1 3 4 5 7 6 8 9 12.

Затем снова J сокращается вдвое и становится равным 1. При

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

После этого:

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8) K(9)

1 3 4 5 6 7 8 9 12

Челночная сортировка работает точно так же, как стандартный обмен,

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

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

сравнение. Монеты

Пример.

5, 4, 1, 2, 3

J=1, I=1;

4 5 1 2 3

J=2, I=2;

4 1 5 2 3

I=1;

1 4 5 2 3

J=3, I=3;

1 4 2 5 3

I=2;

1 2 4 5 3

I=1;

1 2 4 5 3

J=4, I=4;

1 2 4 3 5

I=3;

1 2 3 4 5

I=2;

1, 2, 3, 4, 5

I=1;

1, 2, 3, 4, 5

Челночная сортировка характеризуется следующими параметрами.

Качественные:

1. Простота программирования.

2. Требуется наличие всех записей до начала сортировки.

3. Время на сортировку зависит от степени упорядоченности исходного набора данных

Количественные:

1. Число сравнений постоянно

N*(N-1) /2.

2. Число обменов:

минимальное - 0;

максимальное - N*(N-1)/2.

3. Дополнительный объем памяти требуется для запоминания одной записи при реализации операции обмена.

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

Пример.

5, 4, 1, 2, 3

J=1, I=1;

FLAG=0;

4 5 1 2 3

FLAG=1; I=0;

J=2, I=2;

FLAG=0;

4 1 5 2 3

FLAG=1; I=1;

1 4 5 2 3

FLAG=1; I=0;

J=3, I=3;

FLAG=0;

1 4 2 5 3

FLAG=1; I=2;

1 2 4 5 3

FLAG=1; I=1;

FLAG=0;

J=4, I=4;

FLAG=0;

1 2 4 3 5

FLAG=1; I=3;

1 2 3 4 5

FLAG=1; I=2;

FLAG=0;

1, 2, 3, 4, 5

FLAG позволяет сократить число сравнений.

Число сравнений:

Мин (N-1)

Макс N*(N-1)/2

Число обменов:

Мин 0

Макс N*(N-1)/2