Алгоритмы сортировки массивов: метод выбора, метод вставки, метод быстрой сортировки Хоара, метод Шелла. Поиск в массиве (стр. 2 )

Идея данной сортировки:

Пусть имеется исходный массив A[1..n].

i	1	2	3	4	5	6	7
A[I]	5	11	1	3	4	12	7

Массив разбивается относительно медианного элемента ((1+n) div 2), значение данного элемента обозначим через х (его называют "барьерным").        I:=(1+7) div 2=4;        x:=a[4]:=3;

L¬	I:=1	2	3	4  ↓X	5	6	7	↵R
A[I]	5	11	1	3	4	12	7

→ i                                                                                                 ← j

Обозначим начало фрагмента, то есть левую границу массива через L (left), конец фрагмента через R (right). В исходном массиве l=1, r=n. ⇒ L:=1; R:=7.

Двигаемся по счетчику i: a[1]<x. Если да, то переходим к п.4 (кандидат для обмена a[1]:=5) Если нет, то наращиваем i на (+1)

Двигаемся по j справа в поисках элемента для обмена: a[n]>x. В нашем случае в правой части все элементы тяжелее Х, ⇒, кандидат для обмена само Х.

Если элемент найден (он может быть =х), то меняем их местами. Поэтому меняем местами a[1] и a[4]. При этом i=i+1, j=j+1.

Имеем,

I:=	1	2	3	4	5	6	7
A[I]	3	11	1	5	4	12	7

⇒ I = I + 1=2; j = j – 1=3. Меняем местами a[2] и a[3].

Имеем,.

I:=	1	2	3	4	5	6	7
A[I]	3	1	11	5	4	12	7

⇒ I = I + 1=3; j = j – 1=2. Таким образом повторяем выполнение п. 1-4 до того, как i>j, что является признаком упорядоченности.

Имеем, ⇒ I = I + 1; j = j – 1.

Легкая	Тяжелая часть
I:=	1	2	3	4	5	6	7
A[I]	3	11	1	5	4	12	7

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

Следовательно нужно повторить алгоритм для этих частей поочередно до тех пор, пока в каждой из частей массива не останется по одному элементу, то есть пока не будет отсортирован весь массив..

Конечность глубины рекурсии гарантируется тем, что длина сортируемого участка на каждом уровне рекурсии уменьшается хотя бы на 1 .

РЕАЛИЗАЦИЯ АЛГОРИТМА:

(*------Алгоритм быстрой сортировки массива---*)

Алгоритм SORT

Вход b : mass;

выход a : mass);

Тип  index=0..n;

Алгоритм QuickSort( l, r :I ndex);

Переменные

i, j: index;

       x,        w: float;

Начало

i := l;

j := r;

x := a[(i+j) DIV 2];

Повторять

Нц

Пока a[i]<x делать

Нц

i := i+1;

Кц;

Пока x<a[j] делать

Нц

       j := j-1;

Кц;

Если i<=j

То

Начало

       w := a[i];

       a[i] := a[j];

       a[j] :=        w;

       i := i+1;

       j := j-1;

Все {если};

Кц

До i>j;

Если l<j то QuickSort(l, j);

Если i<r то QuickSort(i, r)

Конец

Начало

QuickSort(1,n);

Конец;

Быстрая сортировка Хоара. Нерекурсивный алгоритм

Идея сортировки:

Пусть имеется исходный массив A[1..n].

i	1	2	3	4	5	6	7
A[I]	5	11	1	3	4	12	7

Массив разбивается относительно медианного элемента ((1+n) div 2), значение данного элемента обозначим через х (его называют "барьерным").        I:=(1+7) div 2=4;        x:=a[4]:=3;

L¬	I:=1	2	3	4  ↓X	5	6	7	↵R
A[I]	5	11	1	3	4	12	7

→ i                                                                                                 ← j

Обозначим начало фрагмента, то есть левую границу массива через L (left), конец фрагмента через R (right). В исходном массиве l=1, r=n. ⇒ L:=1; R:=7.

Двигаемся по счетчику i: a[1]<x. Если да, то переходим к п.4 (кандидат для обмена a[1]:=5) Если нет, то наращиваем i на (+1)

