Quick Sort

Birçok bilgisayar bilimi dersinde Quick Sort’u defalarca işledik, analiz ettik, hatta sınavlarda bile çözdük. Ama çoğu zaman öğrendiğimiz şeyleri pratiğe dökmeden bırakıyoruz. İşte ben de uzun süre yazmayı ertelediğim bu algoritmayı, sonunda kendi elimle uygulamak istedim. Quick Sort, ortalama O(n log n) karmaşıklığıyla büyük diziler için en verimli sıralama yöntemlerinden biridir. Mantığı basit: Bir pivot seçer, diziyi pivot’tan küçük ve büyük elemanlar olarak ikiye ayırır ve aynı işlemi her alt diziye yeniden uygular. Bu rekürsif yapı, algoritmayı hem hızlı hem de öğretici kılar.

Aşağıdaki kod, Quick Sort’un temel prensiplerini açık bir şekilde gösteren birebir uygulamasıdır.

public class QuickSortExample {

    // Quick Sort algoritmasi, ortalama olarak O(n log n) zamanda calisir.
    // Buyuk diziler icin oldukca etkili bir siralama yontemidir.
    public static void quicksort(int[] array, int left, int right) {
        if (left < right) {
            // Partitioning index'i bulunur ve quicksort bu indekse gore iki alt diziye uygulanir
            int partitionIndex = partition(array, left, right);

            // Sol alt diziyi ayri, sag alt diziyi ayri siralayarak recursive olarak quicksort uygulanir
            quicksort(array, left, partitionIndex - 1);
            quicksort(array, partitionIndex + 1, right);
        }
    }

    private static int partition(int[] array, int left, int right) {
        int pivot = array[right];  // Pivot olarak son eleman secilir
        int i = (left - 1);  // Index of smaller element

        for (int j = left; j < right; j++) {
            // Eger mevcut eleman pivot'tan kucuk veya esitse
            if (array[j] <= pivot) {
                i++;

                // i'nci ve j'nci elemanlari degistirir
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        // Pivot elemanini dogru konumuna yerlestirir
        int temp = array[i + 1];
        array[i + 1] = array[right];
        array[right] = temp;

        return i + 1;
    }

    // Test icin main metodu
    public static void main(String[] args) {
        int[] array = { 10, 7, 8, 9, 1, 5 };
        int n = array.length;
        quicksort(array, 0, n - 1);
        System.out.println("Siralanmis dizi: ");
        for (int i = 0; i < n; ++i)
            System.out.print(array[i] + " ");
        System.out.println();
    }
}