Ma’lumotlar tuzilmasi va algoritmlar

Algoritm samaradorligi:
taqqoslashlar soni M = ,
almashtirishlar soni C_max = 3 .


Saralashning yaxshilangan usullari


Quiksort – tez saralash usuli


G’oyasi: Bu usul almashtirish usulidagi saralashga tegishli bo’lib uning asosini kalitlarni tanlangan kalitga nisbatan ajratish tashkil qiladi.

6 dan chap tomonda kalitlari kichik, o’ng tomonda esa kalitlari 6 dan katta bo’lgan elementlar joylashadi (yuqoridagi chizma).

procedure Sort (L, R: integer);
begin
i := L;
j := r;
x := a[(L + r) div 2];
repeat
while a[i] < x do
i := i + 1;
while a[j] > x do
j := j - 1;
if i <= j then
begin
y := a[i];
a[i] := a[j];
a[j] := y;
i := i + 1;
j := j - 1
end;
until i > j;
if L < j then sort (L, j);
if i < r then sort (i, r);
end;


procedure QuickSort;
begin
sort (1, n);
end;
Algoritm samaradorlig:
O(n log n) – eng samarali usul.

Shell saralashi (qisqarib boruvchi qadamlar orqali saralash)

To’g’ri qo’shish usulini 1959 yilda D. Shell tomonidan mukammallashtirish taklif qilingan. Quyidagi chizmada ushbu usul tasvirlangan:

Boshida bir biridan 4 qadamda joylashgan elementlar o’zaro guruhlanib saralash amalga oshiriladi. Bunday jarayon to’rtlik saralash deb ataladi. Birinchi o’tishdan keyin elementlar qayta guruhlanib, endi har ikki qadamdagi elementlar taqqoslanadi. Bu esa ikkilik saralash deb nomlanadi. Va nihoyat, uchinchi o’tishda oddiy yoki yakkalik saralashi amalga oshiriladi.
Bir qarashda mazkur usul bilan saralash amalga oshirilganda saralash jarayoni kamayish o’rniga ortib boradigandek tuyulsada, elementlarni o’rin almashtirishlar nisbatan kam amalga oshiriladi.
Ko’rinib turibdiki, bu usul natijasida tartiblangan massiv hosil bo’lib, har bir o’tishdan keyin saralashlar kamayib boradi. Eng yomon holatda oxirgi ishni yakkalik saralash amalga oshiradi.
Baryer usulidan foydalanilganda har bir saralash o’zining baryeriga ega bo’lishi lozim hamda dastur uning joyini aniqlashi uchun uni iloji boricha osonlashtirish lozim. Shuning uchun massivni [-h1..N] gacha kengaytirish lozim bo’ladi.
h[1..t] – qadamlar o’lchami massivi
a[1..n] - saralanayotgan massiv
k – saralash qadami
x – qo’shilayotgan element qiymati