Quick Sort
Tuesday, November 11, 2014
Nama : Marla Nur Assyifa
NPM : 56414412
Kelas : 1IA17
Mata Kuliah : Algoritma Pemrograman 1A
Dosen : Kunto Bayu A,ST
Quick
sort adalah pensortiran cepat yang menggunakan cara penyelesaian divide
(membagi) dan conquer (menggabungkan). Langkah pertama dalam quick sort
adalah menentukan elemen yang akan digunakan sebagai poros
(pivot). Cara pemilihan pivot sebenarnya tidak ada aturan tersendiri,
namun pada umumnya pivot dipilih dari elemen pertama, elemen tengah,
elemen akhir, atau bahkan elemen tengah suatu tabel/susunan angka.
Contoh :
9
|
1
|
7
|
6
|
5
|
8
|
4
|
3
|
2
|
Ditentukan
angka 5 sebagai pivot yang merupakan elemen tengah. Dimisalkan bahwa
angka-angka sebelah kiri pivot merupakan elemen yang lebih kecil dari
pivot dan sebelah kanan lebih besar dari pivot.
1
|
2
|
7
|
6
|
5
|
3
|
4
|
8
|
9
|
Dikarenakan angka 9>5 dan 1<5, maka angka 9 dan 1 bertukar posisi.
1
|
2
|
7
|
6
|
5
|
3
|
4
|
8
|
9
|
Kemudian kita bergeser ke angka sebelahnya yaitu angka 2 dan 8, 2<5 dan 8>5 maka tidak ada pertukaran posisi.
1
|
2
|
7
|
6
|
5
|
3
|
4
|
8
|
9
|
7>5 dan 4<5 maka 7 dan 4 bertukar posisi.
1
|
2
|
4
|
6
|
5
|
3
|
7
|
8
|
9
|
Masih dengan pivot yang sama yaitu 5, kita lihat ke angka sebelahnya.
1
|
2
|
4
|
6
|
5
|
3
|
7
|
8
|
9
|
6>5 dan 3<5 maka 6 dan 3 bertukar posisi.
1
|
2
|
4
|
3
|
5
|
6
|
7
|
8
|
9
|
Sekarang kita rubah pivotnya menjadi angka 3
1
|
2
|
4
|
3
|
5
|
6
|
7
|
8
|
9
|
Cek elemen sebelah kanan dan kiri pivot, jika tidak sesuai aturan maka bertukar posisi. 5>3 dan 4>3 maka 3 dan 4 bertukar posisi.
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
Sumber :
0 comments