Helo sobat, pada kesempatan kali ini kita akan membahas salah satu metode pemrograman, yaitu sorting.. dimana metode sorting digunakan untuk pengurutan data, pada artikel kali ini kita akan membahas macam-macam metode sorting.
sebelum kita membahas macam-macam metode sorting, mari kita membahas apa itu sorting, langsung aja kalian baca semoga artikel ini dapat bermanfaat untuk menambah wawasan kita semua.
Apa itu Sorting?
Sorting adalah sebuah metode untuk pengurutan data, misalnya dari data yang terbesar ke data yang terkecil. Dengan cara program yang dibuat harus dapat membandingkan antar data yang di input.
Artinya jika ada deretan data, maka data yang pertama akan membandingkan dengan data yang kedua. Jika data yang pertama lebih besar dari pada data yang kedua maka data yang pertama akan bertukar posisi dengan data yang kedua, begitu seterusnya sampai benar-benar data terurut dari yang terbesar hingga yang terkecil.
Metode sorting sangat banyak dan berkembang ada Bubble sort, Selection Sort, Insertion sort, Merge sort, Quick sort. Metode-metode ini menggunakan caranya sendiri untuk membandingkan, memeriksa dan menukar posisi data. Namun tidak semua metode sorting ini efektif. Karena metode sorting yang paling efektif adalah ketika metode tersebut dapat melakukan pengurutan data dengan cepat dan tidak memerlukan banyak memori.
METODE SORTING
Seringkali perancang program perlu mengurutkan sekumpulan data yang dimiliki untuk memudahkan pemrosesan selanjutnya terhadap data tersebut. Pengurutan adalah sebuah algoritma dasar yang sering diperlukan dalam pembuatan program. Berbagai algoritma pengurutan telah diciptakan dan dapat digunakan. Pemahaman tentang beberapa algoritma pengurutan dasar perlu diketahui, termasuk cara penggunaannya dalam program.
Terdapat dua macam pengurutan:
Pengurutan internal (internal sort), yaitu pengurutan terhadap sekumpulan data yang disimpan dalam media internal komputer yang dapat diakses setiap elemennya secara langsung. Dapat dikatakan sebagai pengurutan tabel.
Pengurutan eksternal (external sort), yaitu pengurutan data yang disimpan dalam memori sekunder, biasanya data bervolume besar sehingga tidak mampu untuk dimuat semuanya dalam memori.
Dalam courseware ini, hanya akan dibahas algoritma pengurutan internal, dengan data berada dalam array satu dimensi. Algoritma pengurutan internal yang utama antara lain:
1.Bubble Sort
2.Selection Sort
3.Insertion Sort
4.Shell Sort
5.Merge Sort
6.Radix Sort
7.Quick Sort
8.Heap Sort
BUBBLE SORT
Bubble sort (metode gelembung) adalah metode atau algoritma pengurutan dengan cara melakukan penukaran data dengan tempat disebelahnya jika data sebelum lebih besar dari pada data sesudahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan, atau telah terurut dengan benar.Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci atau data akan dengan lambat menggelembung atau membandingan data ke posisinya yang tepat.
Metode ini mudah dipahami dan diprogram, tetapi bila dibandingkan dengan metode lain yang kita pelajari, metode ini merupakan metode yang paling tidak efisien karena memiliki banyak pertukara sehingga memerlukan pengalokasian memori yang besar untuk menjalankan metode ini.
SELECTION SORT
Selection Sort berbeda dengan Bubble sort. Selection Sort pada dasarnya memilih data yang akan diurutkan menjadi dua bagian, yaitu bagaian yang sudah diurutkan dan bagian yang belum di urutkan.
Langkah pertama dicari data terkecil dari data pertama sampai data terakhir. Kemudian data terkecil ditukar dengan data pertama. Dengan demikian, data pertama sekarang mempunyai nilai paling kecil dibanding data yang lain. Langkah kedua, data terkecil kita cari mulai dari data kedua sampai terakhir. Data terkecil yang kita peroleh ditukar dengan data kedua dan demikian seterusnya sampai semua elemen dalam keadaan terurutkan. Metode ini lebih efektif dari pada metode bubble karena tidak memerlukan banyak pertukaran dan pengalokasian memori.
MERGE SORT
Merge sort merupakan algoritma pengurutan dalam ilmu komputer yang dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar. Algoritma ini ditemukan oleh John von Neumann pada tahun 1945.
Prinsip utama yang diimplementasikan pada algoritma merge-sort seringkali disebut sebagai pecah-belah dan taklukkan (bahasa Inggris: divide and conquer). Cara kerja algoritma merge sort adalah membagi larik data yang diberikan menjadi dua bagian yang lebih kecil. Kedua larik yang baru tersebut kemudian akan diurutkan secara terpisah. Setelah kedua buah list tersusun, maka akan dibentuk larik baru sebagai hasil penggabungan dari dua buah larik sebelumnya. Menurut keefektifannya, alogaritma ini bekerja dengan tingkat keefektifan.
QUICK SORT
Quicksort merupakan salah satu metode pengurutan data yang tercepat. Metode ini sebenarnya dapat dilakukan terhadap kumpulan data yang dikumpulkan di array maupun linkelist, namun saya akan memberikan ilmu saya yang sedikit dari pengurutan data pada linkedlist melalui metode ini.
Logikanya adalah pada awalnya kita akan memilih pivot sebagai data yang hendak kita pindahkan posisinya, pada program saya saya mengambil data pertama. Kemudian urut dari kanan ke kiri kita mencari nilai yang lebih kecil dari data pivot untuk kita tukar posisinya dengan pivot, kemudian urut dari kiri ke kanan kita cari nilai yang lebih besar dari pivot untuk kita tukar dengan pivot, terus kita lakukan hingga tidak ada lagi yang lebih kecil di sebelah kiri pivot dan lebih besar di sebelah kanan pivot.
Kemudian dari pivot itu kita bagi dua kumpulan data tersebut menjadi sebelah kiri pivot dan sebelah kanan pivot, untuk kemudian kita lakukan hal serupa dengan kumpulan data sebelumnya yang merupakan gabungan dua kumpulan data tersebut.
Logikanya memang sedikit rumit. Perulangan yang dilakukan tidak dapat dilakukan dengan perulangan biasa sehingga menggunakan metode rekursif yang akan berhenti apabila data telah urut.
INSERTION SORT
Insertion sort adalah sebuah algoritma pengurutan yang membandingkan dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan. Karena algoritma ini bekerja dengan membandingkan elemen-elemen data yang akan diurutkan, algoritma ini termasuk pula dalam comparison-based sort.
Ide dasar dari algoritma Insertion Sort ini adalah mencari tempat yang “tepat” untuk setiap elemen array, dengan cara sequential search. Proses ini kemudian menyisipkan sebuah elemen array yang diproses ke tempatnya yang seharusnya. Proses dilakukan sebanyak N-1 tahapan (dalam sorting disebut sebagai “pass“), dengan indeks dimulai dari 0.
Proses pengurutan dengan menggunakan algoritma Insertion Sort dilakukan dengan cara membandingkan data ke-i (dimana i dimulai dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuai dengan posisi yang seharusnya.
SHELL SORT (METODE SHELL)
Metode ini disebut juga dengan metode pertambahan menurun (diminishing increment). Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959, sehingga sering disebut dengan Metode Shell Sort. Metode ini mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu, kemudian dilakukan penukaran bila diperlukan. Proses pengurutan dengan metode Shell dapat dijelaskan sebagai berikut :
Pertama-tama adalah menentukan jarak mula-mula dari data yang akan dibandingkan, yaitu N / 2. Data pertama dibandingkan dengan data dengan jarak N / 2. Apabila data pertama lebih besar dari data ke N / 2 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 2. Demikian seterusnya sampai seluruh data dibandingkan sehingga semua data ke-j selalu lebih kecil daripada data ke-(j + N / 2).
Pada proses berikutnya, digunakan jarak (N / 2) / 2 atau N / 4. Data pertama dibandingkan dengan data dengan jarak N / 4. Apabila data pertama lebih besar dari data ke N / 4 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 4. Demikianlah seterusnya hingga seluruh data dibandingkan sehingga semua data ke-j lebih kecil daripada data ke-(j + N / 4).
Pada proses berikutnya, digunakan jarak (N / 4) / 2 atau N / 8. Demikian seterusnya sampai jarak yang digunakan adalah 1.
RADIX SORT
Radix Sort adalah metode sorting tanpa pembandingan dengan kata lain, sorting Non-Comparasion sort dimana dalam prosesnya tidak melakukan perbandingan antar data. Secara umum yang proses yang dilakukan dalam metode ini adalah mengklasifikasikan data sesuai dengan kategori terurut yang tertentu dan dalam tiap kategorinya dilakukan pengklasifikasian lagi dan seterusnya sesuai dengan kebutuhan. Dan kemudian subkategori-subkategori tersebut digabungkan kembali, yang secara dilakukan hanya dengan metode sederhana concatenation.
Apa itu Radix Sort??? Radix Sort merupakan algoritma pengurutan yang ajaib yang mana mengatur pengurutan nilainya tanpa melakukan beberapa perbandingan pada data yang dimasukkan. Kata radix bermakna harafiah posisi dalam angka [1]. Di mana sederhananya, dalam representasi desimal, radix adalah digitnya. Dalam implementasinya, Radix Sort merupakan algoritma pengurutan yang cepat, mudah, dan sangat efektif. Namun banyak orang yang berpikir bahwa algoritma ini memiliki banyak batasan di mana untuk kasus-kasus tertentu tidak dapat dilakukan dengan algoritma ini, seperti pengurutan bilangan pecahan dan bilangan negatif,
Berdasarkan urutan pemrosesan radixnya, Radix Sort terbagi 2 macam, yaitu: LSD (Least Significant Digit), di mana pemrosesan dimulai dari radix yang paling tidak signifikan. dan MSD (Most Significant Digit), di mana pemrosesan dimulai dari radix yang paling signifikan.
Proses dasar Radix Sort adalah mengkategorikan data-data menjadi subkumpulan-subkumpulan data sesuai dengan nilai radix-nya, mengkonkatenasinya, kemudian mengkategorikannya kembali berdasar nilai radix lainnya.
HEAP SORT
Metode heap sort adalah metode dari pengembangan tree. Heap sort memiliki kecepatan O(NlogN). Heap sort melakukan suatu pengurutan menggunakan suatu struktur data yang di sebut heap. Heap memiliki kompleksitas yang besar dalam pembuatan kodenya, tetapi heap sort mampu mengurutkan data-data yang sangat banyak dengan waktu yang cepat. Dalam sorting biasanya mempunyai sebuah aturan, berikut adalah aturan dari heap sort :
Untuk mengisikan heap dimulai dari level 1 sampai ke level dibawahnya, bila dalam level yang sama semua kunci heap belum terisi maka tidak boleh mengisi dibawahnya. Heap dlm kondisi terurut apabila left child <> parent.
Penambahan kunci diletakkan pada posisi terakhir dari level dan disebelah kanan child yg terakhir, kemudian diurutkan dengan cara upheap. Bila menghapus heap dgn mengambil kunci pada parent di level 1 kemudian digantikan posisi kunci terakhir, selanjutnya disort kembali metode downheap.
Berikut adalah langkah-langkahnya dari metode heap sort :
Dalam langkah-langkahnya heap sort terbagi menjadi 2 langkah yaitu insert_heap dan build_heap,
Insert_heap :
Pada bagian ini bertujuan untuk penghapusan suatu simpul pada heap tree. pemilihan sebuah simpul untuk ditempatkan di posisi yang lebih atas, dan menjaga tree tersebut tetap sebuah heaptree.
Berikut langkahnya :
Setiap simpul yang dihapus(low) dicari anaknya yang memiliki kunci terbesar/terkecil(large) Anak dengan kunci yang lebih besar dipromosikan ke tempat simpul yang di hapus.
Langkah 1 dan 2 akan di lakukan berulang kali sampai simpul yang dihapus tidak punya anak lagi atau simpul yang ingin dipromosikan lebih besar/kecil daripada anak dari simpul yang dihapus yang memiliki kunci terbesar/terkecil.
Build Heap :
Pada bagian ini kita akan merapikan data-data yang telah acak tadi, sehingga membentuk heap yang sempurna. kita dapat menggunakan fungsi insert_heap untuk memasukkan setiap masukan ke bagian heap yang terdiri dari semua masukan yang masuk. Sehingga jadilah heap yang sempurna.
Sekian pembahasan mengenai metode pencarian sorting, semooga artikel ini dapat menambah wawasan kita semua. Terimakasih atas kunjungan kalian semua.
