quick sort
Post on 26-Nov-2014
350 Views
Preview:
TRANSCRIPT
Quick sort Pertemuan 12
Matakuliah : T0456 / Algoritma dan Metode Object Oriented Programming
Tahun : 2007
Bina Nusantara
Learning Outcomes
Pada akhir pertemuan ini, diharapkan:Mahasiswa dapat menggunakan algoritma quick sort untuk mengurutkan data.
Buku Referensi:Algorithms in C++, Addison Wesley, 1992.
Websites:
http://www.deitel.com
3
Bina Nusantara
Outline Materi
• Algoritma quick sort• Simulasi algoritma quick sort• Contoh program
4
Bina Nusantara
Quick sortBekerja dengan memartisi data menjadi 2 bagian sehingga:
a[kiri], a[kiri+1], …, a[i-1] < a[i]a[i] berada pada posisi yang tepata[i+1], a[i+2], …, a[kanan] > a[i]
[kiri] [i] [kanan]
4512 69 84 70
[kiri+1] … [i-1]
…
[i+1] …
…
Bina Nusantara
[0] [2] [4] [6] [8]
7872 777973
[1] [3] [5] [7]
7576 7471
K=6J=1
Tukar
7872 777173 7576 7479
K=3J=2
Tukar
7876 777173 7572 7479
K=2J=3
Tukar
7876 777172 7573 7479
QS(0,1) QS(3,8)
Quick sort (0,8)
Bina Nusantara
[0] [2] [4] [6] [8]
7876 777172
[1] [3] [5] [7]
7573 7479
K=1J=2
Tukar
7876 777271 7573 7479
Quick sort (0,1)
Bina Nusantara
[0] [2] [4] [6] [8]
7876 777271
[1] [3] [5] [7]
7573 7479
K=8J=5
Tukar
7476 777271 7573 7879
K=5J=6
Tukar
7674 777271 7573 7879
QS(3,4) QS(6,8)
Quick sort (3,8)
Bina Nusantara
[0] [2] [4] [6] [8]
7674 777271
[1] [3] [5] [7]
7573 7879
K=3J=4
7674 777271 7573 7879
Quick sort (3,4)
Bina Nusantara
[0] [2] [4] [6] [8]
7674 777271
[1] [3] [5] [7]
7573 7879
K=8J=…
7674 777271 7573 7978
Tukar
QS(6,7)
Quick sort (6,8)
Bina Nusantara
[0] [2] [4] [6] [8]
7674 777271
[1] [3] [5] [7]
7573 7978
K=7J=8
7674 787271 7573 7977
Tukar
QS(6,6)
Quick sort (6,7)
Bina Nusantara
[0] [2] [4] [6] [8]
7674 787271
[1] [3] [5] [7]
7573 7977
K=6J=…
7674 787271 7573 7977
Quick sort (6,6)
Bina Nusantara
Void QS (int *Dt, int Kr, int Kn){
int i, j, k;
if (Kr<Kn) {
j = Kr;
k = Kn+1;
do {
do j++; while (Dt[j]<Dt[Kr]);
do k--; while (Dt[k]>Dt[Kr]);
if (j<k) tukar (&Dt[j], &Dt[k]);
} while (j<=k);
tukar (&Dt[Kr], &Dt[k]);
QS (Dt, Kr, k-1);
QS (Dt, k+1, Kn);
}
Quick sort
Bina Nusantara 14
Diskusi dan Tanya JawabLatihan soal
top related