Struktur Data : Merge Sort & Shel Sort (Pyhton) - Part 3 (End)

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 :

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 😄.

Read More

Struktur Data : Insertion Sort & Quick Sort (Pyhton) - Part 2

Haloo sobat kodingers, kembali lagi bersama saya 😅 tentunya dengan postingan baru, materi baru dan juga semangat yang selalu harus baru 😃. Postingan yang lalu kita telah membahas 2 jenis sorting yaitu Bubbel sort dan Selection sort. Nah pada postingan kali ini kita akan membahas 2 sorting baru yaitu Insertion sort dan Quick sort. Are you ready? Yuk langsung saja kita bahas 😃.

Insertion Sort

Insertion Sort merupakan metode pengurutan data yang cara kerjanya menyisipkan suatu elemen list pada posisi yang sesuai. Posisi tersebut dicari dengan cara membandingkan suatu elemen dengan elemen-elemen sebelumnya. Pada algoritma ini, mula-mula elemen pertama dianggap telah berada pada posisi yang tepat. Selanjutnya, elemen kedua akan dibandingkan dengan elemen pertama. Jika elemen pertama lebih besar dari elemen kedua, maka elemen pertama akan digeser ke kanan menjadi elemen kedua dan elemen kedua sebelumnya akan disisiplan pada posisi pertama.

Setelah itu, elemen ketiga akan dibandingkan dengan elemen kedua dan pertama. Jika elemen kedua lebih besar dari elemen ketiga, maka elemen kedua akan digeser ke kanan. Selanjutnya, elemen ketiga akan dibandingkan lagi dengan elemen pertama. Jika elemen pertama lebih besar dari elemen ketiga, maka elemen pertama juga akan digeser ke kanan dan elemen ketiga akan disisipkan pada posisi pertama. Jika elemen pertama lebih kecil dari elemen ketiga, maka elemen ketiga akan disisipkan pada posisi kedua.

Demikian seterusnya sampai seluruh elemen di dalam list terproses. Untuk lebih mudah dalam memahami proses di dalam algoritma Insertion sort, perhatikan implementasinya dalam Python :

Itulah sedikit ulasan mengenai Insertion sort atau pengurutan sisipan. Selanjutnya kita akan bahas sort kedua pada postingan kali ini yaitu Quick sort.

Quick Sort

 Quick sort adalah algoritma sorting yang berdasarkan pembandingan dengan metoda divide-and-conqueror. Sesuai dengan namanya quick yang berarti cepat, sehingga berarti algoritma quick sort mengurutkan data dalam suatu list dengan sangat cepat. Pengurutan Quick sort ditentukan oleh pivot. Dan pivot tersebut bisa berada di depan , berada di belakang atau berada di tengah. Namun algoritma ini sangat komplex dan diproses secara rekursif.

Seperti yang sudah dijelaskan di atas, quick sort merupakan algoritma yang mengurutkan data dengan cara membagi. Pertama quick sort membagi list yang besar menjadi dua buah sub list atau dua kubu yang lebih kecil (kubu element kecil dan kubu element besar). Kemudian quick list akan menyortir sub list itu secara rekursif.

Adapun langkah-langkah pengerjaannya seperti berikut:
Pertama, mengambil sebuah elemen, yang disebut dengan pivot, pada sebuah daftar. Kedua, mengurutkan kembali sebuah list sehingga elemen dengan nilai yang kecil dari pivot berada sebelum pivot, sedangkan seluruh element yang memiliki nilai yang lebih besar dari pivot berada setelahnya (nilai yang sama dapat berada pada pivot setelahnya). Setelah pemisahan, pivot berada pada posisi akhirnya. Operasi ini disebut Partition. Yang terakhir sub list kemudian disortir secara recursif dari elemen yang lebih kecil dan sub list dari elemen yang lebih besar. 
Bingung 😂? Langsung saja kita terapkan pada Python :

Di atas merupakan contoh penerapan quick sort sederhana. Penerapan yang lebih rumit dan lebih panjangnya seperti di bawah ini :

Bagaimana? Sudah mengerti? Jangan lelah untuk mencoba ya 😂. Itulah postingan untuk kita kali ini, semoga bermanfaat. Nantikan postingan selanjutnya tentang 2 sort yang baru. Apakah itu? Tunggu saja ya 😂.

Read More

Struktur Data : Bubble Sort & Selection Sort (Pyhton) - Part 1

Hello sobat codingers jumpa lagi dengan saya 😂. Pada postingan kali ini kita akan membahas Sorting. Sebelum kita bahas lebih lanjut, ada baiknya kita mengetahui apasih sorting itu? Apa fungsinya? Dan ada berapa macam sorting? Itulah kira-kira yang akan kita bahas pada postingan kali ini.

Dalam dunia pemrograman, sorting adalah bagian yang tidak bisa dikesampingkan. Fungsi utama dari sorting itu sendiri adalah sebuah metode untuk mengurutkan data, baik itu dari terendah ataupun tertinggi.  Yang secara tidak langsung akan menjadikan data lebih terstruktur, rapi dan teratur. Ada banyak algoritma sorting untuk mengurutkan data, seperti : insertion sort, selection sort, merge sort, quick sort, bubble sort, shell sort dan masih banyak lagi. Namun pada artikel ini, saya hanya akan membahas Bubble sort dan Selection sort saja dengan menggunakan bahasa pemrograman Python.

Bubble Sort

Pengurutan gelembung atau Bubble sort merupakan metode sorting yang bisa dikatakan prosesnya sederhana. Proses pengurutannya dilakukan dengan cara membandingkan masing-masing nilai dalam suatu list secara berpasangan, kemudian pertukaran akan terjadi jika nilai data ke-[i] lebih kecil daripada data ke-[i-1], sebaliknya jika nilai data ke-[i] lebih besar daripada nilai data ke-[i-1] maka pertukaran tidak akan terjadi dan terus melanjutkan perbandingannya dengan nilai data ke-[i] yang menjadi patokannya.

Proses ini akan berulang sampai list ke-n secara berurutan, hingga nilai yang ada dalam list semuanya terurut atau dengan kata lain tidak ada lagi nilai yang dapat ditukar. Berikut algoritma dan penerapannya dalam Python :

Bagaimana? Sudah paham atau belum 😃 ? Langsung dicoba sendiri saja 👌. Kita akan lanjut membahas sort yang kedua yaitu selection sort.

Selection sort adalah metode pencarian yang membandingkan elemen list yang pertama dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen yang sekarang maka ditandai posisinya dan kemudian akan saling bertukar tempat.

Dengan kata lain metode ini memiliki konsep memilih data yang maksimum/minimum dari suatu kumpulan data sampai list ke-n, lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data maksimum/minimum yang diperoleh, diasingkan ke tempat lain, dan tidak diikutsertakan pada proses pencarian data maksimum/minimum berikutnya.

Untuk lebih jelasnya langsung saja kita aplikasikan algortima tersebut ke dalam Python.

Itulah algoritma beserta implementasinya ke dalam Python. Bagaimana? Sudah mengerti atau sudah pusing? Codingers sejati tidak mengenal kata "menyerah" cukup "pusing" saja ok 😂. Sekian materi sorting part 1 mengenai Bubble sort dan Selection sort kali ini. Semoga bermanfaat. Nantikan postingan selanjutnya yaa boss 😁. 

Read More

Struktur Data - Python : Linear Serching dan Binary Searching

Hello sahabat codingers, semoga selalu dalam keadaan ceria dan penuh ide-ide cemerlang yaa 😁. Untuk postingan pertama kali ini kita akan membahas sesuai dengan judul enstri di atas, yaitu tentang  linear search dan binary search. Kira-kira apa ya Linear Serching itu? 😞 Binary Searching juga seperti apa? Yuk kita bahas bersama-sama 😊.

Linear Searching

