Сортировка с помощью разделения.
Улучшенный метод основанный на методе пузырька. Автор Хоар. Сортировка Quick Sort. Алгоритм исходит из соображений, что для достижения наилучшей эффективности сначала лучше произвести перестановки на большие расстояния.
i<=j
Идея
алгоритма: выберем наугад элемент,
назовём его х и будем рассматривать
массив слева пока не найдем элемент
больше х. затем будем рассматривать
массив справа, пока не найдет элемент
меньше х. Поменяем их местами. Продолжим
процесс просмотра и обмена, пока оба
просмотра не встретятся где-то в середине
массива. В результате массив будет
разбит на 2 части. Слева окажутся все
элементы ai
меньше х, а справа все элементы ai
больше х.
I=1,
j=n
-
Случайно
выбранный х
aiaj
+
просмотр
слева пока не найду ai<x
Repeat
i=i+1
j=J-1
i>j
Просмотр
справа, пока aj>x разделение
завершено
- +
Необходимо применить этот процесс, и к получившимся 2-м частям до тех пор, пока каждая из частей не будет состоять из 1-го элемента.
По структуре алгоритма напрашивается применить рекурсивное обращение программы самой к себе при сужении границ массива до единичного расстояния между ними.
Procedure QuickSort (var a:array of integer);
Procedure Soft (L,R:integer);
i:=L;
j:=R
L<j
Soft
(L,i)
X=a[(L+R)div2]
i<R
Попарное
разделение массива на две части
Soft
(i,R)
repeat
End
Sort
i>j
-
Begin {Quick Soft}
Soft(0,n);
End;
Медианы и порядковые статистики
: порядковые статические множества состоят из n элементов : элементы в порядке возрастания
Медианы неформально означает середину такого множества.
Если n-нечетное, то медиана единственна и ее индекс i:=(n+1)div 2. Если n-четное, то нижняя медиана iн=n/2, iв=n/2+1
Обычно выражение медиана относится к нижней Медиане. Задача состоит в выборе I порядковой статистики в множестве из n чисел .
An 1<=i<=N вх.
Вых: x A превышает по величине (i-1) других элементов массива А.
Задачу выбора можно решить за время пропорциональное О(n*lgn)
Выполняется сортировка и берем элемент с номером i.
Существует более быстрые алгоритмы. Алгоритм выбора с линейным временем работы в нужный случай. Алгоритм будет находить нужный элемент путем разбития вх массива.
Все n элементы Вх массива разбираются на [n/5] и одна группа будет содержать остаток n mod 5
Метод вставок сортирует каждую группу и в каждой группе выбранную медиану
Путем рекурсивного использование??? этой процедуры выдает медиана Х множества из медианы найденных на 2 шаге. Если четное количество медиан, то х нечетное.
Использование QuickSort
Медианой из n элементов называется элемент значения, которого <=половины элементов или => другой половины n элементов.
16 12 99 95 18 87 10: Сортируем и ищем.
Использует алгоритм Хоара. L=1; R=n; В результате получаем индексы i и j
Ah<x, Ɐh<i
Ah>x, Ɐh>j
i<j
Каждый раз работает один из трех случаев
Разделяем элемент х слишком мал и граница принадлежит [i;R] и разделяем этот промежуток
Граница слишком велика и разделяется от L до j [L;j]
Процесс повторяется до тех пор, пока не получим 3 случай
L=1 R=n
j<R
Procedure Find (k:integer)
-
L<R
L=i
Окончание поиска
while +
j>k
x=ak
+
разделяем aL ÷ aR
end
R=i
