J. E. N. I.
2. Conquer Mengurutkan elemen pada sub-rangkaian secara rekursif
Pada algoritma quicksort, langkah” kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array
6.5.1 Algoritma
void quickSort( Object array [], int leftIdx, int rightIdx) { int pivotIdx; /* Kondisi Terminasi */ if( rightIdx > leftIdx) { pivotIdx = partition( array, leftIdx, rightIdx); quickSort( array, leftIdx, pivotIdx-1); quickSort( array, pivotIdx + 1, rightIdx);
}
}
6.5.2 Sebuah Contoh
Rangkaian data: 3 1 4 1 5 9 2 6 5 3 5 8
Pilih sebuah elemen yang akan menjadi elemen pivot. 3 1 4 1 5 9 2 6 5 3 5 8
Inisialisasi elemen kiri sebagai elemen kedua dan elemen kanan sebagai elemen akhir. kiri kanan 3 1 4 1 5 9 2 6 5 3 5 8
Geser elemen kiri kearah kanan sampai ditemukan nilai yang lebih besar dari elemen pivot tersebut. Geser elemen kanan ke arah kiri sampai ditemukan nilai dari elemen yang tidak lebih besar dari elemen tersebut.
kiri kanan 3 1 4 1 5 9 2 6 5 3 5 8
Tukarkan antara elemen kiri dan kanan kiri kanan
Pengenalan Pemrograman 2 6