Metode Quick Sort

Metode Quick Sort

Nama : Irfan Fadhil

NPM  : 55414434

Kelas  : 1IA17

Mata Kuliah : Algoritma & Pemrograman 1A

Dosen : Kunto Bayu A, ST.

Quick Sort bekerja dengan cara membandingkan suatu elemen (pivot) dengan elemen yang lain dan menyusunnya sedemikian rupa sehingga elemen-elemen lain yang lebih kecil daripada pivot tersebut terletak di sebelah kirinya dan elemen-elemen lain yang lebih besar daripada pivot tersebut terletak di sebelah kanan. Sehingga dengan demikian telah terbentuk dua sublist kiri dan sublist kanan dari pivot.

Cara menggunakan Quick Sort

1.    Pertama kita tentukan pivot dengan cara memilih suatu elemen yang sekiranya elemen tersebut mempunyai nilai yang seimbang antara elemen elemen yang sebelah kiri dan elemen elemen yang sebelah kanan.

2.    Setelah kita dapat suatu pivot, tinggal kita bandingkan elemen yang berada di sebelah kiri dari pivot dan sebelah kanan dari pivot, mana yang nilainya lebih kecil, kita tukar posisi kedua elemen tersebut dengan syarat nilai tersebut juga lebih kecil dari pivot.

3.    Lakukan hal yang sama pada elemen elemen selanjutnya sampai posisi dari elemen elemen suatu data tersebut dalam kondisi berurutan.

Contoh Kasus:

Terdapat suatu data yang belum dalam kondisi terurut, yaitu :

6 3 4 5 2 1 

Kita dapat mengurutkan data tersebut dengan metode quick sort dengan cara:

1.       Kita pilih pivot terlebih dahulu. Misal kita ambil pivot 4.

6 3 4 5 2 1 

2.       Lalu kita bandingkan data sebelah kiri dari pivot dengan data sebelah kanan dari pivot kemudian kita bandingkan dengan pivot itu sendiri. Lakukan hal yang sama sampai posisi sebelah kiri pivot telah berurutan.

6 3 4 5 2 1 

Menjadi

1 3 4 5 2 6 

Menjadi

1 2 4 5 3 6 

3.       Setelah posisi sebelah kiri dari pivot telah berurutan, sekarang tinggal kita pilih pivot selanjutnya. (lakukan ketiga cara tersebut sampai data tersebut menjadi terurut)

1 2 4 5 3 6 

1 2 3 5 4 6 

1 2 3 4 5 6  

Referensi :

http://paul-kurniawan-keren.blogspot.com/2009/06/quicksort.html