Pengurutan Cepat (Java)

Aplikasi rekursi yang cukup populer adalah Pengurutan Cepat (Quicksort) yang digunakan untuk mengurutkan array. Di bagian sebelumnya kita telah melihat bagaimana mengurutkan array dengan menggunakan pengurutan pilihan dan pengurutan penyisipan yang relatif lebih mudah, akan tetapi akan berjalan lebih lambat untuk array yang besar. Algoritma pengurutan yang lebih cepat sudah tersedia. Salah satunya adalah pengurutan cepat (quick sort), yaitu algoritma rekursif yang ternyata paling cepat hampir pada segala kondisi.

Algoritma pengurutan cepat dibuat berdasarkan ide yang sederhana namun cerdas : Dari beberapa item, pilih satu item. Item ini kita sebut pivot. Pindahkan semua item yang lebih kecil dari pivot ke awal array, dan pindahkan item yang lebih besar ke akhir array. Kemudian letakkan pivot di tengah-tengah kedua grup tersebut. Atau dengan kata lain, posisi pivot adalah posisi terakhir dan tidak perlu dipindahkan lagi.

LangkahUrutCepat bukan algoritma rekursif. Kecepatan pengurutan cepat tergantung dari kecepatan LangkahUrutCepat. Karena ini bukan diskusi utama kita, kita akan tuliskan algoritma LangkahUrutCepat tanpa diskusi lebih lanjut.

static int LangkahUrutCepat(int[] A, int rendah, int tinggi) {
    // Jalankan LangkahUrutCepat pada array dengan indeks 
    // antara rendah dan tinggi pada array A. Nilai yang dikembalikan
    // adalah posisi akhir pivot dalam array
 
    // Kita ambil sembarang pivot, yaitu pada indeks pertama
    int pivot = A[rendah];
 
    // Nilai antara rendah dan tinggi adalah nilai yang belum pernah
    // kita uji. Kurangi tinggi dan naikkan rendah hingga keduanya
    // bernilai sama, pindahkan nilai yang lebih besar dari pivot
    // sehingga nilai tersebut berada di atas tinggi dan pindahkan
    // nilai yang lebih kecil dari pivot sehingga nilainya berada
    // di bawah rendah. Ketika kita mulai, A[rendah] adalah tempat
    // kosong, karena ini adalah posisi awal nilai pivot
 
    while (tinggi > rendah) {
 
        while (tinggi > rendah && A[tinggi] > pivot) {
            // Pindahkan tinggi hingga melewati nilai yang lebih rendah
            // dari pivot. Nilai ini tidak perlu dipindahkan
            hi--;
        }
 
        if (tinggi == rendah)
            break;
 
        // Nilai pada A[tinggi] kurang dari pivot.  Pindahkan ke tempat
        // kosong pada A[rendah], sehingga tempat di A[tinggi]
        // menjadi kosong
 
        A[rendah] = A[tinggi];
        rendah++;
 
        while (tinggi > rendah && A[rendah] < pivot) {
              // Pindahkan rendah hingga melewati nilai yang lebih tinggai
              // pivot. Nilai ini tidak perlu dipindahkan
              rendah++;
        }
 
        if (tinggi == rendah)
              break;
 
        // Nilai A[rendah] lebih tinggi dari pivot. Pindahkan ke tempat
        // kosong pada A[tinggi], sehingga tempat di A[rendah]
        // menjadi kosong.
 
        A[tinggi] = A[rendah];
        tinggi--;
 
    } // akhir while
 
    // Di sini, rendah sama dengan tinggi, dan ada tempat kosong
    // di sini. Posisi ini berada di antara nilai yang lebih tinggi dan
    // nilai yang lebih rendah dari pivot. Letakkan pivot di sini
    // dan kembalikan posisinya.
 
    A[rendah] = pivot;
    return rendah;
 
}  // akhir LangkahUrutCepat

Degan subrutin ini, maka pengurutan cepat mudah dilakukan. Algoritma untuk mengurutkan deretan nilai yaitu dengan menjalankan LangkahUrutCepat pada nilai-nilai tersebut, kemudian menjalankan pengurutan cepat secara rekursif terhadap item yang ada di sebelah kiri pivot dan item yang ada di sebelah kanan pivot. Tentunya kita juga membutuhkan kasus dasar. Yaitu jika list hanya memiliki satu item atau kosong, maka list tersebut telah diurutkan.

static void urutcepat(int[] A, int rendah, int tinggi) {
    // Jalankan pengurutan cepat untuk mengurutkan array
    // antara posisi rendah dan posisi tinggi dalam urutan naik
    if (tinggi <= rendah) {
        // List memiliki panjang nol atau 1. Tidak ada yang perlu 
        // dilakukan, jadi kita keluar dari subrutin
        return;
    }
    else {
        // Jalankan LangkahUrutCepat dan dapatkan posisi pivot
        // Kemudian jalankan urutcepat untuk mengurut item sebelum
        // pivot dan item setelah pivot
        int posisiPivot = LangkahUrutCepat(A, rendah, tinggi);
        urutcepat(A, rendah, pivotPosition - 1);
        urutcepat(A, pivotPosition + 1, tinggi);
    }
}

Seperti biasa, kita telah melihat masalah dengan mengeneralisirnya. Masalah awalnya adalah untuk mengurutkan array, akan tetapi algoritma rekursif dibuat untuk mengurutkan sebagian array. Untuk mengurut keseluruhan array A, kita bisa menggunakanurutcepat() yaitu dengan perintah urutcepat(A, 0, A.length -1).