Memahami Struktur Data V.2.0.0 (Sorting)
Ditulis oleh : Farhan Rivaldy
Halo Teman-teman, artikel kali ini merupakan sambungan dari artikel yang pernah Saya tulis sebelumnya :
Di artikel kali ini Saya akan membahas tentang algoritma sorting.
Sorting (pengurutan) merupakan konsep yang sangat penting dalam dunia pemrograman komputer. Mengapa sangat penting? Karena dengan sorting Kita bisa menyelesaikan berbagai macam permasalahan yang ada dengan efektif, baik secara memori maupun secara waktu.
Sorting dapat Kita temukan dalam kehidupan sehari-hari, contoh :
- List nama mahasiswa secara urutan NIM (angka)
- Kamus (alfabet)
In-place sorting & Not-in-place sorting
Beberapa algoritma sorting membutuhkan extra space untuk perbandingan dan penyimpanan sementara beberapa element data.
Algoritma yang tidak membutuhkan extra space, yang hanya terjadi di dalam array itu sendiri dinamakan In-place sorting. Bubble sort adalah salah satu contoh In-place sorting.
Sedangkan beberapa algoritma membutuhkan lebih dari satu extra space atau lebih dari satu array dinamakan Not-in-place sorting. Merge sort adalah salah satu contoh Not-in-place sorting.
Stable and Not Stable Sorting
Jika algoritma sorting, setelah mengurutkan sebuah data, tidak mengubah urutan data serupa di mana mereka muncul, maka itu disebut juga dengan stable sorting.
Tapi sebaliknya, jika urutan data serupa berganti posisi, maka itu disebut juga dengan not stable sorting.
Stabilitas sebuah algoritma itu penting ketika kita memiliki data key-value dengan kemungkinan terdapat key yang sama (seperti nama orang sebagai key dan detailnya sebagai value). Dan Kita ingin mengurutkan data tersebut berdasarkan key. Perhatikan contoh berikut :
String dataMahasiswa[] =
[
Abdul: “Hukum”,
Abdul: “Ekonomi”
Farhan: “Informatika”,
Rivai: “Tata Boga”,
Rivaldy: “Manajemen”,
];
Note : Contoh diatas bukan best-practice dalam membuat sebuah array!
Ketika data yang sama tidak dapat dibedakan, seperti bilangan bulat atau data apa pun di mana seluruh data bertindak sebagai key, stabilitas tidak menjadi masalah. Stabilitas juga tidak menjadi masalah jika semua key berbeda. Perhatikan contoh berikut :
Long NIMMahasiswa[] = [2111003, 2111002, 2111018, 2111027 ];
float IPKMahasiswa[] = [3.59, 3.68, 3.68, 3.70,3.70,3.85];
String Jurusan[] = [“Informatika”, “Hukum”, “Manajemen”, “Tata Boga”];
Perhatikan contoh berikut :
Kita punya kumpulan data mahasiswa dan jurusan masing-masing mahasiswa tersebut :
(Raja, A)
(Hakim, A)
(Farhan, B)
(Abdul, B)
(Angga, A)
(Zikri, B)
Jika Kita melakukan sorting berdasarkan nama, maka hasilnya sangat kecil kemungkinannya bahwa kumpulan data yang dihasilkan akan dikelompokkan secara kelasnya.
(Abdul, B)
(Angga, A)
(Farhan, B)
(Hakim, A)
(Raja, A)
(Zikri, B)
Jadi kita mungkin harus melakukan sorting lagi untuk mendapatkan daftar mahasiswa yang memiliki kelas yang sama juga. Tetapi dalam melakukannya, jika algoritma sorting tidak stabil, Kita mungkin mendapatkan hasil seperti ini :
(Angga, A)
(Hakim, A)
(Raja, A)
(Farhan, B)
(Zikri, B)
(Abdul, B)
Kumpulan data yang Kita miliki sekarang sudah terurut secara kelasnya, tapi tidak secara nama, Lihat Farhan menjadi urutan pertama, Zikri menjadi urutan kedua, sedangkan Abdul menjadi urutan terakhir, sehingga Kita perlu mengganti algoritma yang stabil sehingga kumpulan data Kita akan menjadi seperti ini :
(Angga, A)
(Hakim, A)
(Raja, A)
(Abdul, B)
(Farhan, B)
(Zikri, B)
Saya rasa sudah jelas mengapa Kita harus memilih algoritma yang tepat untuk menyelesaikan permasalahan yang Kita hadapi agar proses dalam penyelesaian masalah tidak berbelit-belit sehingga waktu yang dihabiskan menjadi minim.
Pertanyannya… Algoritma sorting yang termasuk stabil dan tidak stabil apa saja?
Stable Sorting : Bubble Sort, Insertion Sort, Merge Sort, Count Sort, dll
Not Stable Sorting : Quick Sort, Heap Sort, dll
Perlu diketahui bahwa sorting dapat dilakukan terhadap data yang berada di main memory (ram) maupun data yang berada di secondary memory (hardisk, usb, ssd, dsb)
Di dalam pengurutan data terdapat istilah ascending(asc) dan descending(desc). Pengurutan dengan nilai dari kecil ke nilai yang besar disebut ascending(urut naik), sedangkan yang disusun dari besar ke nilai yang kecil disebut descending(urut turun).
Bubble Sort Algorithm
Bubble sort adalah algoritma sorting yang paling sederhana. Algoritma sorting ini melakukan perbandingan elemen data sekarang dengan elemen data terdekatnya.
Algoritma ini menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan tergantung jenis pengurutannya, ascending atau descending. Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, seterusnya sampai dengan iterasi sebanyak n-1.
Bubble sort akan berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.
Contoh Kita punya array dengan data seperti berikut :
Bubble sort dimulai dari dua index pertama untuk membandingkan sesuai dengan urutan yang Kita inginkan ascending atau descending. Dalam kasus ini Kita ingin urutan ascending, karena 14 lebih kecil dari 33 maka tidak terjadi pertukaran.
Kita lihat, 33 lebih kecil dari 27, maka Kita tukar posisinya
Sehingga array Kita menjadi seperti ini :
Selanjutnya Kita membandingkan 33 dan 35, karena sudah sesuai urutan maka Kita tidak memindahkan posisinya.
Selanjutnya Kita membandingkan 35 dan 10, karena 10 lebih besar dari 35 maka Kita pindahkan posisinya.
Setelah Kita berhasil mengganti posisinya, Kita sudah berada di posisi index terakhir, sehingga array Kita akan menjadi seperti diatas.
Karena array Kita belum terurut secara sempurna, maka Kita akan mengulang proses nya, sehingga pada perulangan yang kedua array Kita akan menjadi seperti ini
Karena array Kita belum sempurna, maka Kita akan mengulang lagi proses perulangannya sehingga array Kita akan menjadi seperti ini
Dan pada proses perulangan yang terakhir array Kita akan menjadi seperti ini
Dan ketika data di index beruturan , bubble sort akan menganggap bahwa array telah diurutkan sepenuhnya.
Pelu diingat algoritme ini tidak cocok untuk kumpulan data besar karena kompleksitas waktu yang dibutuhkan adalah O(n²) atau Quadratic Time.
Mari Kita lihat penyelesaian bubble sort di bahasa pemrograman java.
Output kode diatas bisa Kalian lihat dibawah ini :
Lalu bagaimana dengan urutan descending? perhatikan kode berikut
Output kode diatas bisa Kalian lihat dibawah ini :
Sekarang urutannya menjadi dari terbesar ke yang terkecil, untuk mengubah urutannya Kita cukup mengubah logika di baris 23
if (listAngka[j] ( < atau > ) listAngka[j+1]){Insertion Sort Algorithm
Insertion sort adalah algoritma sorting yang paling sederhana. Algoritma sorting ini melakukan perbandingan elemen.
Mengapa algoritma ini dinamakan dengan insertion sorting? Karena cara kerja algoritma ini adalah membagi dua bagian, bagian yang pertama berisi data yang sudah diurutkan sesuai urutan yang Kita inginkan (ASC/DESC) dan bagian kedua berisi data yang belum diurutkan.
Bagian yang belum diurutkan akan dimasukan ke bagian yang sudah diurutkan sesuai urutan yang Kita inginkan, oleh karena itu algoritma ini dinamakan Insertion Sort.
Contoh Kita punya array dengan data seperti berikut :
Insertion sort dimulai dari dua index pertama untuk membandingkan sesuai dengan urutan yang Kita inginkan ascending atau descending.
Dalam kasus ini Kita ingin urutan ascending, karena 14 lebih kecil dari 33 maka tidak terjadi pertukaran. sehingga 14 akan masuk ke bagian sub-list yang sudah diurutkan.
Kemudian Kita berpindah ke index selanjutnya yaitu 33 dan 27
Karena 33 berada di posisi yang salah maka Kita akan menukar posisinya, sehingga array Kita akan menjadi seperi ini
Sekarang Kita punya 14 dan 27 di dalam sub-list yang sudah diurutkan. Selanjutnya, Kita membandingkan 33 dengan 10.
Karena 33 berada di posisi yang salah maka Kita akan menukar posisinya, sehingga array Kita akan menjadi seperti ini
Ketika Kita menukar posisi tadi membuat 27 dan 10 tidak menjadi urut di dalam sub-listnya .
Oleh karena itu Kita tukar lagi posisinya
Sekali lagi Kita temukan bahwa 14 dan 10 dalam urutan yang salah, oleh karena itu Kita tukar lagi posisinya
Sehingga array Kita akan menjadi seperti ini
Proses ini berlangsung sampai semua nilai yang berada di bagian yang belum disortir masuk ke dalam sub-list yang sudah diurutkan.
Pelu diingat algoritme ini tidak cocok untuk kumpulan data besar karena kompleksitas waktu yang dibutuhkan adalah O(n²) atau Quadratic Time.
Mari Kita lihat penyelesaian insertion sort di bahasa pemrograman java.
Output kode diatas bisa Kalian lihat dibawah ini :
Lalu bagaimana dengan urutan descending? perhatikan kode berikut
Output kode diatas bisa Kalian lihat dibawah ini :
Sekarang urutannya menjadi dari terbesar ke yang terkecil, untuk mengubah urutannya Kita cukup mengubah logika di baris 27
while (j >= 0 && listAngka[j] ( < atau > ) key){Selection Sort Algorithm
Selection sort adalah algoritma pengurutan sederhana. Algoritma pengurutan ini adalah algoritma yang melakukan perbandingan, di mana data dibagi menjadi dua bagian, bagian yang diurutkan di ujung kiri dan bagian yang tidak disortir di ujung kanan. Awalnya, bagian yang diurutkan kosong dan bagian yang tidak disortir adalah seluruh data.
Data akan dipilih (terbesar atau terkecil tergantung urutan yang diinginkan) dari array yang belum disortir dan ditukar dengan elemen paling kiri yang sudah disortir, proses ini terus berjalan sampai semua elemen berhasil dipindahkan.
Contoh Kita punya array dengan data seperti berikut :
Untuk mencari posisi pertama ke dalam daftar yang sudah diurutkan, seluruh data dipindai secara berurutan.
Dalam kasus ini posisi pertama adalah 14, Ketika berhasil mencari seluruh data Kita menemukan bahwa 10 adalah nilai terendah.
Jadi kita ganti 14 dengan 10. Setelah melakukan iterasi pertama angka 10, merupakan nilai minimum dalam daftar dan muncul di posisi pertama dari daftar yang diurutkan.
Kemudian Kita lakukan iterasi lagi di posisi kedua, di mana 33 berada, Kita mulai memindai sisa daftar secara linier.
Kita menemukan bahwa 14 adalah nilai terendah kedua dalam data dan seharusnya muncul di tempat kedua, maka Kita tukar posisinya.
Setelah melakukan dua kali iterasi, dua nilai terkecil diposisikan di awal dengan cara yang diurutkan.
Proses yang sama dilakukan berulang kali sampai akhirnya semua data berhasil diurutkan.
Pelu diingat algoritme ini tidak cocok untuk kumpulan data besar karena kompleksitas waktu yang dibutuhkan adalah O(n²) atau Quadratic Time.
Mari Kita lihat penyelesaian selection sort di bahasa pemrograman java.
Output kode diatas bisa Kalian lihat dibawah ini :
Lalu bagaimana dengan urutan descending? perhatikan kode berikut
Output kode diatas bisa Kalian lihat dibawah ini :
Sekarang urutannya menjadi dari terbesar ke yang terkecil, untuk mengubah urutannya Kita cukup mengubah logika di baris 16
if (listAngka[j] ( > atau < ) listAngka[minIndex]){Merge Sort Algorithm
Merge sort adalah algoritma sorting berdasarkan teknik divide & conquer.
Dengan kompleksitas waktu kasus terburuk adalah (n log n).
Cara kerja merge sort adalah pertama-tama membagi array menjadi dua bagian yang sama sampai tidak dapat dibagi lagi kemudian menggabungkannya dengan sesuai urutan yang Kita inginkan.
Contoh Kita punya array dengan data seperti berikut :
Seperti yang Kita tahu bahwa merge sort pertama-tama membagi seluruh array menjadi dua bagian yang sama sampai nilai paling kecil tercapai(tidak bisa dibagi). Karena array Kita ada 8 item maka ketika dibagi menjadi dua array akan menjadi 4 elemen.
Sekarang Kita akan bagi lagi array tersebut menjadi dua sehingga array Kita akan menjadi seperti ini
Kemudia Kita bagi lagi array nya menjadi kecil sehingga tidak bisa dibagi lagi, sehingga array Kita akan menjadi seperti ini
Sekarang, Kita menggabungkannya dengan cara yang persis sama seperti saat dipecah. Harap perhatikan kode warna yang diberikan pada elemen tersebut.
Pertama-tama Kita membandingkan elemen untuk setiap elemen dan kemudian menggabungkannya dengan urutan yang Kita inginkan (ASC/DESC).
Kita lihat bahwa 14 dan 33 berada di posisi yang diurutkan. Kemudia Kita membandingkan 27 dan 10 dan memindahkan 10 terlebih dahulu, diikuti oleh 27. Hal ini dilakukan seterusnya mengubah urutan 19 dan 35 dan 42 dan 44 , sehingga array Kita akan menjadi seperti ini :
Proses berikutnya yaitu tahap penggabungan, Kita menggabungkan array tersebut menjadi dua bagian dan kemudian mengurutkannya sesuai dengan urutan yang Kita inginkan, sehingga array Kita akan menjadi seperti ini :
Setelah berhasil mengurutkan data, Kita akan menggabungkan lagi data tersebut, sehingga array Kita akan menjadi seperti ini :
Mari Kita lihat penyelesaian merge sort di bahasa pemrograman java.
Output kode diatas bisa Kalian lihat dibawah ini :
Lalu bagaimana dengan urutan descending? perhatikan kode berikut
Output kode diatas bisa Kalian lihat dibawah ini :
Sekarang urutannya menjadi dari terbesar ke yang terkecil, untuk mengubah urutannya Kita cukup mengubah logika di baris 27
if (left[temporaryLeft] ( > atau < ) right[TemporaryRight]) {Shell Sort Algorithm
Algoritma shell sort pertama kali dikenalkan oleh Donald L. Shell pada tahun 1959. Algoritma shell sort adalah algoritma sorting yang sangat efisien dan hampir miri dengan algoritma insertion sorting, yang membedakannya adalah tidak melakukan pergeseran elemen secara besar-besaran.
Algoritma shell sort didasarkan pada penukaran sepasang elemen untuk mencapai urutan yang Kita inginkan (ASC/DESC). Algoritma shell sort akan membandingkan elemen dengan jarak tertentu (biasanya saat algoritma ini dieksekusi pertama kali jarak elemen ditentukan dari jumlah separuh elemen yang ada N = jumlahArray / 2).
Contoh Kita punya array dengan data seperti berikut :
Untuk mendapatkan gambaran tentang cara kerja algoritma shell sort, Kita gunakan dalam contoh array sebelumnya. Karena jumlah array diatas ada 8 maka jarak antar elemen ketika pertama kali yaitu sebanyak 4 jarak. Kemudian Kita masukkan ke sub-array dari semua nilai yang terletak pada jarak antar 4 posisi elemen , sehingga elemen-elemen tersebut akan menjadi seperti ini :
{35, 14}, {33, 19}, {42, 27} dan {10, 44}
Kemudian Kita membandingkan nilai di setiap sub-array dan menukarnya (jika diperlukan) sesuai urutan yang Kita inginkan di array asli. Setelah langkah ini, array baru akan terlihat seperti ini.
Kemudian Kita mengambil sebanyak 1 jarak antar elemen yang akan menghasilkan dua sub-array {14, 27, 35, 42}, {19, 10, 33, 44}
Kami membandingkan dan menukar nilai (jika diperlukan), kemudian Kita masukkan ke dalam array asli. Setelah langkah ini, array akan terlihat seperti ini
Terakhir, kita mengurutkan array sebanyak 1 jarak. di tahap ini Shell sort akan menggunakan insertion sort untuk mengurutkan array. sehingga prosesnya akan menjadi seperti ini
Kita bisa lihat, pada step terakhir hanya memerlukan 4 langkah dengan insertion sort untuk melakukan pengurutan data yang belum terurut
Mari Kita lihat penyelesaian merge sort di bahasa pemrograman java.
Output kode diatas bisa Kalian lihat dibawah ini :
Lalu bagaimana dengan urutan descending? perhatikan kode berikut
Output kode diatas bisa Kalian lihat dibawah ini :
Sekarang urutannya menjadi dari terbesar ke yang terkecil, untuk mengubah urutannya Kita cukup mengubah logika di baris 21
for (j = i; j ( >= atau >= ) jarak && listAngka[j - jarak] < temp; j -= jarak)Quick Sort Algorithm
Algoritma sorting yang akan Kita bahas terakhir adalah quick sort. Algoritma ini diperkenalkan oleh C.A.R Hoare pada tahun 1960, Algoritma ini merupakan pengembangan lebih lanjut dari shell sort sehingga menurut para ahli computer scientist bahwa algoritma ini terbilang sangat efisien. Bagaimana cara kerja algoritma ini?
Kita mengambil nilai pivot (tengah) Ada banyak versi untuk mengambil nilai pivot, diantaranya
- Selalu pilih elemen pertama sebagai pivot
- Selalu pilih elemen terakhir sebagai pivot
- Pilih elemen acak sebagai pivot
- Pilih elemen tengah sebagai pivot
Dalam artikel kali ini Kita akan gunakan cara nomor dua untuk mengambil nilai pivotnya. Proses utama dalam quick sort ada di fungsi partition(). tugas yang dilakukan partisi adalah, diberikan sejumlah array dan elemen x dari array sebagai pivot, letakkan semua elemen yang lebih kecil dari x sebelum x, dan letakkan semua elemen yang lebih besar dari x setelahnya x, atau sebaliknya tergangtung posisi urutan sesuai yang Kita inginkan (ASC/DESC), Semua ini harus dilakukan dalam waktu linier.
Agar lebih memahami quick sort Kita bisa melihat animasi dibawah ini
Mari Kita lihat penyelesaian quick sort di bahasa pemrograman java.
Output kode diatas bisa Kalian lihat dibawah ini :
Lalu bagaimana dengan urutan descending? perhatikan kode berikut
Output kode diatas bisa Kalian lihat dibawah ini :
Sekarang urutannya menjadi dari terbesar ke yang terkecil, untuk mengubah urutannya Kita cukup mengubah logika di baris 20
if(listAngka[j] ( > atau < ) pivot){PENUTUP
Sebenarnya masih ada banyak sekali algoritma sorting yang sudah ada tapi di artikel ini Saya hanya akan membahas sebagian kecil saja, mungkin di next artikel akan Saya coba untuk membahas algoritma sorting lainnya
Perlu teman-teman ketahui, tidak ada algoritma pengurutan terbaik atau terburuk. Setiap algoritma berguna dalam kasus tertentu begitu juga sebaliknya.
Algoritma yang sama dapat mengubah perilakunya tergantung pada ukuran data input. Pendekatan pertama untuk memilih Algortima sorting adalah menentukan ruang masalah dan kebutuhan teman-teman.
Dengan menggunakan Big-O Notation sebagai tolak ukur untuk menghitung waktu dan memory yang digunakan maka dari situlah Kita bisa memilih algoritma yang cocok untuk digunakan
Pada artikel ini Saya rasa cukup sampai disini saja dulu, bila teman-teman masih bingung dengan tulisan Saya ini bisa mengajukan pertanyaan atau ada hal yang ingin dibahas silahkan komentar dibawah…
Kurang lebihnya mohon dimaafkan, bila ada saran dan kritik sangat dipersilahkan sekali demi menambah wawasan setiap orang yang membaca artikel ini.
Jangan lupa follow akun medium Saya Farhan Rivaldy dan DSC Mulia University agar bisa mendapatkan pengetahuan lainnya.
Sekian dan terima kasih
じゃあね ー See you
Refrensi :
“Mimpi tidak berarti apa-apa jika kau tidak menggapainya dengan tangan mu sendiri.” — Jin Mori
