1.3 Описание схемы алгоритма

Алгоритмы сортировки очень сильно зависят от структуры данных.. В данной работе рассматривается сортировка массивов. Тип данных «массив» удобен тем, что хранится во внутренней памяти и имеет случайный доступ к элементам, то есть более быстрый, чем у последовательности. Поэтому массивы целесообразно использовать для хранения небольших, часто используемых множеств

Из выше сказанного следует, что в процессе работы потребуются следующие переменные:

n – количество элементов массива;

A – сортируемый массив;

j – переменная;

x – i-й ключ (переносимый элемент);

r – номер последнего обмена при просмотре входной последовательности слева-направо.

l - номер последнего обмена при просмотре входной последовательности справа -

налево.

Все переменные целого типа.

Описание схемы алгоритма. Блок-схема данного алгоритма изображена на рис. 1 в Приложении.

Алгоритм работает следующим образом. Сначала вводятся исходные данные: длина массива и его элементы (блок 1, 2) , затем организуется цикл по всей длине массива, во время которого (блоки 3 -7) и проводится сравнение элементов а[j-1]>a[j] и их обмен при проходе справа-налево . Номер последнего обмена l запоминается. Далее организуется цикл, в котором проводится проверка условия а[j-1]>a[j] при проходе массива слева-направо (блоки 8 - 12).

1.4 Контрольный пример

Рассмотрим пример работы алгоритма сортировки Шейкер.

Задан массив A, состоящий из 8 элементов: 44, 55, 12, 42, 94, 18, 6, 67.

Шаг 1. l = 2, r = 8

Таблица 2

l	2	3	3	4	4
r	8	8	7	7	4
Направление	↑	↓	↑	↓	↑
j=1	44	6	6	6	6
j = 2	55	44	44	12	12
j= 3	12	55	12	44	18
j = 4	42	12	42	18	42
j = 5	94	42	55	42	44
j = 6	18	94	18	55	55
j = 7	6	18	67	67	67
j = 8	67	67	94	94	94

j = r =8

1. A[7]<A[8] , j = j -1 =7

2. A[6]>A[7], x=18, A[6]=6, A[7]=x=18 ; j=6

3. A[5]>A[6], A[5] =6, A[6] = 94

4. A[4]>A[5], A[4] =6, A[5] =42

5. A[3]>A[4], A[3] =6, A[4] =12

6. A[2]>A[3], A[2] =6, A[3] = 55

7. A[1]>A[2], A[1] =6, A[2] = 44

8. l=3.

Шаг 2. A[7]<A[8] , j = j -1 =7

1) A[1]>A[2]; j=6

2) A[2]>A[3], A[1] =, A[2] = 44, j= 4

3) A[3]>A[4], A[2] =6, A[3] =12, j=5

4) A[4]>A[5], A[3] =6, A[4] =12, j=6

5) A[5]>A[6], j =7

6) A[6]>A[7], A[5] =6, A[6] = 18 , j=8

7) r =7.

Шаг 3.

1. A[7]>А[8] , j = j -1 =7

2. A[6]>A[7], x=18, A[6]=6, A[7]=x=18 ; j=6

3. A[5]>A[6], A[5] =6, A[6] = 94; j=5

4. A[4]>A[5], A[4] =6, A[5] =42; j=4

5. A[3]>A[4], A[3] =6, A[4] =12; j=3

6. A[2]>A[3], A[2] =6, A[3] = 55; j=2

7. A[1]>A[2], A[1] =6, A[2] = 44; j=1

8. l=3.

Шаг 4.

1) A[1]>A[2], x=18, A[6]=6, A[7]=x=18 ; j=6

2) A[2]>A[3], A[1] =, A[2] = 94, j= 4

3) A[3]>A[4], A[2] =6, A[3] =42, j=5

4) A[4]>A[5], A[3] =6, A[4] =12, j=6

5) A[5]>A[6], j =7

6) A[6]>A[7], A[5] =6, A[6] = 44 , j=8 ,

7) r =7. → конец алгоритма.

Таким образом, мы получили исходный массив, отсортированный методом Шейкер:

6, 12, 18, 42, 44, 55, 67, 94.