Bahan Ajar/modul matakuliah Struktur Data ini membahas konsep tentang salah satu metode pengurutan Quick Sort. Materi membahas mulai dari pengertian Quick Sort, pseudocode Quick Sort, analisis algoritma Quick Sort dan dDiakhir sesi dapat dilihat implemetasi Quick Sort Menggunakan C/C++.
Pengertian Quick Sort
Algoritma sortir yang efisien yang ditulis oleh C.A.R. Hoare pada 1962. Dasar strateginya adalah “memecah dan menguasai”. Quicksort dimulai dengan menscan daftar yang disortir untuk nilai median. Nilai ini, yang disebut tumpuan (pivot), kemudian dipindahkan ke satu sisi pada daftar dan butir-butir yang nilainya lebih besar dari tumpuan di pindahkan ke sisi lain.
Algoritma Quick Sort
- Divide
Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.
- Conquer
Mengurutkan elemen pada sub-rangkaian secara rekursif Pada algoritma quick sort, langkah ”kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub array.
Pseudocode Quick Sort
Contoh Quick Sort
Analisis Algoritma QuickSort
Setiap elemen yang akan disort selalu diperlakukan secara sama di sini, diambil salah satu elemen, dibagi menjadi 3 list, lalu ketiga list tersebut disort dan digabung kembali. Contoh kode di atas menggunakan 3 buah list, yaitu yang lebih besar, sama dan lebih kecil nilainya dari pivot. Untuk membuat lebih efisien, bisa digunakan 2 buah list dengan mengeliminasi yang nilainya sama (bisa digabung ke salah satu dari 2 list yang lain). Kasus terburuk dari algoritma ini adalah saat dibagi menjadi 2 list, satu list hanya terdiri dari 1 elemen dan yang lain terdiri dari n-2 elemen. Untuk kasus terburuk dan kasus rata-rata, algoritma ini memiliki kompleksitas sebesar O(n log n). Jumlah rata-rata perbandingan untuk quick sort berdasarkan permutasinya dengan asumsi bahwa nilai pivot diambil secara random adalah :
Lalu bagaimana cara menentukan pivot sendiri? Kasus terbaik yang diharapkan diilustrasikan sebagai berikut:
Bagi sebuah list menjadi 4 buah. Lalu pilih 2 buah list sedemikian rupa sehingga setiap elemennya lebih besar dari 25 % elemen terkecil dan lebih kecil dari 25% elemen terbesar. Bila nilai pivot yang dipilih secara konstan terambil dari nilai ini maka hanya diperlukan pembagian list sebanyak 2log2n kali.Biladibandingkan dengan merge sort, quick sort memiliki keuntungan di kompleksitas waktu sebesar Θ(log n), dibanding dengan merge sort sebesar Θ(n). namun quick sort tidak mampu membandingkan linked list sebaik merge sort, karena ada kemungkinan pemilihan pivot yang buruk. Selain itu pada linked list merge sort memerlukan ruang yang lebih sedikit. Berdasarkan analisis tersebut quick sort termasuk algoritma sorting yang cukup baik, namun kita pun harus bisa memilih nilai pivot yang baik agar penggunaannya bisa optmal.
Implementasi Quic Sort Menggunakan C/C++
| 01 | Partition(A, p, r) | |
| 02 | x = A[p]; //pivot=elemen posisi pertama | |
| 03 | i = p ; //inisialisasi | |
| 04 | j = r ; | |
| 05 | repeat | |
| 06 | while(A[j] > x) | |
| 07 | j--; | |
| 08 | while(A[i] < x) | |
| 09 | i++; | |
| 10 | if (i < j){ | |
| 11 | Swap(A, i, j); | |
| 12 | j--; | |
| 13 | i++ | |
| 14 | } | |
| 15 | else | |
| 16 | return j; | |
| 17 | until i >= j |
0 komentar:
Posting Komentar