Quick Sort di C++: Pengertian, Cara Kerja, dan Contoh Program

Mengurutkan data adalah salah satu kegiatan paling umum dalam pemrograman. Salah satu algoritma yang sering digunakan dan memiliki kinerja baik untuk pengurutan adalah Quick Sort. Dalam artikel ini, kita akan membahas Quick Sort di C++ secara mendetail, mulai dari pengertiannya, mekanisme kerjanya, hingga contoh program yang mengimplementasikannya.

Quick Sort di C++

Pengertian Quick Sort

Quick Sort adalah salah satu algoritma pengurutan yang menggunakan teknik 'membagi-dan-taklukkan'. Dibandingkan dengan algoritma pengurutan lainnya seperti Bubble Sort atau Merge Sort, Quick Sort biasanya lebih cepat dalam prakteknya, walaupun dalam kasus terburuk bisa lebih lambat.

Cara Kerja Quick Sort

Quick Sort adalah sebuah algoritma yang berfungsi untuk mengurutkan data dengan teknik 'membagi-dan-taklukkan'. Berikut adalah langkah-langkah yang dijalankan oleh algoritma ini:

1. Memilih Pivot

Algoritma ini dimulai dengan memilih sebuah elemen dari array sebagai "pivot". Tidak ada aturan khusus dalam memilih pivot, tetapi pilihan ini akan mempengaruhi keefisienan algoritma. Biasanya, pivot bisa berupa elemen pertama, elemen tengah, atau elemen akhir dari array.

Mengapa Pivot Penting?

Pivot digunakan sebagai elemen referensi untuk membagi array menjadi dua bagian: satu bagian dengan elemen yang lebih kecil dari pivot dan satu lagi dengan elemen yang lebih besar dari pivot.

2. Proses Partisi

Setelah pivot dipilih, algoritma akan mempartisi array menjadi dua bagian. Ini adalah langkah kunci dari Quick Sort.

Bagaimana Partisi Dilakukan?

• Iterasi dimulai dari dua ujung array; satu indeks (i) dari ujung kiri dan satu indeks (j) dari ujung kanan.
• Elemen-unsur array dibandingkan dengan pivot.
• Indeks i bergerak ke kanan, melewati elemen yang lebih kecil dari pivot.
• Indeks j bergerak ke kiri, melewati elemen yang lebih besar dari pivot.
• Ketika i kurang dari atau sama dengan j, elemen pada posisi i dan j ditukar.
• Proses ini terus berlanjut hingga i dan j bertemu.

Setelah partisi selesai, array telah terbagi menjadi dua sub-array. Elemen pada sub-array pertama lebih kecil dari pivot, sementara elemen pada sub-array kedua lebih besar dari pivot.

3. Rekursi pada Sub-array

Setelah proses partisi, algoritma akan memanggil dirinya sendiri (rekursif) untuk mengurutkan dua sub-array yang telah dibuat. Ini terjadi secara rekursif sampai seluruh array menjadi terurut.

Mengapa Rekursi?

Rekursi digunakan karena Quick Sort mengadopsi prinsip 'membagi dan taklukkan'. Sub-array yang lebih kecil akan lebih mudah (dan lebih cepat) untuk diurutkan. Seiring waktu, semua sub-array akan terurut, dan oleh karena itu, seluruh array juga akan terurut.

Baca Juga: Tutorial Lengkap Belajar Bahasa Pemrograman C++

Contoh Program Quick Sort di C++

Berikut adalah contoh kode program Quick Sort di C++.

#include <iostream>

using namespace std;

void quickSort(int arr[], int left, int right) {

    int i = left, j = right;

    int pivot = arr[(left + right) / 2];

  

    while (i <= j) {

        while (arr[i] < pivot)

            i++;

        while (arr[j] > pivot)

            j--;

        if (i <= j) {

            swap(arr[i], arr[j]);

            i++;

            j--;

        }

    }

  

    if (left < j)

        quickSort(arr, left, j);

    if (i < right)

        quickSort(arr, i, right);

}

int main() {

    int arr[] = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};

    int n = sizeof(arr)/sizeof(arr[0]);

  

    quickSort(arr, 0, n-1);

  

    for(int i = 0; i < n; i++) {

        cout << arr[i] << " ";

    }

  

    return 0;

}

