Hai hai hai sobat kodingers apa kabar 😁 ? Semoga sehat selalu dan lancar ya kodingannya 😂. Seperti yang kami janjikan pada postingan sebelumnya, sekarang kami akan membahas tentang 2 sorting lagi Merge sort dan Shell sort sekaligus sebagai penutup pada pembahasan tentang algoritma sorting.
Tenang saja, itu bukan berarti menjadi postingan yang terakhir 😃 masih ada materi-materi yang akan menemani kita pada postingan-postingan selanjutnya. Sekarang langsung saja kita masuk pada pembahasan yang pertama, yaitu merge sort.
Merge Sort
Merge sort merupakan algoritma pengurutan yang memang dirancang untuk mengurutkan data-data dalam jumlah yang sangat besar guna untuk mengefesiensi waktunya. Adapun cara kerja algoritma pengurutan data merge sort dilakukan dengan menggunakan cara divide and conquer yaitu dengan memecah kemudian menyelesaikan setiap bagian, kemudian menggabungkannya kembali.
Pertama data dipecah menjadi 2 bagian dimana bagian pertama merupakan setengah (jika data genap) atau setengah minus satu (jika data ganjil) dari seluruh data, kemudian dilakukan pemecahan kembali untuk masing-masing blok sampai hanya terdiri dari satu data tiap blok.
Setelah itu, data digabungkan kembali dengan membandingkan pada blok yang sama apakah data pertama lebih besar daripada data ke-tengah+1, jika iya, maka data ke-tengah+1 akan dipindah sebagai data pertama, kemudian data ke-pertama sampai ke-tengah digeser menjadi data kedua sampai ke-tengah+1, demikian seterusnya, selanjutnya data tersebut dibandingkan menjadi 2 kubu kembali dan dibandingkan antara kubu kanan dan kiri, nilai data terkecil akan akan masuk terlebih dahulu pada tempat list terurut dilanjutnya hingga yang terbesar. Sehingga metode merge sort merupakan metode yang membutuhkan fungsi rekursi untuk penyelesaiannya.
Untuk lebih jelasnya, perhatikan penerrapannya di dalam Python di bawah ini.
Output :
Output :
Cukup panjang ya 😃 ? Jika anda sudah memahaminya pasti anda bisa mempersingkatnya atau bahkan memodifikasinya. Selanjutnya kita akan membahas metode sorting yang kedua yaitu, Shell sort.
Shell Sort
Algoritma Shell sort dapat dikatakan bentuk perbaikan dari algoritma Selection short. Dengan demikian, pada dasarnya pengurutan Shell juga bisa menggunakan algoritma Selection sort yang telah dimodifikasi. Namun, dalam algoritma pengurutan Shell, elemen - elemen list dibagi menjadi beberapa sub-list. Selanjutnya, seiap sub-list tersebut diurutkan menggunakan algoritma Selection sort. Hal ini bertujuan untuk mengurangi banyaknya proses pergeseran elemen yang terjadi di dalam algoritma Selection sort.
Mekanisme Shell sort sebagai berikut. Pada pengurutan data kita terlebih dahulu harus membuat sub list – sub list yang didasarkan pada jarak antar data yang ditentukan. Jarak yang telah ditetukan biasanya dilambangakan dengan k. Biasanya jarak yang paling digunakan pada Shell sort saat melakukan pengurutan data yaitu k5, k3. dan k1. Artinya, dari data yang akan ditentukan atau ditukar dengan data yang lain kira-kira berjarak 5, 3 atau 1 data saja.
Perhatikan implementasi algoritma ke dalam Python di bawah ini.
Okey sobat kodingers itulah sedikit pembahasan mengenai Shell sort. Sekian untuk postingan mengenai struktur data : sorting. Dalam waktu dekat, kita akan kembali memposting materi baru. Materi apakah itu? Tunggu saja 😃 see yaa guys have a nice day 😄.
0 komentar:
Posting Komentar