|
8-Mavzu: Birlashtirib saralash algoritmlari. Samarali saralash algoritmlari. Birlashtirib saralashni rekursiv va rekursiv bo'lmagan algoritmlari
|
| bet | 3/4 | | Sana | 30.05.2024 | | Hajmi | 42,15 Kb. | | #257330 |
Bog'liq 8-Mavzu{
pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // Before pi quickSort(arr, pi + 1, high); // After pi
}
}
“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
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
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
8-Mavzu: Birlashtirib saralash algoritmlari. Samarali saralash algoritmlari. Birlashtirib saralashni rekursiv va rekursiv bo'lmagan algoritmlari
|
