- 1 1. Apa itu Quick Sort? Konsep Dasar dan Gambaran Umum
- 2 2. Penjelasan Algoritma Quick Sort
- 3 3. Implementasi Quick Sort dalam Bahasa C
- 4 4. Performa dan Optimasi Quick Sort
- 5 5. Perbandingan Quick Sort dengan Algoritma Pengurutan Lain
- 6 6. Error Umum pada Quick Sort dan Cara Debugging
- 7 7. Kesimpulan dan Aplikasi Selanjutnya
1. Apa itu Quick Sort? Konsep Dasar dan Gambaran Umum
Quick sort adalah salah satu algoritma pengurutan yang digunakan untuk mengurutkan data secara efisien dalam bahasa C maupun banyak bahasa pemrograman lainnya. Metode ini diciptakan oleh C. A. R. Hoare dan dikenal karena kecepatannya yang sangat tinggi.
Ide Dasar Quick Sort
Quick sort membagi data berdasarkan nilai acuan yang disebut pivot, lalu mengurutkan data secara rekursif. Dengan menerapkan algoritma divide and conquer (pembagian dan penaklukan), semua elemen pada akhirnya akan terurut.
- Pivot: Nilai yang dipilih secara acak atau dengan aturan tertentu sebagai acuan untuk membagi data menjadi dua grup.
- Divide and conquer: Teknik memecah masalah besar menjadi masalah-masalah kecil, menyelesaikannya secara terpisah, lalu menggabungkan hasilnya.
Dibandingkan dengan algoritma pengurutan lain (seperti bubble sort atau insertion sort), quick sort sangat cepat terutama pada dataset berukuran besar.
2. Penjelasan Algoritma Quick Sort
Selanjutnya, mari kita bahas secara detail cara kerja algoritma quick sort.
Pemilihan Pivot
Langkah pertama pada quick sort adalah memilih pivot dari dalam array. Pivot adalah elemen penting yang mempengaruhi kecepatan eksekusi algoritma, dan pemilihan pivot yang tepat akan memengaruhi performa secara signifikan.
- Contoh: Pivot dapat dipilih dari elemen pertama, terakhir, atau tengah pada array.
Proses Pembagian Rekursif
Setelah pivot dipilih, array dibagi menjadi dua bagian berdasarkan nilai pivot. Nilai yang lebih kecil dari pivot diletakkan di satu sisi, dan nilai yang lebih besar di sisi lainnya. Proses ini diulang secara rekursif pada bagian-bagian yang tersisa.
- Langkah 1: Tempatkan elemen yang lebih kecil dari pivot di sisi kiri, dan yang lebih besar di sisi kanan.
- Langkah 2: Terapkan quick sort lagi pada masing-masing sub-array yang telah dibagi.
Dengan pembagian rekursif ini, seluruh array akhirnya akan terurut dengan baik.
3. Implementasi Quick Sort dalam Bahasa C
Selanjutnya, berikut langkah-langkah implementasi quick sort menggunakan bahasa C beserta contoh kodenya.
#include <stdio.h>
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Memilih elemen terakhir sebagai pivot
int i = (low - 1); // Indeks untuk elemen yang lebih kecil
for (int j = low; j <= high - 1; j++) {
if (arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
// Jalankan quick sort secara rekursif pada sub-array yang telah dibagi
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array:n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("n"); // Tambahkan baris baru untuk memperjelas output
return 0;
}
Pada kode di atas, fungsi swap digunakan untuk menukar dua elemen, fungsi partition membagi array berdasarkan pivot, dan fungsi quickSort melakukan pengurutan secara rekursif.

4. Performa dan Optimasi Quick Sort
Performa quick sort dikatakan sangat unggul dibandingkan algoritma pengurutan lain, namun pada kasus terburuk waktu eksekusi bisa menjadi tidak efisien. Berikut detail performa dan metode optimasinya.
Kompleksitas dan Kasus Terburuk
Rata-rata kompleksitas quick sort adalah O(n log n), namun pada kasus terburuk seperti array yang sudah terurut atau banyak elemen sama, kompleksitas bisa menjadi O(n^2). Hal ini menyebabkan kedalaman rekursi meningkat dan efisiensi menurun.
Metode Optimasi
- Pemilihan pivot yang lebih cermat: Dengan memilih elemen tengah atau elemen acak sebagai pivot, pembagian dapat menjadi lebih seimbang.
- Mengontrol pemanggilan rekursif stack: Untuk mengurangi kedalaman rekursi, dapat digunakan metode non-rekursif.
5. Perbandingan Quick Sort dengan Algoritma Pengurutan Lain
Quick sort adalah algoritma pengurutan yang sangat efisien, namun masih ada beberapa algoritma lain yang populer. Pada bagian ini, kita akan membandingkan quick sort dengan algoritma lain beserta kelebihan dan kekurangannya.
Quick Sort vs. Merge Sort
- Cara kerja algoritma:
Quick sort dan merge sort sama-sama menggunakan divide and conquer, namun berbeda pada cara membagi dan menggabungkan data. Quick sort lebih fokus pada pembagian, sedangkan merge sort fokus pada penggabungan hasil sub-array. - Performa:
Kedua algoritma rata-rata memiliki kompleksitas O(n log n), namun pada kasus terburuk quick sort bisa O(n^2). Merge sort memiliki performa yang lebih stabil di semua kondisi. - Kelebihan dan Kekurangan:
Quick sort biasanya lebih hemat memori daripada merge sort, sehingga efektif untuk data besar. Namun, pada kasus terburuk perlu hati-hati. Merge sort stabil dan konsisten, cocok untuk data yang hampir terurut.
Quick Sort vs. Heap Sort
- Cara kerja algoritma:
Quick sort bekerja dengan membagi array secara rekursif, sedangkan heap sort mengubah data menjadi struktur heap, lalu mengambil elemen terbesar (atau terkecil) secara berurutan. - Performa:
Heap sort juga berjalan dengan O(n log n), namun sering kali lebih lambat dari quick sort pada data acak. - Kelebihan dan Kekurangan:
Quick sort biasanya lebih cepat dari heap sort. Namun, heap sort menjamin O(n log n) di kasus terburuk, cocok sebagai alternatif jika quick sort berisiko O(n^2).
Quick Sort vs. Bubble Sort
- Cara kerja algoritma:
Bubble sort membandingkan elemen yang berdekatan dan menukar posisinya bila perlu, sehingga sangat sederhana namun tidak efisien dibanding quick sort. - Performa:
Bubble sort memiliki kompleksitas O(n^2), jauh lebih lambat dari quick sort. Hanya cocok untuk array kecil dan sederhana. - Kelebihan dan Kekurangan:
Bubble sort sangat mudah dipahami dan diimplementasikan, tetapi dalam praktik jarang digunakan karena performanya sangat rendah dibanding quick sort.
6. Error Umum pada Quick Sort dan Cara Debugging
Dalam implementasi quick sort atau penggunaan qsort()
, beberapa error umum dapat terjadi. Berikut beberapa contoh error dan solusinya.
1. Stack Overflow
Karena quick sort adalah algoritma rekursif, terlalu dalamnya rekursi dapat menyebabkan stack overflow. Untuk menghindarinya, batasi kedalaman rekursi atau pertimbangkan implementasi non-rekursif.
- Solusi: Ganti bagian rekursif dengan perulangan (loop) agar risiko stack overflow berkurang.
2. Infinite Loop (Loop Tak Berakhir)
Jika pemilihan pivot atau proses rekursi salah, infinite loop bisa terjadi. Umumnya disebabkan oleh pivot yang tidak tepat atau kondisi akhir rekursi yang kurang benar.
- Solusi: Pastikan pemilihan pivot dan kondisi akhir rekursi sudah benar agar sort selesai dengan baik.
3. Akses Memori yang Salah
Pada penggunaan pointer untuk manipulasi array, akses memori yang salah dapat terjadi jika mengakses di luar batas array.
- Solusi: Pastikan seluruh akses array berada dalam rentang yang valid dan proses rekursi sudah tepat.
7. Kesimpulan dan Aplikasi Selanjutnya
Quick sort adalah salah satu algoritma pengurutan paling efisien di C, terutama untuk dataset besar. Dengan pemilihan pivot dan teknik divide and conquer, algoritma ini digunakan secara luas. Selain itu, fungsi qsort()
pada library standar C memudahkan proses pengurutan secara praktis dan kuat.
Saat menggunakan quick sort, pilih pivot yang optimal sesuai ukuran dan karakteristik data untuk meningkatkan performa. Jika terjadi error, periksa kembali proses rekursi dan manajemen memori.
Semoga artikel ini membantu Anda memahami quick sort dari dasar hingga implementasi, dan dapat diterapkan dalam program Anda.