PENGURUTAN DATA

Pengurutan data adalah algoritma yang meletakkan elemen pada sebuah list atau tabel dengan urutan tertentu. Algoritma pengurutan data saat ini telah demikian banyaknya, mulai dari yang sederhana sampai yang kompleks. Untuk saat ini, algoritma heap sort dan quicksort merupakan dua buah algoritma yang dianggap terbaik.

Penggunaan algoritma heap sort dan quick sort dalam pengurutan data berbeda. Perbedaan ini dipengaruhi oleh keunggulan dan kelemahan masing-masing algoritma pengurutan.

Algoritma Heap Sort dan Quick Sort

1. Heap Sort
Heapsort merupakan salah satu bentuk dari selection sort yang memiliki kompleksitas algorima O(n log(n)) yang menggunakan struktur data heap.

Algoritma ini bekerja dengan menentukan elemen terbesar (atau terkecil) dari sebuah daftar elemen, dan diletakkan pada akhir (atau awal) dari daftar tersebut. Heap sort menyelesaikan sebuah pengurutan menggunakan struktur data yang disebut heap.

Heap merupakan sebuah pohon biner hampir lengkap dimana isi dari simpul ayah selalu lebih besar dari isi simpul anak-anaknya sehingga simpul akar selalu merupakan elemen terbesar.

2. Quick Sort
Quick sort adalah algoritma yang menggunakan metode divide and qonquer yaitu dengan mempartisi tabel dengan acuan elemen tabel yang dijadikan sebagai pivot. Tabel dipartisi menjadi tabel dengan elemen pivot, <> pivot, hingga elemen tersebut terurut. pengurutan hanya dengan 1 kali pass saja. Namun sampai saat ini, belum ada algoritma yang mampu untuk mencapai keadaan ini.

Kompleksitas waktu dari kedua algoritma ini, secara rata-rata adalah sama, yaitu O(n log n). Saat ini, kompleksitas waktu O(n log n) merupakan kompleksitas algoritma sorting yang paling mendekati algoritma pengurutan ideal yaitu O(n). Hal inilah yang menyebabkan kedua buah algoritma ini dipandang sebagai yang terbaik saat ini.

Walaupun memiliki kompleksitas algoritma yang sama yaitu O(n log n), dalam praktiknya, algoritma quicksort memiliki kecepatan pemrosesan yang lebih baik dari heap sort. Penyebabnya adalah algoritma heapsort membutuhkan tahapan-tahapan yang lebih banyak daripada quicksort.

Namun untuk quicksort, pada kasus terburuknya memiliki kompleksitas O(n2). Sedangkan, pada heap sort, kompleksitas untuk kasus terburuknya sama dengan kasus rata-rata, yaitu O(n log n). Jadi pada kasus terburuk, algoritma heap sort lebih baik daripada algoritma quicksort.

Klasifikasi AlgoritmaPengurutan (sorting)

* Exchange Sort : Melakukan pembandingan antar data, dan melakukan pertukaran apabila urutan yang didapat belum sesuai. Contohnya : Bubble sort, Cocktail sort, Comb sort, Gnomesort, Quicksort.

* Selection Sort : Mencari elemen yang tepat untuk diletakkan diposisi yang telah diketahui, dan meletakkannyadi posisi tersebut setelah data tersebutditemukan. Contohnya :Selection sort, Heapsort, Smoothsort, Strand sort

* Insertion Sort : Mencari tempat yang tepat untuk suatu elemen data yang telah diketahui ke dalam sub kumpulan data yang telah terurut, kemudian melakukan penyisipan (insertion) data di tempat yang tepat tersebut. Contohnya adalah : Insertion sor, Shell sort, Tree sort, Library sort, Patience sorting.

* Merge Sort : Data dibagi menjadi subkumpulan-subkumpulan yang kemudian subkumpulan tersebut diurutkan secara terpisah, dan kemudian digabungkan kembali dengan metode merging. Algoritma ini melakukan metode pengurutan merge sort juga untuk mengurutkan sub kumpulan data tersebut, atau dengan kata lain, pengurutan dilakukan secara rekursif. Contohnya adalah : Merge sort.

* Non-Comparison Sort : Proses pengurutan data yang dilakukan algoritma ini tidak terdapat pembandingan antar data, data diurutkan sesuai dengan pigeon hole principle. Contohnya adalah : Radix sort, Bucket sort, Counting sort, Pigeonhole sort, Tally sort.

Ide Dasar
Ide dasar dari metode Radix sort ini adalah mengkategorikan data-data menjadi sub kumpulan sub kumpulan data sesuai dengan nilai radix-nya, mengkonkatenasinya, kemudian mengkategorikannya kembali berdasar nilai radix lainnya.

Algoritma Bubble Sort

1. Setiap pasangan data: x[j] dengan x[j-1], untuk semua i=1,...,n-1 harus memenuhi keterurutan, yaitu x[j] > x[j-1].
2. Apabila tidak memenuhi maka posisi kedua data harus ditukar.
3. Untuk pemrograman konvensional maka pemeriksaan-pemeriksaan pasangan tersebutharus dilakukan satu demi satu, misalnya oleh bubble-sort dilakukan dari kanan ke kiri serta di dalam sejumlah iterasi.
4. Keuntungan lain dari algoritma ini adalah dapat dijalankan dengan cukup cepat dan efisien untuk mengurutkan list yang urutannya sudah hampir benar.
5. Selain kasus terbaik tersebut, komleksitas untuk algoritma ini adalah O(n²), karenanya algoritma ini termasuk sangat tidak efisien untuk dilakukan, apalagi jika pengurutan dilakukan terhadap elemen yang banyak jumlahnya. Biasanya bubble sort digunakan untuk mengenalkan konsep dari sorting algoritma pada pendidikan komputer karena idenya yang cukup sederhana.

* Metode Selection Short
Metode selection sort merupakan perbaikan dari metode bubble sort dengan mengurangi jumlah perbandingan. Selection sort merupakan metode pengurutan yang mencari nilai data terbesar atau terkecil dan kemudian menempatkannya pada posisi yang sebenarnya, dimulai dari data diposisi 0 hingga data diposisi N-1.
* Metode Insertion Short
Metode insertion sort adalah metode pengurutan yang biasa dipakai oleh pemain kartu dalam mengurutkan kartunya, yaitu menyisipkan kartu dengan nilai yang lebih kecil ke posisi sebelum kartu pembandingnya. Selection Sort merupakan kombinasi antara sorting dan searching. Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar
kan dipertukarkan ke posisi yang tepat di dalam array. Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]). Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.Tehnik pengurutan dgn cara pemilihan elemen atau proses kerja dgnmemilih elemen data terkecil utk kemudian dibandingkan & ditukarkan dgn elemen pd data awal, dst s/d seluruh elemen shg akan menghasilkan pola data yg telah disort.

Kelebihan dan kekurangan Selection Sort:

1. Kompleksitas selection sort relatif lebih kecil
2. Mudah menggabungkannya kembali, tetapi sulit membagi masalah
3. Membutuhkan method tambahan.

* Metode Insertion Sort
Prinsip dasar Insertion adalah secara berulangulang menyisipkan / memasukan setiap elemen. ke dlm posisinya / tempatnya yg benar. Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya. Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya. Pada penyi sipan elemen, maka elemen-elemen lain akan bergeser ke belakang.

* Quick Short : Quick sort banyak digunakan utk proses sorting, karena merupakan proses sorting yang umum digunakan, mudah untuk diimplementasikan, prosesnya sangat cepat.

Aturan Quick Sort:

1. Select, pertama kita pilih elemen yang ditengah sebagai pivot, misalkan X.
2. Partition, kemudian semua elemen tersebut disusun dengan menempatkanX mpada posisi j sedemikian rupa sehingga elemen disebelah kiri1 lebih <> X.
3. Rekursif, kemudian proses diulang untuk bagian kiri dan kanan elemenX dengan cara yg sama dengan langkah 1 sampai kondisi terurut

* Metode Heap Short adalah binary tree dengan menggunakan tree , dimana mempunyai aturan-aturan sebagai berikut :

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