Ma’lumotlar tuzilmasi Data structures 4-ma’ruza: Saralash usullari

Bu algoritm quyidagi prinsip asosida ishlaydi:

1. Berilgan massiv ikkita massivga ajratib olinadi.

2. Qismmassivlarning har biri alohida saralanadi.

3. Saralangan massivlar qayta qo’shiladi.

Izoh: ajratilgan massivning birinchi qismidagi barcha elementlar ikkinchi qismdagi barcha elementlardan kichik bo’lish sharti qo’llaniladi.

Algoritm sxemasi

• A(6,5,1,9,3,4,8,7,2) massiv berilgan.

Ushbu massiv elementlarini o’rtacha qiymatining butun qismiga nisbatan ikkiga ajratamiz:

• А1(5,1,3,4,2) – birinchi qismmassiv.
• А2(6,9,8,7) – ikkinchi qismmassiv.

Har birini alohida saralaymiz:

• А1(1,2,3,4,5) –birinchi qismmassiv.
• А2(6,7,8,9) – ikkinchi qismmassiv.

A=A1+A2 yangi saralangan massiv hosil qilinadi

Aralashtirib saralash algoritmi

viod Sliv(int p,q)

{

int r,i,j,k

r=(p+q) div 2;

i=p; j=r+1;

for (k=p; k<= q; k++)

if (i<=r) and ((j>q) or (a[i]

{

b[k]=a[i]; i=i+1;

} else

{

b[k]=a[j]; j=j+1;

}

for (k=p; k<= q; k++)
a[k]=b[k];
}
void Sort(int p,q)
{
if p{
Sort(p,(p+q) div 2);
Sort((p+q) div 2 + 1,q);
Sliv(p,q);
}
}
p,q – сараланадиган қисмларнинг боши ва охири

Algoritmning samaradorligi

• Ushbu saralash algoritmida elementlarning tuzilmada joylashishiga nisbatan, algoritmning ishlash vaqti e’tiborga olinishi kerak. Shunki bunda oldin saralangan qism massivlar hosil qilinayotgani uchun ko’p vaqt sarflanadi.
• Demak, tez saralash algoritmi massiv elementlari tasodifiy qonuniyat asosida berilgan bo’lsa O(nlog2n) kabi vaqt sarflaydi.

Алгоритмнинг самарадорлиги

N та элементдан иборат массивни саралаш учун T(n) вақт сарфланган бўлсин, у ҳолда аралаштирилган массивларни саралашга кетган вақтни қуйидагича ифодалаш мумкин: