SEKILAS TENTANG METODE-METODE SORTING

  Pengertian dan Metode Sorting dalam Pemrograman

Nama        : Emirza Mahendra

NPM         : 53414559

Kelas       : 1IA17

Mata Kuliah : Algoritma dan Pemrograman 1A

Dosen       : Kunto Bayu A, S.T.

Dalam Ilmu Komputer, Algoritma Sorting merupakan algoritma yang menempatkan elemen list pada urutan tertentu. Urutan yang paling sering digunakan ialah urutan numerikal dan urutan lexicographical (urutan alfabet). Sorting yang efisien sangat dibutuhkan untuk mengoptimisasi penggunaan dari algoritma lain seperti pencarian dan penggabungan yang membutuhkan list terurut untuk berjalan dengan sempurna, yang juga sering digunakan untuk Canonicalisisasi (membakukan) data dan menghasilkan output yang dapat dibaca manusia.

A. PENGERTIAN

Sorting berarti proses pengurutan. Sorting atau pengurutan data adalah proses yang sering harus dilakukan dalam pengolahan data. Sort dalam hal ini diartikan mengurutkan data yang berada dalam suatu tempat penyimpanan, dengan urutan tertentu baik urut menaik (ascending) dari nilai terkecil sampai dengan nilai terbesar, atau urut menurun (descending) dari nilai terbesar sampai dengan nilai terkecil.

B. METODE-METODE SORTING

 

Berikut adalah beberapa jenis dari metode sorting, antara lain:

• Bubble Sort atau Exchange Sort
  Ide dari Bubble sort adalah gelembung air yang akan “mengapung” untuk table yang terurut menaik (ascending). Elemen bernilai kecil akan “diapungkan” (ke indeks terkecil), artinya diangkat ke “atas” (indeks terkecil) melalui pertukaran. Karena algoritma ini melakukan pengurutan dengan cara membandingkan elemen-elemen data satu sama lain, maka bubble sort termasuk ke dalam jenis algoritma comparison-based sorting.
  
  
  Metode gelembung (bubble sort) sering juga disebut dengan metode penukaran (exchange sort) adalah metode yang mengurutkan data dengan cara membandingkan masing-masing elemen, kemudian melakukan penukaran bila perlu. Metode ini mudah dipahami dan diprogram, tetapi bila dibandingkan dengan metode lain yang kita pelajari, metode ini merupakan metode yang paling tidak efisien.

http://upload.wikimedia.org/wikipedia/commons/c/c8/Bubble-sort-example-300px.gif

• Selection Sort
  Algoritma Selection sort memilih elemen maksimum atau minimum array, lalu menempatkan elemen maksimum atau minimum itu pada awal atau akhir array (tergantung pada urutannya ascending atau descending). Selanjutnya elemen tersebut tidak disertakan pada proses selanjutnya. Karena setiap kali selection sort harus membandingkan elemen-elemen data, algoritma ini termasuk dalam comparison-based sorting.
  Terdapat dua pendekatan dalam metode pengurutan dengan Selection Sort :
  
  • Algoritma pengurutan maksimum (maximum selection sort), yaitu memilih elemen maksimum sebagai basis pengurutan. 
  • Algoritma pengurutan minimum (minimum selection sort), yaitu memilih elemen minimum sebagai basis pengurutan.

 

http://upload.wikimedia.org/wikipedia/commons/9/94/Selection-Sort-Animation.gif

• 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.
  
  Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan dan yang sudah diurutkan. Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.

http://upload.wikimedia.org/wikipedia/commons/0/0f/Insertion-sort-example-300px.gif

• Shell Sort
  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.
  
  Pada langkah pertama, kita ambil elemen pertama dan kita bandingkan dan kita bandingkan dengan elemen pada jarak tertentu dari elemen pertama tersebut. Kemudain elemen kedua kita bandingkan dengan elemen lain dengan jarak yang sama seperti jarak yang sama seperti diatas. Demikian seterusnya sampai seluruh elemen dibandingkan. Pada langkah kedua proses diulang dengan langkah yang lebih kecil, pada langkah ketiga jarak tersebut diperkecil lagi seluruh proses dihentikan jika jarak sudah sama dengan satu. 

http://upload.wikimedia.org/wikipedia/en/2/26/Shellsort.svg

• Merge Sort
  MergeSort adalah algoritma yang berdasarkan strategi divide-and-conquer. Algoritma ini  tediri dari dua bagian utama, yaitu bagian pembagian list menjadi sublist-sublist yang lebih kecil dan bagian sort (pengurutan) dan merge (penggabungan) pada sublist-sublist tersebut.
  • Divide:  membagi masalah menjadi beberapa submasalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama), 
  • Conquer: memecahkan (menyelesaikan) masing-masing submasalah (secara  rekursif), dan 
  • Combine: mengabungkan solusi masing-masing submasalah sehingga membentuk solusi masalah semula.
    
  Metode penggabungan biasanya digunakan pada pengurutan berkas. Prinsip dari metode penggabungan sebagai berikut : mula-mula diberikan dua kumpulan data yang sudah dalam keadaan urut. Kedua kumpulan data tersebut harus dijadikan satu table sehingga dalam keadaan urut.

 

http://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif

• Quick Sort
  Metode Quick sering disebut juga metode partisi (partition exchange sort). Metode ini diperkenalkan pertama kali oleh C.A.R. Hoare pada tahun 1962. Untuk mempertinggi efektifitas dari metode ini, digunakan teknik menukarkan dua elemen dengan jarak yang cukup besar.
  
  Dasar strateginya adalah “memecah dan menguasai”. Quick sort dimulai dengan menscan daftar yang disortir untuk nilai median. Nilai ini, yang disebut tumpuan (pivot), kemudian dipindahkan ke satu sisi pada daftar dan butir-butir yang nilainya lebih besar dari tumpuan di pindahkan ke sisi lain.

http://upload.wikimedia.org/wikipedia/commons/9/9c/Quicksort-example.gif

• Heap Sort
  Metode heap sort adalah metode dari pengembangan tree. Metode Heap sort memiliki kecepatan O(N log N). 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 :
  
  1. 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. 
  2. Heap dalam kondisi terurut apabila left child <> parent. 
  3. Penambahan kunci diletakkan pada posisi terakhir dari level dan disebelah kanan child yg terakhir, kemudian diurutkan dengan cara upheap. 
  4. Bila menghapus heap dgn mengambil kunci pada parent di level 1 kemudian digantikan posisi kunci terakhir, selanjutnya disort kembali metode downheap.  
  5. Dalam langkah-langkahnya heap sort terbagi menjadi 2 langkah yaitu insert_heap dan build_heap.

 

http://upload.wikimedia.org/wikipedia/commons/4/4d/Heapsort-example.gif

• Radix Sort
  
  Radix Sort merupakan algoritma pengurutan yang ajaib yang mana mengatur pengurutan nilainya tanpa melakukan beberapa perbandingan pada data yang dimasukkan.
  
  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.
  
  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.

• Bucket Sort
  Bucket sort adalah algoritma sorting yang bekerja dengan partisi array ke dalam jumlah terbatas sort. Setiap kotak ini kemudian diurutkan secara individual, baik menggunakan algoritma sorting yang berbeda, atau dengan rekursif menerapkan algoritma bucket sort. Sebuah variasi dari metode ini disebut semacam hitungan tunggal buffered lebih cepat dari jenis cepat dan membutuhkan waktu sekitar waktu yang sama untuk berjalan pada set data.

• Counting Sort
  Counting Sort adalah salah satu metode mengurutkan data yang dikenal. Ide dasarnya adalah seperti kita melakukan perhitungan pemilu yaitu dengan mencatat frekuensi atau banyaknya kemunculan data. Namun metode ini hanya cocok digunakan bila data yang digunakan bertipe integer dan dibatasi pada range tertentu.

Sumber Referensi :

http://id.wikipedia.org/wiki/Algoritma_sorting

http://thenurulazizah.wordpress.com/artikel-2/13-metode-sorting/

http://lunarphue.wordpress.com/asd/macam-macam-sorting/ 

http://agusjembung.blogspot.com/2012/02/macam-macam-sorting.html

http://lecturer.eepis-its.edu/~entin/Struktur%20Data%20&%20Algoritma/buku/Data%20Structure%20-%20Bab%206.pdf

http://hack.spyrozone.net/0221_Struktur_Data_Sorting_Method_by_y3ppy_WWW.SPYROZONE.NET_07_Oktober_2007.html

http://kael9001.blogspot.com/2013/02/bubble-sort.html

http://maryambadoe.blogspot.com/2012/06/materi-algoritma.html