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

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

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

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

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

Пример.

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