Quick Sort (Sürətli Sıralama)

Quick Sort

Quick Sort, massivdən bir "dayaq" (pivot) elementi seçmək və digər elementləri bu dayağa görə — ondan kiçik və ya böyük olmalarından asılı olaraq — iki alt massivə bölmək (partitioning) prinsipi ilə işləyən "böl və idarə et" (divide-and-conquer) tipli sıralama alqoritmidir. Daha sonra bu alt massivlər rekursiv olaraq sıralanır.

Addımlar

1. Dayaq Elementinin Seçilməsi (Select Pivot): Massivdən bir pivot (dayaq) elementi seçin. Pivot olaraq massivin ilk elementini, son elementini, orta elementini və ya hər hansı təsadüfi bir elementi seçmək olar.

2. Parçalama (Partition): Pivot ilə müqayisə apararaq massivi yenidən nizamlayın. Pivotdan kiçik olan bütün elementlər ondan əvvəl, böyük olan elementlər isə ondan sonra yerləşdirilir. Bu addımdan sonra pivot özünün son sıralanmış mövqeyində olur.

3. Rekursiv Sıralama (Recursive Sort): Yuxarıdakı addımları iki alt massivə (pivotdan kiçik və böyük olan elementlər hissəsinə) rekursiv olaraq tətbiq edin.

Bu məntiqin izahı:

• Pivotun rolu: Pivot massivi iki qrupa bölən "sərhəd" rolunu oynayır.

• Bölmə mexanizmi: Hər rekursiv addımda ən azı bir element (seçilmiş pivot) öz qəti yerini tapır.

• Səmərəlilik: Pivot düzgün seçildikdə (məsələn, median dəyər), alqoritm massivi hər dəfə tən yarıya bölərək çox sürətlə işləyir.

C++ Tətbiqi

Rekursiv quickSort metodunu yaradın. Bu metod tam ədədlərdən ibarət massiv, həmçinin aşağı (low) və yuxarı (high) indeksləri təmsil edən iki tam ədəd qəbul edir. Metod geriyə heç bir dəyər qaytarmamalıdır. low indeksi high indeksindən kiçik olduğu müddətcə, partition metodunu çağırmaqla parçalama indeksini (partition index) tapın. Daha sonra sol hissə üçün, ardınca isə sağ hissə üçün yenidən quickSort metodunu çağırın.

static void quickSort(int arr[], int low, int high) {
    // Baza halı: Əgər 'low' 'high'-dan kiçikdirsə, proses davam edir
    if (low < high) {
        // pivotIndex - pivot elementinin sıralanmış massivdəki qəti yeridir
        int pivotIndex = partition(arr, low, high);

        // Pivotdan əvvəlki elementləri rekursiv olaraq sıralayırıq
        quickSort(arr, low, pivotIndex - 1);

        // Pivotdan sonrakı elementləri rekursiv olaraq sıralayırıq
        quickSort(arr, pivotIndex + 1, high);
    }
}

partition Metodunun Təyin Edilməsi

Növbəti addım olaraq, partition (parçalama) metodunu təyin etməliyik. Bu metod tam ədədlərdən ibarət bir massiv, həmçinin aşağı (low) və yuxarı (high) indeksləri təmsil edən iki tam ədəd qəbul edir. Metod geriyə bir tam ədəd (pivotun indeksi) qaytarmalıdır. Pivot elementini massivin sonuncu elementi olaraq təyin edin. i dəyişənini yaradın və onun dəyərini low - 1 olaraq təyin edin. j dövr dəyişəni low-dan başlayan və j dəyəri high-dan kiçik olduğu müddətcə davam edən bir for dövrü yaradın.

static int partition(int arr[], int low, int high) {
    // Pivot olaraq massivin sonuncu elementini seçirik
    int pivot = arr[high]; 
    
    // Daha kiçik elementin indeksini təyin edirik
    int i = low - 1; 

    for (int j = low; j < high; j++) {
        // Burada pivot ilə müqayisə aparılacaq
    }
    
    // Funksiyanın sonunda pivotun yekun indeksi qaytarılmalıdır
}

swap Metodunun Yaradılması

partition (parçalama) metoduna davam etməzdən əvvəl, massivdəki iki dəyərin yerini dəyişdirən swap metodunu yaradacağıq. Proses boyu bir neçə dəfə yerdəyişmə aparacağımız üçün bu məntiqi ayrıca bir metoda yerləşdirmək məqsədəuyğundur. Metod tam ədədlərdən ibarət bir massiv və yerləri dəyişdiriləcək iki tam ədəd (indekslər) qəbul edir. Metod geriyə heç nə qaytarmır.

