{ 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