1. Pivot adalah elemen pertama, elemen terakhir, atau elemen tengah tabel. Cara ini hanya bagus jika elemen tabel tersusun secara acak, tetapi tidak bagus jika elemen tabel semula sudah terurut. Misalnya, jika elemen tabel semula menurun, maka semua elemen tabel akan terkumpul di upatabel kanan.
2. Pivot dipilih secara acak dari salah satu elemen tabel. Cara ini baik, tetapi mahal, sebab memerlukan biaya (cost) untuk pembangkitan prosedur acak. Lagi pula, itu tidak mengurangi kompleksitas waktu algoritma.
3. Pivot adalah elemen median tabel. Cara ini paling bagus, karena hasil partisi menghasilkan dua bagian tabel yang berukuran seimbang (masing masing ≈ n/2 elemen). Cara ini memberikan kompleksitas waktu yang minimum. Masalahnya, mencari median dari elemen tabel yang belum terurut adalah persoalan tersendiri.
contoh :
22 10 15 3 8 2
i j
- i bergerak dari sudut kiri ke kanan sampai mendapatkan nilai yang lebih besar atau sama dengan pivot
- j bergerak dari sudut kanan ke kiri sampai menemukan nilai yang lebih kecil dari pivot
22 10 (15) 3 8 2 ket : () merupakan pivot
proses pertama yaitu akan mencari angka lebih besar dari pivot dan paling terkecil dari pivot , sehingga terpilih 22 dan 2 melakukan penukaran:
2 10 (15) 3 8 22
proses kedua yaitu mencari angka lebih besar lagi dari pivot dan ternyata tidak terdapat angka yang lebih besar dari pivot sehingga terpilihlah angka pivot tersebut , dan elemen yang terkecil yang akan terpilih adalah 8
sehingga : 2 10 (8) 3 15 22 KET:() merupakan pivot
proses yang sama sehingga terpilih elemen yang lebih besar dari pivot yaitu 10 dan yang lebih kecil dari pivot yaitu 3 , sehingga :
2 3 8 10 15 22
Tidak ada komentar:
Posting Komentar