static void swap(int arr[], int i, int j) {
    // i-ci elementin dəyərini müvəqqəti olaraq temp-də saxlayırıq
    int temp = arr[i];
    
    // j-ci elementin dəyərini i-ci mövqeyə yazırıq
    arr[i] = arr[j];
    
    // temp-də saxladığımız ilkin dəyəri j-ci mövqeyə yazırıq
    arr[j] = temp;
}

partition Metoduna Qayıdış

partition metoduna geri dönək. for dövrünün daxilində, j indeksindəki elementin pivotdan kiçik olub-olmadığını yoxlayın. Əgər belədirsə, i indeksini bir vahid artırın və yeni yaratdığımız swap metodundan istifadə edərək arr[i] və arr[j] dəyərlərinin yerini dəyişdirin.

static int partition(int arr[], int low, int high) {
    // Pivot olaraq sonuncu elementi götürürük
    int pivot = arr[high];
    
    // Kiçik elementlərin indeksini izləmək üçün
    int i = low - 1;

    for (int j = low; j < high; j++) {
        // Əgər cari element pivotdan kiçikdirsə
        if (arr[j] < pivot) {
            i++; // Sərhədi bir addım sağa çəkirik
            swap(arr, i, j); // Elementi sol tərəfə keçiririk
        }
    }
    // QEYD: Funksiya hələ tam bitməyib, pivotun özü də yerinə qoyulmalıdır.
}

partition Metodunun Tamamlanması

for dövrü işini bitirdikdən sonra, arr[i + 1] və arr[high] (pivotun olduğu yer) indekslərindəki dəyərlərin yerini dəyişdirin. Daha sonra i + 1 dəyərini geri qaytarın.

static int partition(int arr[], int low, int high) {
    // Pivot olaraq massivin sonuncu elementini seçirik
    int pivot = arr[high];
    
    // 'i' pivotdan kiçik olan elementlərin yerləşəcəyi sonuncu indeksi izləyir
    int i = low - 1;

    for (int j = low; j < high; j++) {
        // Əgər cari element pivotdan kiçikdirsə
        if (arr[j] < pivot) {
            i++; // Kiçik elementlərin sahəsini genişləndiririk
            swap(arr, i, j); // Elementi sol tərəfə keçiririk
        }
    }

    // Dövr bitdikdən sonra pivotun özünü (arr[high]) düzgün mövqeyinə (i + 1) qoyuruq
    swap(arr, i + 1, high);
    
    // Pivotun yeni indeksini qaytarırıq ki, növbəti addımda massivi buradan bölək
    return i + 1;
}

Sonda kodunuz bu şəkildə olmalıdır:

