Bu yazımızda quick sort (hızlı sıralama) algoritması hakkında bilgiler vereceğiz.

Quick Sort (Hızlı Sıralama) Algoritması Nedir ?

Hızlı sıralama algoritması, divide and conquer (böl ve yönet) yöntemi kullanarak dizileri veya listeleri sıralama algoritmasıdır. Quick Sort Algoritması genellikle dizinin boyutu büyük olduğunda verimli bir şekilde çalışır.

Quick Sort (Hızlı Sıralama) Algoritması Nasıl Çalışır ?

Algoritma aşağıdaki adımları izler:

  1. Pivot elemanı seç: Dizinin bir pivot elemanı seçilir. Pivot elemanı genellikle dizinin ortasındaki bir eleman olarak seçilir.
  2. Elemanları ikiye ayır: Dizi pivot elemanına göre ikiye ayrılır. Pivot elemanından küçük olan elemanlar bir tarafa, pivot elemanından büyük olan elemanlar ise diğer tarafa yerleştirilir. Bu işlem pivot elemanının tam olarak yerine konmasını sağlar.
  3. Recursive olarak işlem yap: Her iki taraf için aynı işlem tekrar uygulanır. Bu adımda, pivot elemanı seçilir, elemanlar ikiye ayrılır ve bu işlem her taraf için tekrar uygulanır. Bu işlem böylece dizinin tüm elemanlarının sıralanmış hale gelmesini sağlar.

Quick Sort Algoritması genellikle dizinin boyutu büyük olduğunda verimli bir şekilde çalışır. Ancak, pivot elemanın seçimi yanlış yapıldığında algoritma zaman karışıklığı O(n^2) olabilir, Bu nedenle pivot elemanının seçimi önemlidir.

Quick Sort (Hızlı Sıralama) Algoritması Zaman Karışıklığı

Quick Sort Algoritmasının zaman karışıklığı, genellikle en iyi, ortalama ve en kötü senaryolarda farklıdır.

En iyi senaryo: Dizinin her seferinde pivot elemanın ortalama değerleri seçilir ve dizi eşit şekilde bölünür. Bu durumda, zaman karışıklığı O(n log n) olur.

Ortalama senaryo: Dizinin her seferinde pivot elemanın ortalama değerleri seçilir. Bu durumda, zaman karışıklığı O(n log n) olur.

En kötü senaryo: Dizinin her seferinde pivot elemanın en küçük veya en büyük eleman seçilir. Bu durumda, zaman karışıklığı O(n^2) olur.

Bu yazı dikkatini çekebilir.   Arama Algoritmaları - Linear Search (Doğrusal Arama) Algoritması

Quick Sort Algoritmasının zaman karışıklığı O(n log n) olması için pivot elemanının doğru şekilde seçilmesi önemlidir. Bu nedenle, pivot elemanının seçimi önemlidir. Örneğin, pivot elemanının ortanca değerleri seçilmesi, diziyi eşit şekilde bölmesini ve zaman karışıklığını optimize etmeyi sağlar.

Quick Sort (Hızlı Sıralama) Algoritması Örnek Kod

Şimdide C programlama dili ile, quick sort algoritmasının örnek bir kodunu görelim. Bu kodu örnek olması amacıyla c programlama dilinde göreceğiz. 

#include <stdio.h>

void quicksort(int[], int, int);
int partition(int[], int, int);

int main() {
    int a[] = {7, 12, 1, -2, 0, 15, 4, 11, 9};
    int n = sizeof(a)/sizeof(a[0]);

    quicksort(a, 0, n-1);

    printf("Sorted array: \n");
    for (int i=0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

void quicksort(int a[], int low, int high) {
    int pivot;

    if (low < high) {
        pivot = partition(a, low, high);

        quicksort(a, low, pivot - 1);
        quicksort(a, pivot + 1, high);
    }
}

int partition(int a[], int low, int high) {
    int pivot = a[high];
    int i = low - 1;

    for (int j = low; j <= high- 1; j++) {
        if (a[j] <= pivot) {
            i++;
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }

    int temp = a[i + 1];
    a[i + 1] = a[high];
    a[high] = temp;

    return i + 1;
}

Bu kod, kullanıcı tarafından girilen dizinin elemanlarını Quick Sort Algoritmasını kullanarak sıralar. Fonksiyonlar quick_sort() ve partition() kullanılır. quick_sort() fonksiyonu, diziyi hızlı sıralamak için kullanılır, partition() fonksiyonu ise diziyi bölmek için kullanılır. Bu kod, pivot elemanın en ilk elemanını kullanır.

Çıktısı : 

Sorted array: 
-2 0 1 4 7 9 11 12 15

Bu yazımızda quick sort (hızlı sıralama) algoritması hakkında bilgiler verdik. Diğer veri yapıları konulu yazılarımızı okumak için buraya tıklayabilirsiniz.