Pengurutan (sorting) adalah proses mengatur sekumpulan objek menurut
urutan atau susunan tertentu. Urutan objek tersebut dapat menaik (ascending) atau
menurun (descending). Bila N buah objek atau data disimpan di dalam larik L,
maka pengurutan menaik berarti menyusun elemen larik sedemikian sehingga:
L[1] > L[2] > L[3 > … > L[N]
Sedangkan pengurutan menurun berarti menyusun elemen larik sedemikian
sehingga:
L[1] < L[2] < L[3 < … < L[N]
Data yang diurut dapat berupa data bertipe dasar atau tipe terstruktur (record).
Jika data bertipe terstruktur, maka harus dispesifikasikan berdasarkan field apa
data tersebut diurutkan. Field yang dijadikan dasar pengurutan dikenal sebagai
field kunci.
Adanya kebutuhan terhadap proses pengurutan memunculkan bermacammacam
metode pengurutan. Metode tersebut diantaranya adalah:1). Metode
Pengurutan Gelembung (Bubble Sort) 2). Metode Pengurutan Pilih (Selection
Sort) 3). Metode Pengurutan Sisip (Insertion Sort) 4). Metode Pengurutan Shell
(Shell Sort) 5). Heap Sort 6). Quick Sort 7). Merge Sort 8). Radix Sort dan 9).
Tree Sort. Pada modul ini, tidak semua metode pengurutan akan dibahas.
Tidak ada metode yang terbaik untuk pengurutan. Kebanyakan metode
pengurutan sederhana hanya bagus untuk volume data yang kecil tetapi lambat
untuk ukuran data yang besar. Metode pengurutan yang lebih cepat pun (seperti
quick sort dan merge sort) memang bagus untuk mengurutkan data yang banyak,
tetapi tidak bagus untuk ukuran data yang sedikit karena memerlukan beban
tambahan (overhead) yang boros waktu dan memori.
Metode pengurutan dapat diklasifikasikan sebagai berikut:
a. Metode pengurutan internal, yaitu metode pengurutan untuk data yang
disimpan di dalam memori computer. Umumnya struktur internal yang
dipakai untuk pengurutan internal adalah larik, sehingga pengurutan
internal disebut juga pengurutan larik.
b. Metode pengurutan eksternal, yaitu metode pengurutan untuk data
yang disimpan di dalam disk storage, disebut juga pengurutan arsip
(file), karena struktur eksternal yang dipakai adalah arsip.
1. Metode Pengurutan Gelembung (Bubble Sort)
Metode ini memiliki prinsip pengapungan. Apabila kita menginginkan
larik terurut menaik, maka elemen larik yang berharga paling kecil ‘diapungkan’,
artinya diangkat ke atas (atau ke ujung kiri larik) melalui proses pertukaran.
Proses pengapungan ini dilakukan sebanyak N-1 langkah dengan N adalah ukuran
larik. Pada akhir setiap langkah ke-I, larik L[1..N] akan terdiri atas dua bagian
yaitu bagian yang sudah terurut, yaitu L[1..I] dan bagian yang belum terurut
L[I+1..N]. Setelah langkah terakhir, diperoleh larik L[1..N] yang terurut menaik. Pengurutan gelembung merupakan metode pengurutan yang tidak efisien. Hal ini
disebabkan oleh banyaknya operasi pertukaran yang dilakukan pada setiap
langkah pengapungan. Untuk nukuran larik yang besar, pengurutan dengan
metode ini membutuhkan waktu yang lama. Karena alasan itu, maka metode ini
jarang digunakan dalam praktek. Namun, kelebihan metode ini adalah pada
kesederhanaannya dan mudah dipahami.
2. Metode Pengurutan Pilih (Selection Sort)
Metode ini memilih elemen maksimum/minimum dari larik, lalu
menempatkan elemen itu pada awal atau akhir larik (elemen terujung).
Selanjutnya elemen terujung tersebut ‘diisolasi’ dan tidak disertakan pada proses
selanjutnya. Proses yang sama diulang untuk elemen larik yang tersisa, yaitu
memilih elemen maksimum/minimum berikutnya dan mempertukarkannya
dengan elemen terujung larik sisa. Dibandingkan dengan metode pengurutan gelembung, metode pengurutan pilih
memiliki kinerja yang lebih baik. Alasannya, operasi pertukaran elemen hanya
dilakukan sekali saja dengan demikian lama pengurutannya berkurang.
3. Metode Pengurutan Sisip (Insertion Sort)
Algoritma pengurutan sisip untuk memperoleh elemen larik yang terurut
menaik. Kelemahan metode pengurutan sisip terletak pada banyaknya operasi pergeseran
yang diperlukan dalam mencari posisi yang tepat untuk elemen larik. Untuk larik
dengan N yang besar, jumlah operasi pergeseran meningkat secara kuadratik,
sehingga pengurutan sisip kurang bagus untuk volume data yang besar.
4. Metode Pengurutan Shell (Shell Sort)
Metode shell sort pertama kali diperkenalkan oleh Donald L. Shell tahun
1959. Metode ini didasarkan pada penukaran sepasang elemen untuk mencapai
keadaan urut. Dalam hal ini jarak elemen yang akan dibandingkan (kemudian
ditukarkan) ditentukan (biasanya jarak ini ditentukan dengan cacah data = n
dibagi 2). Pada langkah pertama, elemen-elemen yang terpisahkan oleh jarak itu
dibandingkan dan jika perlu ditukarkan. Kemudian jarak dibagi 2 sehingga
bernilai setengah jarak yang semula. Kemudian, pembandingan dan penukaran itu
dilanjutkan dengan jarak yang baru. Demikian selanjutnya hingga jarak sama
dengan 1.
5. Metode Merge Sort
kemudian kita ingin mengurutkannya. Larik masukan yang mempunyai N elemen
dianggap N buah larik yang masing-masing tersusun oleh 1 elemen. Untuk setiap
larik, kita lakukan penggabungan (merging) dengan larik di sebelahnya dengan
meletakan elemen yang lebih kecil di sebelah kiri kemudian penggabungan
diteruskan hingga mendapatkan kembali 1 larik yang utuh.
0 comments:
Speak up your mind
Tell us what you're thinking... !