class QuickSort {
public:
    // Massivdəki iki elementin yerini dəyişdirən köməkçi metod
    static void swap(int arr[], int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // Pivot elementini seçən və massivi nizamlayan metod
    static int partition(int arr[], int low, int high) {
        // Pivot olaraq sonuncu elementi seçirik
        int pivot = arr[high];
        // Kiçik elementlərin sərhədini göstərən indeks
        int i = low - 1;

        for (int j = low; j < high; j++) {
            // Əgər cari element pivotdan kiçikdirsə
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        // Pivotun özünü düzgün (ortadakı) mövqeyinə yerləşdiririk
        swap(arr, i + 1, high);
        return i + 1;
    }

    // Quick Sort alqoritmini həyata keçirən əsas rekursiv funksiya
    static void quickSort(int arr[], int low, int high) {
        if (low < high) {
            // Parçalama indeksini tapırıq
            int pivotIndex = partition(arr, low, high);

            // Pivotun sol və sağ tərəflərini ayrı-ayrılıqda sıralayırıq
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }
};

main Metodu və Nəticə

main metodunda kodunuza aşağıdakı sıralanmamış massiv təqdim olunacaq: {10, 7, 8, 9, 1, 5}

Kodunuzun istehsal etməli olduğu nəticə: Sıralanmış massiv: 1 5 7 8 9 10

Adından da göründüyü kimi, Quick Sort (Sürətli sıralama) daha sürətli bir sıralama növüdür. Praktikada o, hətta eyni zaman mürəkkəbliyinə malik digər sıralama alqoritmlərini də geridə qoya bilir. Proqram təminatı mütəxəssisləri, alqoritmin bəzi çatışmazlıqlarını aradan qaldırmaq üçün təsadüfi pivot seçimi və ya "üçün medianı" (median-of-three) yanaşması kimi ümumi strategiyalar hazırlamışlar.

Pivot

Pivotun Əhəmiyyəti

Pivot elementinin seçimi həlledici məqamdır, çünki bu, sıralama prosesinin səmərəliliyinə və performansına birbaşa təsir göstərir. Pivot elementi massivi iki alt massivə bölmək üçün istifadə olunur:

• Biri pivotdan kiçik və ya ona bərabər olan elementləri,

• Digəri isə pivotdan böyük olan elementləri ehtiva edir.

Parçalama (partitioning) addımı quick sort alqoritmində fundamental əməliyyatdır və pivot seçimi alqoritmin davranışına əhəmiyyətli dərəcədə təsir edir. Yanlış pivot seçmək balanssız parçalanmaya gətirib çıxarır.

Bu o deməkdir ki, bir alt massiv digərindən əhəmiyyətli dərəcədə çox elementə sahib olacaq və bu da qeyri-effektiv sıralamaya səbəb olacaq. Quick sort üçün pivot seçmək məqsədilə istifadə olunan bəzi ümumi texnikalar aşağıdakılardır.

Təsadüfi Pivot Seçimi (Random Pivot Selection)

Bu strategiyada biz massivdən təsadüfi bir pivot elementi seçirik. Bu, ardıcıl olaraq "pis" pivotla qarşılaşma ehtimalını azaltmağa kömək edir. Biz random kitabxanasından istifadə edəcəyik. Proqramın əvvəlinə bu kitabxananın daxil edildiyindən əmin olun:

#include <random>

Növbəti addım olaraq partition metodunu yeniləyin. low və high indeksləri arasında təsadüfi bir ədəd yaradın. Sonra həmin pivot dəyərini alt massivin sonuna keçirin (swap). O, i + 1 qaytarılmazdan əvvəl öz düzgün mövqeyinə geri qaytarılacaqdır.

static int partition(int arr[], int low, int high) {
    // low və high arasında təsadüfi indeks seçilir
    int pivotIndex = rand() % (high - low + 1) + low;
    // Seçilmiş indeksdəki dəyər pivotValue kimi saxlanılır
    int pivotValue = arr[pivotIndex];
    
    // Pivotu müvəqqəti olaraq massivin sonuna keçiririk
    swap(arr, pivotIndex, high);
    
    int i = low - 1;
    for (int j = low; j < high; j++) {
        // Elementləri pivot dəyəri ilə müqayisə edirik
        if (arr[j] < pivotValue) {
            i++;
            swap(arr, i, j);
        }
    }
    // Pivotu son mövqedən öz qəti yerinə (i + 1) qaytarırıq
    swap(arr, i + 1, high);
    return i + 1;
}

İlk Elementin Pivot Kimi Seçilməsi (First Element as Pivot)

Bu strategiyada biz hər zaman alt massivin ilk elementini pivot olaraq seçirik. Alt massivdəki ilk elementi pivot dəyəri kimi istifadə etmək üçün partition metodunu yeniləyin. Diqqət yetirin ki, burada i dəyişəni low olaraq təyin edilir və fordövrü j-ni low + 1-dən başladır. Həmçinin, for dövrü bitdikdən sonra arr[i] və arr[low] elementlərinin yerini dəyişdiririk (swap).

static int partition(int arr[], int low, int high) {
    // Pivot olaraq alt massivin ilk elementini seçirik
    int pivotValue = arr[low];
    // i-ni pivotun başlanğıc mövqeyinə bərabər edirik
    int i = low;

    // Dövrü pivotdan sonrakı elementdən (low + 1) başlayırıq
    for (int j = low + 1; j <= high; j++) {
        // Əgər cari element pivotdan kiçikdirsə
        if (arr[j] < pivotValue) {
            i++; // Kiçik elementlər üçün yeri artırırıq
            swap(arr, i, j); // Elementi sol tərəfə keçiririk
        }
    }
    
    // Pivotu ilk mövqedən öz düzgün sıralanmış yerinə (i) keçiririk
    swap(arr, i, low);
    
    // Pivotun yeni indeksini qaytarırıq
    return i;
}

Quick Sort Analizi

Quick sort (Sürətli sıralama), merge sort (birləşmə ilə sıralama) kimi digər sıralama alqoritmləri ilə müqayisədə bəzi üstünlüklərə malikdir. Lakin, indiyə qədər gördüyümüz kimi, alqoritm dizaynındakı seçimlər bir sıra güzəştlərdən (tradeoffs) başqa bir şey deyildir. Gəlin quick sort alqoritminə nəzər salaq və onun digər sıralama alqoritmləri ilə necə müqayisə olunduğunu görək.

Zaman Mürəkkəbliyi (Time Complexity)

• Ən Yaxşı Hal (Best Case): Əgər pivot hər addımda massivi təxminən bərabər yarı hissələrə bölərsə, alqoritm özünün ən yaxşı performansını göstərir və bu, O(nlogn) zaman mürəkkəbliyinə səbəb olur. Bunun səbəbi massivi hər addımda yarıya bölməyimiz (logn faktorunu verən budur) və sonra hər səviyyəni emal etmək üçün xətti (n) zaman sərf etməyimizdir.

• Orta Hal (Average Case): Orta hesabla, seçilən pivotların massivi kifayət qədər balanslı hissələrə böldüyünü fərz etsək, quick sort O(nlogn) zamanında çalışır.

• Ən Pis Hal (Worst Case): Quick sort üçün ən pis ssenari, hər zaman ən kiçik və ya ən böyük elementin pivot kimi seçildiyi haldır (məsələn, sıralanmış və ya tərs sıralanmış massivdə). Bu, O(n2) zaman mürəkkəbliyi ilə nəticələnir, çünki biz n−1,n−2 və s. ölçülü (balanssız) hissələr alırıq.

Məkan Mürəkkəbliyi (Space Complexity)

Quick sort in-place (yerində) sıralama alqoritmidir, yəni massivi sabit miqdarda əlavə yaddaş sahəsi istifadə edərək sıralayır. Bununla belə, rekursiv yaddaş stekinin (stack) ölçüsü fərqlilik göstərə bilər:

• Ən yaxşı halda: Rekursiv stək logn qədər təbəqə tələb edə bilər ki, bu da O(logn) məkan mürəkkəbliyinə səbəb olur.

• Ən pis halda: Əgər hər rekursiv çağırış əvvəlki siyahıdan yalnız bir vahid kiçik olan siyahını emal edərsə, bu, O(n) məkan mürəkkəbliyi ilə nəticələnir.

Stabillik (Stability)

Quick sort alqoritmi standart olaraq stabil deyil. Sıralama alqoritmlərində stabillik o deməkdir ki, iki element eyni açara (dəyərə) malik olduqda, onların ilkin ardıcıllığı sıralanmış nəticədə də qorunub saxlanılır. Lakin, müvafiq dəyişikliklər etməklə quick sort alqoritmini stabil hala gətirmək mümkündür.

Üstünlükləri

Quick sort yerində sıralama (in-place sort) alqoritmidir (əlavə saxlama sahəsi tələb etmir), bu da onu yaddaş baxımından səmərəli edir. Onlar çox vaxt merge sort kimi digər sıralama alqoritmlərindən daha yaxşı keş performansına malik olurlar, çünki massiv elementlərinə ardıcıl şəkildə müraciət edirlər. Həmçinin, quick sort quyruq-rekursiv (tail-recursive) struktura malikdir ki, bu da bəzi arxitekturalarda çağırış steki (call stack) yükünün daha az olması deməkdir.

Çatışmazlıqları

Düzgün tətbiq edilmədikdə, quick sort ən pis ssenaridə O(n2) zaman mürəkkəbliyinə malik ola bilər ki, bu da böyük verilən dəstləri üçün ciddi səmərəsizlik yarada bilər. Bu alqoritm stabil deyil, yəni eyni dəyərlərin ardıcıllığını qorumaq istədiyiniz halda yaxşı seçim deyil. Nəhayət, etdiyiniz pivot seçimi səmərəliliyə təsir edə bilər; yanlış pivot seçimi performansın azalmasına gətirib çıxarır.

Quick Sort, orta hal performansı və yaddaş səmərəliliyi sayəsində praktikada daxili yaddaşda (in-memory) sıralama üçün çox vaxt seçilən alqoritmdir. Bununla belə, ən pis hal performansının qəbulolunmaz ola biləcəyi ssenarilərdə diqqətli olmaq lazımdır. Ən pis hal performansından qaçmaq üçün bir çox praktiki tətbiqlər, kiçik alt massivlər üçün insertion sort kimi başqa bir alqoritmə keçid edən hibrid yanaşmadan istifadə edir.