4-§ Birlashtirib saralash algoritmlari Merge sort algoritmi. Birlashtirib saralash (Merge sort)

//toʻgʻri holatini koʻrsatadi 
 
 
for (int j = low; j <= high - 1; j++) 
 
{ 
 
 
//Agar joriy element tayanchdan kichik boʻlsa 
 
 
if (arr[j] < pivot) 
 
 
{ 
 
 
 
i++; 
 
 
 
swap(&arr[i], &arr[j]); 
 
 
} 
 
} 
 
swap(&arr[i + 1], &arr[high]); 
 
return (i + 1); 
} 
 
void quickSort(int arr[], int low, int high) 
{ 
 
if (low < high) 

---

76 
 
{ 
 
 
 
int pi = partition(arr, low, high); 
 
 
 
 
quickSort(arr, low, pi - 1); 
 
 
quickSort(arr, pi + 1, high); 
 
} 
} 
 
void printArray(int arr[], int size) 
{ 
 
int i; 
 
for (i = 0; i < size; i++) 
 
 
cout << arr[i] << " "; 
 
cout << endl; 
} 
 
 
int main() 
{ 
 
int arr[] = {10, 7, 8, 9, 1, 5}; 
 
int n = sizeof(arr) / sizeof(arr[0]); 
 
quickSort(arr, 0, n - 1); 
 
cout << "Saralangan massiv: \n"; 
 
printArray(arr, n); 
 
return 0; 
} 
QuickSort algoritmi tahlili. Massivni „tayanch― elementiga 
nisbatan ikki qismga boʻlish jarayoni O(log
2
n) vaqtni oladi. Bir xil 
rekursiya darajasi bajariladigan barcha boʻlinish amallari hajmi doimiy 
boʻlgan boshlangʻich massivning turli qismlarini qayta ishlagani uchun, 
har bir rekursiya darajasida jami O (n) amallar ham talab qilinadi. 
Shuning uchun algoritmning umumiy murakkabligi faqat boʻlinishlar 
soni, ya‘ni rekursiya darajasi bilan belgilanadi. Rekursiyaning darajsi, 

---

77 
oʻz navbatida, kirishlarning kombinatsiyasiga va ―tayanch element‖ 
qanday aniqlanishiga bogʻliq. 
Eng yaxshi holat. Eng yaxshi holatda har bir boʻlinish paytida 
massiv ikkita bir xil (+/- bitta element) qismlarga boʻlinadi, shuning 
uchun qayta ishlangan ichki massivlarning oʻlchamlari 1 ga yetadigan 
maksimal rekursiya darajasi log
2
n boʻladi. Natijada, quicksort 
tomonidan taqqoslash soni O(nlog
2
(n)) algoritmining umumiy 
murakkabligini 
beradigan 
rekursiv ifodasining 
qiymatiga teng boʻladi. 
Oʻrtacha holat. Kirish ma‘lumotlarini tasodifiy taqsimlash uchun 
oʻrtacha murakkablik faqat ehtimollik bilan baholanishi mumkin. 
Avvalo shuni ta‘kidlash kerakki, aslida, ―tayanch‖ elementi har 
safar massivni ikkita teng qismga ajratishi shart emas. Masalan, agar har 
bir bosqichda dastlabki massivning 75% va 25% uzunlikdagi 
massivlarga boʻlinish boʻlsa, rekursiya darajasi
ga teng boʻladi va 
O (nlogn) murakkablikni beradi. Umuman olganda, ―tayanch‖ 
elementning chap va oʻng tomonlari orasidagi har qanday aniq nisbatlar 
uchun algoritmning murakkabligi bir xil boʻladi, faqat har xil 
konstantalar mavjud. 
Yomon holat. Eng yomon holatda har bir ―tayanch‖ 1 va n-1 
oʻlchamdagi ikkita kichik massivni beradi, ya‘ni har bir rekursiv 
chaqiriq uchun kattaroq massiv oldingi vaqtga nisbatan 1 ta qisqa 
boʻladi. Agar har bir ishlov berilgan elementlarning eng kichigi yoki eng 
kattasi mos yozuvlar sifatida tanlansa, bu sodir boʻlishi mumkin.
Bunday holda, n-1 ―boʻlinish‖ amallar talab qilinadi va umumiy 
ishlash muddati ∑
ta operatsiyani tashkil qiladi, 
ya‘ni saralash kvadratik vaqt ichida amalga oshiriladi. Ammo 
almashtirishlar soni va shunga koʻra ish vaqti uning eng katta kamchiligi 
emas. Bundan ham yomoni, bu holda algoritmni bajarish paytida 
rekursiya darajasi n ga yetadi. 
Mavzu yuzasidan savollar: 
1. Saralash algoritmlari va ularning tahlili haqida gapiring