Sorting

Pengurutan
Algoritma pengurutan adalah suatu Algoritma untuk meletakkan kumpulan elemen data ke dalam urutan tertentu, berdasarkan satu atau beberapa kunci dalam tiap - tiap elemen pengertian ini dikutip dari Microsoft Bookshelf.


Pada algoritma pengurutan biasanya terdiri dari dua proses yaitu

• Urut naik (ascending) yaitu dari data yang mempunyai nilai paling kecil sampai paling besar  
• Urut turun (descending) yaitu data yang mempunyai nilai paling besar sampai paling kecil 

 salah satu petanyaan yang sering dipikirkan oleh kita adalah mengapa data itu harus diurutkan ? jawaban yang paling sederhana adalah agar dapat mempermuda kita dalam melihat data yang akan dicari . Sebagai contoh pada sebuah kamus , coba bayangkan jika kamus tidak dalam keadaan terurut kita akan sangat sulit dalam mencari data yag ingin kita cari kalaupun dapat kita akan membutuhkan waktu yang sangat lama dalam mencari suatu arti dari data yang ingin kita cari .

Metode yang ada dalam pengurutan sangat banyak tetapi kita akan membahas beberapa metode saja
diantaranya :

• Metode Gelembung ( Bubble Sort)
• Counting Sort
• Insertion Sort
• Shell Sort
• Quick Sort
• selection sort

 Metode Gelembung


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.

Ide dari algoritma ini adalah mengulang proses pembandingan antara tiap-tiap elemen array dan menukarnya apabila urutannya salah. Pembandingan elemen-elemen ini akan terus diulang hingga tidak perlu dilakukan penukaran lagi. Algoritma ini termasuk dalam golongan algoritma comparison sort, karena menggunakan perbandingan dalam operasi antar elemennya
 
Ide perbandingan

1. Algoritma dimulai dari elemen paling awal 
2. 2 elemen awal dari list dibandingkan 
3. jika elemen awal lebih besar dari elemen kedua dilakukan pertukaran 
4. lakukan langkah kedua untuk elemn selanjunya 
5. bila sudah tidak ada pertukaran lagi maka list elemen sudah terurut
6. pengurutan tergatung jenis dari pengurutannya apakah ascending atau descending .

• Ascending Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar
• (kecil ke besar)
• Descending Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut
• (Besar ke kecil)  

Misalkan kita mempunyai sebuah array dengan elemen-elemen “4 2 5 3 9”. Proses yang akan terjadi apabila digunakan algoritma bubblesort adalah sebagai berikut.

Pass pertama

(4 2 5 3 9) menjadi (2 4 5 3 9)

(2 4 5 3 9) menjadi (2 4 5 3 9)

(2 4 5 3 9) menjadi (2 4 3 5 9)

(2 4 3 5 9) menjadi (2 4 3 5 9)

Pass kedua

(2 4 3 5 9) menjadi (2 4 3 5 9)

(2 4 3 5 9) menjadi (2 3 4 5 9)

(2 3 4 5 9) menjadi (2 3 4 5 9)

(2 3 4 5 9) menjadi (2 3 4 5 9)

Pass ketiga

(2 3 4 5 9) menjadi (2 3 4 5 9)

(2 3 4 5 9) menjadi (2 3 4 5 9)

(2 3 4 5 9) menjadi (2 3 4 5 9)

         (2 3 4 5 9) menjadi (2 3 4 5 9)
 kelebihan  dan kekurangan

Algoritma yang simpel. Hal ini dilihat dari proses pengurutan yang hanya menggunakan rekurens dan perbandingan, tanpa penggunaan proses lain. Algoritma pengurutan lain cenderung menggunakan proses lain, misalnya proses partisi pada algoritma Quick Sort. Mudah untuk diubah menjadi kode. Hal ini diakibatkan oleh simpelnya algoritma Bubble Sort, sehingga kecil kemungkinan terjadi kesalahan sintax dalam pembuatan kode.

Definisi terurut terdapat dengan jelas dalam algoritma. Definisi terurut ini adalah tidak adanya satu kalipun swap pada satu kali pass. Berbeda dengan algoritma lain yang seringkali tidak memiliki definisi terurut yang jelas tertera pada algoritmanya, misalnya Quick Sort yang hanya melakukan partisi hingga hanya ada dua buah nilai yang bisa dibandingkan.

Cocok untuk pengurutan data dengan elemen kecil telah terurut. Algoritma Bubble Sort memiliki kondisi best case dengan kompleksitas algoritma

Kekurangan terbesar dari Bubble Sort adalah kompleksitas algoritma yang terlalu besar, baik dalam average case maupun worst case, yaitu O(n2), sehingga seringkali disebut sebagai algoritma primitif, brute-force, maupun algoritma naïf. Untuk 1000 buah data misalnya, maka akan terjadi proses tidak lebih dari satu juta proses perbandingan. Kompleksitas yang besar ini juga seringkali membuat algoritma Bubble Sort sebagai “the general bad algorithm”. Bahkan, diantara algoritma pengurutan lain yang memiliki kompleksitas algoritma O(n2), insertion sort cenderung lebih efisien

lanjut ke pege selanjutnya

Pe