Output

2 3 5 6 7 9 10 11 12 14 

Penjelasan Program

Deklarasi Library: #include <iostream> adalah untuk memasukkan library input-output stream pada C++.

Deklarasi Fungsi Quick Sort: Fungsi quickSort mengambil array dan dua indeks left dan right sebagai argumennya. left adalah indeks paling kiri dari array atau sub-array yang akan diurutkan, dan right adalah indeks paling kanan.

Inisialisasi Variabel: Variabel i dan j digunakan untuk iterasi. pivot adalah elemen tengah dari array atau sub-array.

While Loop: Loop ini bertujuan untuk mempartisi array. Dalam partisi ini, elemen yang lebih kecil dari pivot bergerak ke sebelah kiri pivot dan elemen yang lebih besar bergerak ke sebelah kanan.

• while (arr[i] < pivot) i++; : Meningkatkan indeks i sampai menemukan elemen yang lebih besar atau sama dengan pivot.
• while (arr[j] > pivot) j--; : Mengurangi indeks j sampai menemukan elemen yang lebih kecil atau sama dengan pivot.
• if (i <= j): Jika i kurang dari atau sama dengan j, tukar elemen pada indeks i dan j.

Rekursi: Setelah mempartisi, fungsi quickSort dipanggil secara rekursif pada sub-array yang terbentuk, yaitu dari left sampai j dan dari i sampai right.

Fungsi Main: Fungsi main() menginisialisasi array arr dan memanggil fungsi quickSort.

Output: Menampilkan array yang sudah diurutkan.

Program diatas menunjukkan bagaimana algoritma Quick Sort bekerja dalam mengurutkan sebuah array. Fungsi quickSort melakukan semua kerjaan, mulai dari memilih pivot, mempartisi array, dan akhirnya memanggil dirinya sendiri secara rekursif untuk mengurutkan sub-array yang dihasilkan.

Kelebihan dan Kekurangan Algoritma Quick Sort

Kelebihan Quick Sort:

• Kecepatan: Quick Sort termasuk algoritma sorting yang cepat dengan kompleksitas waktu rata-rata O(nlogn), membuatnya efisien untuk dataset yang besar.
• Penggunaan Memori: Quick Sort adalah algoritma 'in-place', yang berarti ia hanya memerlukan sedikit memori tambahan (overhead) untuk melakukan operasinya.
• Adaptif: Quick Sort adalah algoritma yang adaptif, yang berarti ia bekerja lebih cepat jika sebagian dari input data sudah diurutkan.
• Versatilitas: Dapat digunakan pada berbagai jenis data dan struktur data, seperti array dan linked list.

Kekurangan Quick Sort:

• Stabilitas: Quick Sort bukan merupakan algoritma yang stabil. Dua elemen yang sama bisa bertukar posisi, mengubah stabilitas data.
• Kompleksitas Terburuk: Dalam kasus terburuk, kompleksitas waktunya adalah O(n2), meskipun ini bisa diatasi dengan menggunakan teknik seperti 'median-of-three' untuk memilih pivot.
• Sensitif terhadap Pemilihan Pivot: Efisiensi algoritma sangat bergantung pada pemilihan pivot. Jika pivot yang buruk dipilih, algoritma menjadi tidak efisien.
• Tidak Efisien untuk Data Kecil: Meski jarang terjadi, untuk dataset yang sangat kecil, algoritma lain seperti Bubble Sort atau Insertion Sort bisa lebih cepat.

Algoritma Quick Sort adalah salah satu algoritma pengurutan yang paling efisien dan sering digunakan. Dengan memahami cara kerjanya, Anda bisa mengimplementasikannya dalam berbagai proyek pemrograman Anda. Meskipun memiliki kasus terburuk yang kurang optimal, dalam banyak skenario, Quick Sort tetap menjadi pilihan terbaik.

Daftar Pustaka

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). The MIT Press.
• Sedgewick, R. (2011). Algorithms (4th ed.). Addison-Wesley.

Sekian artikel mengenai Quick Sort di C++. Semoga artikel ini dapat bermanfaat baik untuk menambah ilmu, mengerjakan tugas, maupun untuk sekedar menambah wawasan, Terimakasih atas kunjungannya.

MateriDosen.Com

Berbagi: