Quicksort

Öğrendikten sonra yazmak lazımdı. Yazmadık, şimdi yazıyorum.

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();
    }
}