Tekshirdi: Bo’riev Yusuf Toshkent 2022 Tezkor saralash (Quick sort) algoritmi Ishdan maqsad

Muhammad Al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universiteti

Ma’lumotlar tuzilmasi va algoritmlar
3-amaliy ishi
Bajardi: SWD002-2 guruhining talabasi
Qilichbayev Sirojiddin


Tekshirdi: Bo’riev Yusuf

Toshkent 2022


Tezkor saralash (Quick sort) algoritmi
Ishdan maqsad: Quick sort algoritmini to’liq o’rganib chiqish va C++ dasturlash tilida amaliy masalalar yechib ko’rish.
Nazariy ma’lumotlar
Merge sort singari, Quick sort ham divide va conquer algoritmidir. U elementni pivot sifatida tanlaydi va berilgan massivni tanlangan pivot atrofida ajratadi. QuickSort-ning turli xil yo'llar bilan pivotni tanlaydigan ko'plab turli versiyalari mavjud:

• 
  Har doim birinchi elementni pivot sifatida tanlang.
  
• 
  Har doim oxirgi elementni pivot sifatida tanlang (quyida amalga oshiriladi)
  
• 
  Pivot sifatida tasodifiy elementni tanlang.
  
• 
  Pivot sifatida medianni tanlang.
  

QuickSort-dagi asosiy jarayon - bu partition() (bo’lak) funksiyasi. Bo’limlarning maqsadi - massiv va massivning x elementi pivot sifatida berilgan, x ni tartiblangan massivda o'zining to'g'ri joyiga qo'yish va barcha kichikroq (x dan kichik) elementlarni x dan oldin qo'yish va barcha katta (x dan kattaroq) elementlarni qo'yishdir x dan keyin. Bularning barchasi chiziqli vaqtda amalga oshirilishi kerak.
Partition algoritmi
Bunda massiv elementlarini 0 – dan oxirgi indeksgacha aylanib chiqamiz. Agar elementimiz pivot dan kichik bo’lsa uni dastlabki elementlar bilan almashtirib chiqamiz. Ya’ni masalan, 0, 1 – elementlarimiz pivotdan katta va 2-elementimiz pivotdan kichik bo’lib qolsa, uni 0-indeksdagi element bilan almashtiramiz, keying pivotdan kichig elementimiz 5-indeksda bo’lsa, endi uni 2-indeksdagi element bilan almashtiramiz… Bu funksiyamiz rekursiv bo’lgani uchun unga massiv, chap va o’ng indekslarini berib yuboramiz. Shuningdek siklimiz aylanib bo’lgandan keyin oxirgi elementimiz bilan navbati kelib qolgan indeksdagi element bilan almashtiramiz.

int partition(int a[], int l, int r){
int pivot = a[r];
int i = l - 1;
for (int j = l; j < r; j++) {
if (a[j] <= pivot){
i++;
my_swap(&a[i], &a[j]);
}
}
my_swap(&a[i+1], &a[r]);
return i+1;
}

Agar partition funksiyasini C++ dasturlash tilida quyidagicha yozishimiz mumkin:
Shu bilan yordamichi partition() funksiyamiz tugaydi va asosiy sortlash funksiyamizni yozsak bo’ladi.