Xreferat.com » Рефераты по информатике и программированию » Быстрые алгоритмы сортировки

Быстрые алгоритмы сортировки

самі дії, але в параметрах процедури ми змінюємо ліву границю. Те саме відбувається, коли відсортована права частина масиву.

По суті цей алгоритм працює на основі алгоритму сортування обмінами, але цей алгоритм вважається швидким, оскільки перегляд послідовності відбувається у двох напрямках одночасно. Реалізовано ж цей алгоритм за допомогою оператору “if”, який відповідає за порівняння елементів, та пересилань.


Procedure _Qsort (var a:mas; low, hi: byte);

Var i,j:byte;

begin

if hi> low then

begin i:= low;

j:= hi;

x:= a[i];

While i< j do

if a[i+1]<=x then

begin

a[i]:= a[i+1];

a[i+1]:=x;

i:= i+1;

end

else

begin

if a[j]<=x then

begin

y:=a[j];

a[j]:=a[i+1];

a[i+1]:=y;

end;

j:=j-1

end;

-Qsort (a, low, i-1);

-Qsort (a, i+1, hi);

end;

end;


Процедура Mergesort виконує сортування двох масивів “злиттям”. Тобто, спочатку перший масив сортується за допомогою процедури Qsort і другий масив сортується за допомогою цієї ж процедури. Потім два, вже відсортованих масиви з’єднуються в один. А саме, за допомогою оператору “if” ми порівнюємо перший елемент одного і перший елемент другого масивів. Якщо один з них менший, то ми відсилаємо його в третій масив, а індикатор пересуваємо на наступний елемент і знов порівнюємо їх. Знову менший з двох елементів пересилаємо в третій масив, а індикатор пересуваємо. Також ми передбачили варіант, коли елементи, що порівнюються – однакові. Тоді в третій масив по-черзі записуються обидва елементи, а індикатори зміщуються на наступні елементи в обох масивах. Якщо один з масивів виявився меншим за кількістю елементів ніж інший, то решта елементів довшого масиву просто пересилається до третього масиву в тій самій послідовності (адже вихідні масиви вже відсортовані раніше процедурою Qsort). Таким чином, в результаті ми отримуємо третій масив з впорядкованими елементами.


Procedure Mergesort;

Var i, j, k: byte;

Begin

i:=1;

j:=1;

for k:=1 to n_c do c[k]:=0;

k:=1;

While ( i<= n_a ) or ( j<=n_b ) do

if i= n_a+1 then

begin

c[k]:=b[j];

k:=k+1;

j:= j+1;

end

else

if i= n_b+1 then

begin

c[k]:=a[i];

k:= k+1;

i:=i+1 ;

end

else

if a[i]= b[j] then

begin

c[k]:=b[j];

c[k+1]:= a[i];

k:=k+2;

i:=i+1;

j:=j+1

end

else

if a[i] > b[j] then

begin

c[k]:= b[j];

k:= k+1;

j:= j+1;

end

else

begin

c[k]:= a[i];

k:= k+1;

i:= i+1;

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: