Сортировка простым обменом (метод пузырька)

В этой сортировки обмен 2-х эл-тов является основной характеристикой процесса. Алгоритм основан на сравнии двух соседних эле-тов.

const n=20; type item= integer; index=0..n; var a:array [1..n] of item; I,j:index; x:item; begin for i:=2 to n do for j:=n downto i do

if a[j-1]>a[j] then begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; end; end;

Число сравнений и пересылок равняется N².

Сортировку простым обменом (метод пузырька) можно улучшить, т. к. при СПО последние проходы не влияют на порядок Эл-тов. т. е. можно запомнить производится ли на данном этапе обмен и если нет то это означает, что алгоритм может закончить работу. Процесс улучшения можно продолжить если запоминать не только сам факт обмена, но и место (индекс) последнего обмена, т. к. ясно, что все пары соседних эл-тов с индексами < этого индекса уже рассортированы в нужном порядке. Поэтому следующие проходы можно заканчивать на этом индексе вместо того, чтобы двигаться до установленной заранее нижней границы.

Шейкер сортировка.

Если менять направление следующих друг за другом проходов в сортировки простым обменом (метод пузырька), то получается алгоритм Шейкер сортировки.

const n=20; var a:array [1..n] of integer; i,j,l,k,x,r:integer; begin l:=2; r:=n; k:=n; repeat for j:=r downto l do if a[j-1]>a[j] then begin

x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; k:=j; end; l:=k+1; for j:=l to r do if a[j-1]>a[j] then begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; k:=j; end;

r:=k-1 until l>r; end;

Число сравнений и пересылок равняется N².

Алгоритм Шейкер сортировки можно использовать в тех случаях, когда Эл-ты почти упорядочены.

Не нашли, что искали? Воспользуйтесь поиском: