begin
if a[j-l]>a[j] then
begin
x:=a[j-l];
a[j-l] :=a[j] ;
a[j] :=x;
k:=j
end;
end;
R:=k-l;
until L>R;
Пузырьковая сортировка является не самой эффективной, особенно для последо вательностей, у которых «всплывающие» элементы находятся в крайней правой стороне. В улучшенной (быстрой) пузырьковой сортировке предлагается производить перестановки на большие расстояния, причем двигаться с двух сторон. Идея алгорит ма заключается в сравнении элементов, из которых один берется слева (i = 1), другой — справа (j = n). Если a[i] <= a[j] , то устанавливают j = j — 1 и проводят следующее сравнение. Далее уменьшают j до тех пор, пока a[i]>a[j]. В противном случае меняем их местами и устанавливаем i=i+1 . Увеличение i продолжаем до тех пор, пока не получим a[i] > a[j]. После следующего обмена опять уменьшаем j. Чередуя уменьше ние j и увеличение i, продолжаем этот процесс с обоих концов до тех пор, пока не станет i = j. После этого этапа возникает ситуация, когда первый элемент занимает предназначенное ему место, слева от него младшие элементы, а справа — старшие.
Далее подобную процедуру можно применить к левой и правой частям массива и т.д. Очевидно, что характер алгоритма рекурсивный. Для запоминания ведущих левого и правого элементов в программе необходимо использовать стек.
(*улучшенная сортировка разделением — быстрая сортировка с рекурсией*)
const N=8;
type item= integer;
var a: array[l..n] of item;
i: integer;
procedure sort (L,R: integer) ;
var i, j: integer;
x, y: item;
begin
i:=L;
j:=R;
x:=a[(L+R) div 2 ] ;
repeat
while a[i]
Похожие записи
- No related posts found