Linear Searching atau sequential search adalah sebuah metode pencaran data dengan cara membandingkan nilai yang dicari dengan nilai dari setiap elemen list , mulai dari elemen pertama (indeks = 0) sampai nilai yang dicari ditemukan atau sampai elemen terakhir (indeks - n). Untuk lebih jelasnya perhatikan gambar animasi di bawah ini.

Misalnya kita memiliki sebuah list, anggap saja list a. Di dalam list itu terdapat beberapa elemen yang terdiri dari beberapa angka acak. Katakanlah 8,5,7,9,2. Kita ingin mencari sebuah angka dari dalam list tersebut, misalnya angka 7. Dan juga kita bisa juga sekaligus mendapatkan informasi pada indeks ke-berapa letak angka tersebut berada, berapa kali iterasinya (proses perulangan saat mencari data tersebut). Bagaimana caranya untuk mengimplementasikannya ke dalam bahasa pemrograman seperti python? Yuk kita simak baik-baik 😂.

Pada contoh di atas, mula-mula kita pastikan posisi awal pencarian berada pada posisi 0 atau pencarian dimulai dari indeks 0. Dan menentukan batas akhir pencarian tersebut dengan len(a) - 1. Metode linear search di atas akan mengembalikan nilai True jika nilai yang dicari ditemukan di dalam list dan False jika tidak ditemukan. Tambahkan pengkondisian untuk memastikan agar proses pencarian dilakukan, jika ditemukan ia akan berhenti, dan jika tidak ditemukan ia akan terus mencari hingga seluruh indeks habis diperiksa. Untuk mengetahui letak indeks angka yang kita cari dan berapa jumlah iterasi yang dilakukan tinggal tambahkan saja iterasi = 0 dan masukan iterasi +=1 di dalam proses looping dan print(posisi) untuk mengetahui letak posisi indeksnya, print(iterasi) untuk mengetahui jumlah iterasinya.

Setelah kita run maka angka 7 yang kita cari terletak pada indeks ke-2 dengan iterasi sebanyak 3 kali. Bagaimana sob? Mudah bukan 😃? Silahkan dicoba dengan mengganti elemen list sesuai dengan keinginan hati kalian atau mungkin ada juga yang penasaran bagaimana list tersebut diisikan dengan data string? Selamat mencoba sob 😂.

Binary Searching

Selanjutnya kita akan membahas binary searching. Binary Search merupakan metode pencarian data dengan membagi 2 atau pencarian dimulai dari indeks list bagian tengah, lalu membandingkannya. Jika bertemu dengan angka yang lebih kecil dari pada yang dicari, maka langsung dibuangnya, begitu seterusnya hingga nilai yang dicari (==)  cocok.  Untuk lebih jelasnya, perhatikan gambar animasi di bawah ini.

Perlu diketahui, data list pada binary search sangatlah mengharuskan urut terlebih dahulu sebelum memulai proses pencarian. Secara logaritmik pencarian binary lebih cepat dibandingkan linear search karena dapat mereduksi jumlah elemen yang dicari sehingga iterasi yang dihasilkannya lebih sedikit. Implementasinya ke dalam python :

Cara kerja algoritma pencarian bagi-dua adalah dengan membagi elemen-elemen list menjadi dua bagian secara berulang. Jika nlai yang dicari (value) lebih kecil dari elemen tengah (alist[middle]), maka proses pencarian dilakukan pada bagian list sebelah kiri. Jika lebih besar, maka pencarian dilakukan pada bagian list sebelah kanan; dengan asumsi bahwa elemen-elemen list terurut secara menaik (ascending). 

Dengan demikian, setelah kalian mengetahui dan mempraktekkan linear search dan binary search tentu sudah mengetahui kelebihan dan kekurangan dari masing - masing kedua metode tersebut. Sekian untuk materi struktur data : linear dan binary searching kali ini. kami akan kembali pada posting selanjutnya dalam waktu dekat 😊. Selamat bercoding ria sob 😃. 

Read More