j = 2 : arr[j] <= pivot, shart bajarilsa i++ va swap(arr[i], arr[j])
i = 1
arr[] = {10, 30, 80, 90, 40, 50, 70} // 80 va 30 almashdi
j = 3 : arr[j] > pivot, shart bajarilsa, hech nima oʻzgarmaydi
// No change in i and arr[]
j = 4 : arr[j] <= pivot, shart bajarilsa i++ va swap(arr[i], arr[j])
i = 2
arr[] = {10, 30, 40, 90, 80, 50, 70} // 80 va 40 almashadi
j = 5 : arr[j] <= pivot, shart bajarilsa i++ va swap(arr[i], arr[j])
i = 3
arr[] = {10, 30, 40, 50, 80, 90, 70} // 90 va 50 almashadi
Soʻnggi natija
arr[i+1] va arr[high]
arr[] = {10, 30, 40, 50, 70, 90, 80} // 80 va 70 almashtiriladi
―Tayanch element‖ hisoblanuvchi 70 ham oʻz oʻrnida. Undan kichik
elementdan boshida, kattalari esa undan tepada
Quick sort algoritmning umumiy dasturi (C++)
#include
using namespace std;
75
// Ikki elementni almashtirish uchun yordamchi funksiya
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
/*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
*/
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // tayanch element
int i = (low - 1); // Kichikroq element koʻrsatkichi va tayanch
Dostları ilə paylaş: |
