Pengurutan cepat

(quick sort)

Pengurutan data merupakan komponen dasarstruktur data

Misal : Pencarian biner, Pencarian interpolasi

Pengurutan data juga dimanfaatkan untukmengeliminasi rekaman-rekaman yang ganda.

Pengurutan rekaman terbagi menjadi beberapabagian

1. Pengurutan gelembung

2. Pengurutan dengan penyisipan

3. Pengurutan dengan cepat

4. Pengurutan lomuto

5. Pengurutan dengan Heap (deret atau pohon biner)

Memproses berkas dengan membagi rekaman-

rekaman menjadi beberapa kelompok kemudian

mengurutkannya.

Bila sebuah kelompok hanya berisi satu item

maka proses pengurutan kelompok tersebut

dihentikan

Bila proses pengurutan untuk semua kelompok

sudah selesai, maka keseluruhan rekaman dalam

berkas sudah dalam keadaan urut

Prosedur quick sort melakukan pengurutan

berkas dengan mengelompokkan rekaman-

rekaman menjadi beberapa kelompok berdasar

hasil perbandingan terhadap anggota berkas

tertentu.

Proses tersebut diulang sampai semua

kelompok sudah dalam keadaan urut

Algoritma Quick Sort

1. Jika terdapat sejumlah rekaman yang harusdiurutkan, pisahkan rekaman-rekaman tersebutdalam tiga kelompok (rekaman-rekaman dengankunci rekaman lebih kecil dari kunci rekamanpertama dan rekaman-rekaman dengan kuncirekaman lebih besar dari kunci rekamanpertama) Ulangi langkah 1 untuk rekaman-rekaman dalam kelompok

pertama maupun kelompok ke-3

Ulangi langkah 1 untuk rekaman-rekaman dalam subkelompokyang dibentuk oleh langkah (a)

2. Jika masing-masing hanya terdapat 1 rekamandalam semua kelompok atau subkelompok (sub-sub…) maka proses berakhir

Berkas/kelompok dibagi berdasar pada perbandingan

dengan rekaman pertama dari berkas/kelompok.

Semua rekaman dengan kunci lebih kecil dari kunci

pada rekaman pertama di letakkan di sebelah kiri

rekaman pembanding

Kemudian rekaman dengan kunci yang lebih besar di

letakkan pada bagian sebelah kanan rekaman

pembanding.

Latihan

Urutkanlah rekaman-rekaman berikut :

36 25 79 56 89 76 90 100

Urutkanlah rekaman-rekaman berikut :

9 8 26 12 19 63 52 99

Urutkanlah rekaman-rekaman berikut :

85 51 61 41 73 43 101 93