Двигаемся по j справа в поисках элемента для обмена: a[n]>x. В нашем случае в правой части все элементы тяжелее Х, ⇒, кандидат для обмена само Х.

Если элемент найден (он может быть =х), то меняем их местами. Поэтому меняем местами a[1] и a[4]. При этом i=i+1, j=j+1.

Имеем,

I:=	1	2	3	4	5	6	7
A[I]	3	11	1	5	4	12	7

⇒ I = I + 1=2; j = j – 1=3. Меняем местами a[2] и a[3].

Имеем,.

I:=	1	2	3	4	5	6	7
A[I]	3	1	11	5	4	12	7

⇒ I = I + 1=3; j = j – 1=2. Таким образом повторяем выполнение п. 1-4 до того, как i>j, что является признаком упорядоченности.

Имеем, ⇒ I = I + 1; j = j – 1.

Легкая	Тяжелая часть
I:=	1	2	3	4	5	6	7
A[I]	3	11	1	5	4	12	7

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

Следовательно, алгоритм должен повторяться. Причем части должны упорядочиваться поочередно. Стоит вопрос, какую из частей сортировать в первую очередь.

У Вирта на этот счет существует несколько идей. Мы используем следующую:

Помещаем границы массивов в стеки. L – в левый, R – в правый. L_St, R_St –границы необработанной части массивов.

L_St	R_St
Исходный массив	3	7

L        R
I:=	1	2	3	4	5	6	7
A[I]	3	11	1	5	4	12	7
Легкая часть j	i

Сортируем легкую часть, R:=J

L:=1	R:=2
3	1
I:=1	J:=R

Медианный элемент (1+2) div 2=1;

1	3
J →	←i

I<J – Это признак упорядоченности.

Теперь извлекаем значения L_St, R_St из стека. Продолжаем сортировку

РЕАЛИЗАЦИЯ АЛГОРИТМА

Обратите внимание на то, что в программе использован тип Record

Алг NonRecursivQuickSort Вход b:massiv; Выход  a:massiv; Локальные переменные X:* - значение  медианного элемента w : *- вспомогательная переменная для обмена; i, j: index - счетчики L, R: index; границы легклй и тяжелой части сортируемого массива s: 0..M; счетчик эл-тов эмулируемого стека L_St, R_St: massiv1; эмулируемые стеки для хранения значений индексов границ легкой и тяжелой части сортируемого массива

Инициализация стека 1 - Внешний цикл Передаем границы фрагмента, который был разделен на легкую и тяжелую части Выбор из стека последнего запроса 2 - Внутренний цикл Разделение a[L],...,a[R] 3 - Сам процесс разбивки Ищем позицию элемента, который тяжелее или равен элементу Х, который н. переместить в правую часть элемента Х, который н. переместить в левую часть i<= j?- то есть может быть ситуация, когда элемент д. меняться сам  с собой {3} То есть мы разбили наш фрагмент на легкую и тяжелую части Если i<R то  Заполняем  стек R := j Теперь L и ограничивают левую часть. Подвинули R на новую границу { 2}                До L>=R; {1}        До s=0;

Начало s:=1; L_St[s]:=1; R_st[s]:=n; {1} Повторять  {1 - Внешний цикл}        Нц        L:=L_St[s];        R:=R_st[s];        s:=s-1; {2}        Повторять  {2 - Внутренний цикл}        Нц                        i:=L;                j:=R;                x:=a[((i+j) div 2)]; {3}                Повторять  {3- Внутренний цикл}                Нц                                Пока a[i]<x делать                        Нц                                i:=i+1;                        Кц                        Пока a[j]>x делать                        Нц                                j:=j-1;                        Кц                        Если i<=j то                        начало                                y:=a[i];                                a[i]:=a[j];                                a[j]:=y;                                i:=i+1;                                j:=j-1;                        все {если} {3}                Кц                До i>j;                Если i<R то                начало                        s:=s+1;                        L_St[s]:=i;                        R_st[s]:=R;                все; {если}                R:=j;        Кц {2}        До L>=R Кц {1}До S=0; Конец;

Метод Шелла

Метод Шелла предложен автором Donald Lewis Shеll в 1959 г. Основная идея этого алгоритма заключается в том, чтобы в начале устранить массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы. Как видно, интервал между сравниваемыми элементами (gap) постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми).