Perbedaan Shell Sort dan Quick Sort Dalam Algoritma

Sumber : http://herukristanto.blogspot.com/2008/10/metode-pengurutan-data-dan-contoh-array.html

Pengurutan Cangkang (Shell Sort)

Shell sort adalah algoritma dengan kompleksitas algoritma O(n2) dan yang paling efisien dibanding algoritma-algoritma lain dengan kompleksitas algoritma yang sama. Algoritma shell sort lima kali lebih cepat dibandingkan algoritma pengurutan gelembung dan dua kali lebih cepat dibandingkan algoritma pengurutan dengan penyisipan. Dan tentu saja shell sort juga merupakan algoritma yg paling yang paling kompleks dan sulit dipahami.
Algoritma shell sort melakukan pass atau traversal berkali-kali, dan setiap kali pass mengurutkan sejumlah nilai yang sama dengan ukuran set menggunakan insertion sort. Ukuran dari set yang harus diurutkan semakin membesar setiap kali melakukan pass pada tabel, sampai set tersebut mencakup seluruh elemen tabel. Ketika ukuran dari set semakin membesar, sejumlah nilai yang harus diurutkan semakin mengecil. Ini menyebabkan insertion sort yang dijalankan mengalami kasus terbaik dengan kompleksitas algoritma mendekati O(n). Ukuran dari set yang digunakan untuk setiap kali iterasi (iteration) mempunyai efek besar terhadap efisiensi pengurutan.
Tetapi, walaupun tidak se-efisien algoritma merge sort, heap sort, atau quick sort , algoritma shell sort adalah algoritma yang relatif sederhana. Hal ini menjadikan algoritma shell sort adalah pilihan yang baik dan efisien untuk mengurutkan nilai dalam suatu tabel berukuran sedang (mengandung 500-5000 elemen).

Pengurutan Cepat (Quick Sort)
Algoritma quick sort sangat sederhana dalam teori, tetapi sangat sulit untuk  diterjemahkan ke dalam sebuah code karena pengurutan dilakukan dalam sebuah list dan diproses secara rekursif. Algoritma ini terdisi dari empat langkah (yang mana menyerupai merge sort) yaitu :

• Memilih sebuah elemen untuk dijadikan poros atau pivot point (biasanya elemen paling kiri dari tabel).
• Membagi tabel menjadi dua bagian, satu dengan elemen yang lebih besar dari poros, dan satu lagi untuk elemen yang lebih kecil dari poros.
• Mengulang algoritma untuk kedua buah tabel secara rekursif.

Tingkat keefektifan dari algoritma ini dangat bergantung pada elemen yang dipilih menjadi poros. Kasus terburuk terjadi ketika tabel sudah terurut dan elemen terkecil di sebelah kiri menjadi poros. Kasus ini mempunyai kompleksitas algoritma O(n2). Maka dari itu sangat disarankan untuk memilih poros bukan dari elemen paling kiri dari tabel, tetapi dipilih secara random. Selama poros dipilih secara random, algoritma quick sort mempunyai kompleksitas algoritma sebesar O(n log n).
Algoritma quick sort mengurutkan dengan sangat cepat, namun algoritma ini sangat komplex dan diproses secara rekursif. Sangat memungkinkan untuk menulis algoritma yang lebih cepat untuk beberapa kasus khusus, namun untuk kasus umum, sampai saat ini tidak ada yang lebih cepat dibandingkan algoritma quick sort.
Walaupun begitu algoritma quick sort tidak selalu merupakan pilihan yang terbaik. Seperti yang telah disebutkan sebelumnya, algoritma ini dilakukan secara rekursif yang berarti jika dilakukan untuk tabel yang berukuran sangat besar, walaupun cepat, dapat menghabiskan memori yang besar pula. Selain itu, algoritma ini adalah algoritma yang terlalu komplex untuk mengurutkan tabel yang berukuran kecil (hanya puluhan elemen misalnya). Selain itu algoritma quick sort mempunyai tingkat efisiensi yang buruk ketika dioperasikan pada tabel yang hampir terurut atau pada tabel yang terurut menurun.

Sumber: http://dearyechicho.blogspot.com/2008/10/pengurutan-data.html

Selasa, 2008 Oktober 21

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.

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.

Diposkan oleh ecHicHo_dReaMer di 12:32                           

 Dari kedua artikel diatas, dapat saya simpulkan bahwa :

1. Shell sort adalah metode yang mengurutkan sejumlah nilai yang sama pada setiap set dengan menggunakan insertion short pada setiap passnya. Ketika set diurut harus semaikn membesar dan nilainya harus semakin mengecil. Shell sort selalu melakukan pas berkali-kali hingga pass itu mencakup seluruh isi tabel.
2. Quick sort adalah metode yang mengambil data ditengah sebagai pivot dan membaginya menjadi dua bagian lalu menempatkan pivot tersebut sedemikian rupa sehinnga tidak bagian kiri pivot tidak lebih dari pivot itu sendiri. Kemudian mengulang kembali hingga terurut. Tentu saja dalam pelaksanaannya metode Quick sort sangat sulit untuk dipraktekkan.
3. Heap sort adalah metode yang mengurutkan dengan pertama-tama menentukan elemen terbesar dari data yang ada, kemudian meletakkannya pada bagian paling kanan, atau menentukan elemen paling kecil dan kemudian meletakkannya paling kiri, kemudian menyelesaikan struktur data yang disebut heap. Heap terurut jika data paling kanan lebih besar dari data sebelumnya di bagian kiri