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

 
pi = partition(arr, low, high); 
 
quickSort(arr, low, pi - 1); // Before pi 
quickSort(arr, pi + 1, high); // After pi 
} 

---

73 
} 
 
“Boʻlib tashlash” algoritmning psevdokodi. Ushbu funksiya 
soʻnggi elementni ―tayanch‖ sifatida qabul qiladi, ―tayanch‖ elementni 
tartiblangan qatorga toʻgʻri holatiga qoʻyadi va kichikroq (burilishdan 
kichikroq) burilishning chap tomoniga va barcha katta elementlarni 
―tayanch element‖ ning oʻng tomoniga joylashtiradi
partition (arr[], low, high) 
{ 
// pivot (Element toʻgʻri joyga joylashtiriladi) 
pivot = arr[high];

i = (low - 1) // Kichikroq element koʻrsatkichi va tayanch
//toʻgʻri holatini koʻrsatadi
for (j = low; j <= high- 1; j++) 
{ 
// Agar joriy element “tayanch” elementdan kichikroq boʻlsa 
if (arr[j] < pivot) 
{ 
i++; // kichik elementning oʻsish koʻrsatkichi 
swap arr[i] and arr[j] 
} 
} 
swap arr[i + 1] and arr[high]) 
return (i + 1) 
} 
―Boʻlib tashlash‖ algoritmining ishlashini quyidagi misolda qarab 
chiqish mumkin: 
arr[] = {10, 80, 30, 90, 40, 50, 70} 
Indekslar: 0 1 2 3 4 5 6
low = 0, high = 6, pivot = arr[h] = 70 
Kichik element indeksini initsializatsiya qilish, i = -1 

---

74 
j = low to high-1 
j = 0 : arr[j] <= pivot, shart bajarilsa, i++ va swap(arr[i], arr[j]) 
i = 0  
arr[] = {10, 80, 30, 90, 40, 50, 70} //Massivda oʻzgarish boʻlmaydi
j = 1 : arr[j] > pivot, bajarilsa, hech nima oʻzgarmaydi 
// i va arr [] da oʻzgarish yoʻq