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

Saralashning yaxshilangan usullari

• Tez saralash algoritmi;
• Aralashtirib saralash algoritmi;

Tez saralash algoritmi

• Bu algoritm – bo’laklash usuli deb yuritiladi. 1962-yilda Charlz Xoar tomonidan taklif etilgan.
• Bu usul “bo’laklarga bo’l va hukmronlik qil” g’oyasiga asoslangan.
• Bu algoritmning asosiy g’oyasi almashtirish (pufak) usulidagi saralash algoritmiga mos keladi, ya’ni tanlab olingan kalitli elementga nisbatan kichik yoki teng elementlar ikki tomonga ajratib olinadi.

Algoritmning umumiy sxemasi

• Tuzilmadan aniq qiymatga ega biror p element tanlab olish;
• Ushbu elementga nisbatan chap tomonga “kichik yoki teng”, o’ng tomonga esa “katta yoki teng” elementlarni ajratib olish;
• Natijada ikkita “kichiklar” va “kattalar” qismto’plami hosil bo’ladi;
• Agar hosil qilingan qismto’plamlar 2 tadan ortiq elementlarga ega bo’lsa, u holda ushbu jarayon har bir qismto’plam uchun takrorlanadi.

Тез саралаш алгоритми (С++)

#include

#include

int array[100000];

void tezsaralash (long h,long l)

{ long i,j; int p, temp;

i=l; j=h;

p=array[(l+h)/2];

do

{

while (array[i]

while (array[j]>p) j--;

if (i<=j)

{ temp=array[i];

array[i]=array[j];

array[j]=temp;

i++; j--;

} }

while (i<=j);
if(j>l) tezsaralash(j,l);
if(h>i) tezsaralash(h,i);
}
main()
{
int size; int i;
cin>>size;
for (i=0; icin>>array[i];
tezsaralash(size-1,0);
for(i=0; icout<getch();
return 0;
}

Aralashtirib saralash usuli

Bu saralash usulining asosiy g’oyasi, ikkita alohida saralangan massiv yordamida, ularni aralashtirib yuborish orqali yangi saralangan massiv hosil qilishdan iborat.