Pengurutan (Java)

Ada banyak algoritma yang tersedia untuk melakukan pengurutan. Salah satu yang paling mudah dimengerti adalah pengurutan penyisipan (insertion sort). Metode ini juga bisa digunakan untuk menjaga agar list selalu dalam urutan tertentu (naik atau turun) sewaktu kita menambah item baru ke dalam list. Mari kita lihat contoh pertama :

Misalnya kita memiliki list yang sudah diurutkan, dan kita ingin menambahkan sebuat item ke dalamnya. Jika kita ingin memastikan bahwa suatu list tetap dalam kondisi terurut, maka item tersebut harus diletakkan di tempat yang tepat, yaitu semua item yang lebih kecil harus ditempatkan sebelum item tersebut, dan semua item yang lebih besar ditempatkan setelahnya. Artinya kita harus menggeser semua item yang lebih besar ke satu sisi untuk memberi ruangan pada item baru yang akan ditambahkan.

static void sisip(int[] A, int jmlItem, int itemBaru) {
    // Kondisi awal : jmlItem adalah jumlah item pada A.
    //    Item ini harus berada dalam kondisi terurut naik di mana
    //    (A[0] <= A[1] <= ... <= A[jmlItem-1]).
    //    Ukuran array harus lebih besar dari jmlItem.
    // Kondisi akhir : jumlah item akan ditambah dengan satu,
    //    itemBaru telah ditambah pada array, dan semua item
    //    masih dalam kondisi terurut.
    // Catatan: untuk menyelesaikan proses penyisipan item
    //    dalam array, variabel yang mencatat jumlah item dalam
    //    array harus ditambah satu setelah memanggil subrutin ini.
 
    int lok = jmlItem - 1;  // Mulai dari akhir array
 
    /* Pindahkan item yang lebih besar dari itemBaru satu posisi;
       Stop jika item yang lebih kecil ditemukan atau sampai ke
       awal array (lok == 0) */
 
    while (lok >= 0 && A[lok] > itemBaru) {
        A[lok + 1] = A[lok];  // Pindahkan lokasi item dari posisi lok ke lok+1
        lok = lok - 1;        // Pindah ke lokasi sebelumnya
    }
 
    A[lok + 1] = itemBaru;  // Letakkan itemBaru di tempat kosong
}

Metode di atas bisa dikembangkan menjadi metode pengurutan jika kita mengeluarkan semua item dari array yang belum diurutkan, kemudian memasukkannya kembali satu demi satu, sambil menjaga agar array tetap terurut selama kita menambah item ke array baru. Setiap penyisipan bisa dilakukan dengan rutin sisip() di atas. Dalam algoritma sesungguhnya, kita tidak benar-benar mengambil semua item dari dalam array, kita hanya cukup mengingat bagian mana yang sudah diurutkan.

static void urutPenyisipan(int[] A) {
    // Mengurutkan array A dalam urutan menaik (dari kecil ke besar)
 
    int itemTerurut; // Jumlah item yang sudah diurut
 
    for (itemTerurut = 1; itemTerurut < A.length; itemTerurut++) {
        // Anggap item A[0], A[1], ... A[itemTerurut-1]
        // telah diurutkan. Sisipkan A[itemTerurut]
        // ke dalam bagian yang sudah diurutkan
 
        int temp = A[itemTerurut];  // Item yang akan disisipkan
        int lok = itemTerurut - 1;  // Mulai dari akhir list
 
        while (lok >= 0 && A[lok] > temp) {
            A[lok + 1] = A[lok]; // Pindahkan item dari lok ke lok+1
            lok = lok - 1;       // Pindah ke lokasi sebelumnya
        }
 
        A[lok + 1] = temp; // Letakkan temp di tempat kosong
    }
}

Ilustrasi berikut adalah ilustrasi di tengah-tengah pengurutan, yang menunjukkan apa yang terjadi di tengah-tengah salah satu eksekusi perulangan for dari kode di atas, ketika itemTerurut = 5.

Pengurutan Pilihan (Selection Sort)

Metode pengurutan lainnya yang biasa digunakan adalah pengurutan pilihan (selection sort). Metode ini mencari item terbesar di dalam list, kemudian memindahkannya ke akhir array -- atau dengan kata lain di tempatnya, karena item terbesar akan berada di akhir array. Setelah item terbesar ditempatkan di tempat yang benar, kita gunakan cara yang sama, yaitu cari item terbesar berikutnya, kemudian letakkan di tempat kedua dari akhir, dan seterusnya. Metode ini dapat ditulis sebagai :

static void urutPilihan(int[] A) {
 
    // Urut A dengan urutan menaik dengan Pengurutan Pilihan
 
    for (int tmptTerakhir = A.length-1; tmptTerakhir > 0; tmptTerakhir--) {
        // Cari nilai terbesar di antara A[0], A[1], ..., A[tmptTerakhir],
        // dan pindahkan ke tmptTerakhir dengan cara menukarny
        // dengan nilai yang ada di tmptTerakhir
 
        int lokMaks = 0;  // Lokasi nilai terbesar saat ini
 
        for (int j = 1; j <= tmptTerakhir; j++) {
            if (A[j] > A[lokMaks]) {
                // Karena A[j] lebih besar dari nilai maksimum yang pernah
                // kita lihat, j adalah lokasi baru tempat di mana nilai
                // maksimum tersebut berada
                lokMaks = j;
            }
        }
 
        int temp = A[lokMaks];  // Tukar nilainya dengan A[tmptTerakhir].
        A[lokMaks] = A[tmptTerakhir];
        A[tmptTerakhir] = temp;
    }  // akhir perulangan
}

Pengurutan penyisipan dan pengurutan pilihan cocok digunakan untuk mengurut array dengan ukuran kecil (hingga beberapa ratus elemen). Ada beberapa algoritma pengurutan lain yang jauh lebih cepat dari pengurutan penyisipan dan pengurutan pilihan untuk array yang sangat besar.

Mengacak Nilai

Kita akan sudahi bagian ini dengan masalah yang sedikit berkaitan, lebih jarang muncul, akan tetapi menarik, yaitu bagaimana caranya meletakkan elemen array dengan urutan acak. Misalnya adalah untuk mengocok kartu. Algoritma baik untuk mengocok mirip dengan pengurutan pilihan, akan tetapi kita tidak memindahkan item terbesar ke array paling belakang. Item dipilih secara acak dan dipindahkan ke akhir array. Berikut ini adalah subrutin untuk mengocok array bertipe int.

static void kocok(int[] A) {
    // Kondisi akhir : Item pada A diatur dalam urutan yang acak
 
    for (int tmptTerakhir = A.length-1; tmptTerakhir > 0; tmptTerakhir--) {
        // Pilih lokasi acak di antara 0,1,...,tmptTerakhir.
        int lokAcak = (int)(Math.random()*(tmptTerakhir+1));
 
        // Tukar item pada lokAcak dengan A[tmptTerakhir]
        int temp = A[lokAcak];
        A[lokAcak] = A[tmptTerakhir];
        A[tmptTerakhir] = temp;
    }
}