Saralashning qat’iy va yaxshilangan usullar
Bu algoritm ham “Bo’lib tashla va hukmronlik qil” metodiga asoslanadi. Algoritmning g’oyasi: - Massivda bo’luvchi element X tanlanadi.
- Elementlarni shunday joylashtiramizki, dastlab X dan kichik yoki teng bo’lgan elementlar joylashsin, keyin undan katta bo’lgan elementlar joylashsin.
- Natijada chap tamonda barcha kichik elementlar, o’ng tamonda esa barcha katta sonlar joylashib qoladi. Bu qismlarning endi bir-biriga aloqasi yo’q. Keyin ularni alohida saralaymiz.
- Bu jarayon rekursiv jarayon bo’ladi.
[L, R] saralanishi kerak bo’lgan kesma. - [L, R] saralanishi kerak bo’lgan kesma.
- m = (L+R) / 2 – bu kesmanig o’rtasi.
- X=a[m] - bo’luvchi element. Ya’ni uni o’rtasidan tanlab olamiz.
Keyin quyidagi amallarni bajaramiz: - Chap tamondan X dan katta yoki teng bo’lgan birinchi elementni topamiz.
- O’ng tamondan X dan katta bo’lmagan birinchi elementni topamiz.
- Ikkalasining qiymatini almashtiramiz.
Natijada chap tamondan bitta katta element o’ng tamonga o’tadi, ong tamondan bitta kichik element chapga o’tadi. - Natijada chap tamondan bitta katta element o’ng tamonga o’tadi, ong tamondan bitta kichik element chapga o’tadi.
- 1) Bo’luvchi element x=6. Chap tamondan birinchi 6 dan katta yoki teng bo’lgan son 10, chap tamondan 6 dan kichik yoki teng bo’lgan element 3.
- Ularning o’rnini almashtiramiz.
2) Endi chap tamondan birinchi 6 dan katta yoki teng bo’lgan son 9, chap tamondan 6 dan kichik yoki teng bo’lgan son 2. 2) Endi chap tamondan birinchi 6 dan katta yoki teng bo’lgan son 9, chap tamondan 6 dan kichik yoki teng bo’lgan son 2. Ularning o’rnini almashtiramiz. 3) Chap tamondan birinchi 6 dan katta yoki teng bo’lgan son 10, chap tamondan 6 dan kichik yoki teng bo’lgan son 1. 3) Chap tamondan birinchi 6 dan katta yoki teng bo’lgan son 10, chap tamondan 6 dan kichik yoki teng bo’lgan son 1. Ularning o’rnini almashtiramiz. 4) Chap tamondan birinchi 6 dan katta yoki teng bo’lgan son 7, chap tamondan 6 dan kichik yoki teng bo’lgan son 6. 4) Chap tamondan birinchi 6 dan katta yoki teng bo’lgan son 7, chap tamondan 6 dan kichik yoki teng bo’lgan son 6. Ularning o’rnini almashtiramiz. Natijada j > i bo’lib qoldi. Bu iteratsiyani shu yerda to’xtatamiz va keyingi bosqichga o’tamiz: Natijada j > i bo’lib qoldi. Bu iteratsiyani shu yerda to’xtatamiz va keyingi bosqichga o’tamiz:
Berilgan interval ikkita qismga ajralib qoldi: [L, j] va [i,R] intervallar. Bu qismlarning bir-biriga aloqasi yo’q, chunki o’ng tamondagi barcha sonlar chap tamondagi barcha sonlardan katta(aniqrog’i kichik emas). Endi bu qismlarni huddi shunday jarayon bo’yicha saralashni davom ettirish mumkin. Buni amalaga oshirish uchun eng yaxshi usul bu rekursiv usuldan foydalanish. [L, R] ni saralash kerak bo’lgan masala undan kichikroq ikkita masalaga [L, j] va [i,R] intervallarni saralashga keltirildi. Bu esa bo’lib tashla va hukmronlik qil metodi deb nomlanadi.
Quick sort algoritmining qo’llanilishi Quick sort algoritmining faqatgina saralash uchun emas boshqa bir narsani hisoblash uchun ham qo’llaniladi. Quick sort(Tezkor saralash) algoritmining ajoyib qo’llanilishi bu massivdagi k-tartibli qiy-matni topish, ya’ni massiv saralangan vaqtda k-o’rinda turadigan elementning qiymatini topish. Agar avval massivni to’liq saralab keyin k-indeksdagi qiymatini chiqarsak u holda ishlash vaqtu n∙log(n) bo’ladi. Lekin quick sort orqali u O(n) vaqtda topiladi. n=105 bo’lgan paytda n∙log(n) = 1 661 000 bo’ladi. Quick sort
static void sort(int l, int r, int[] a) {
int m = (l + r) / 2;
int x = a[m];
int i = l; //0
int j = r; //6
while(i <= j) {
while (a[i] < x) i ++;
while (a[j] > x) j --;
if (i <= j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
i ++;
j --;
}
}
if(l < j) sort(l, j, a); if(i < r) sort(i, r, a);
}
Do'stlaringiz bilan baham: |
