Beranda pendidikan peringkat qs universitas

QS Itu Apa Sih? Panduan Lengkap Mengenal QS dan Fungsinya!

Updated: • 0 • min read
Table of Contents

Quick Sort atau sering disingkat QS, adalah salah satu algoritma pengurutan (sorting algorithm) yang populer dalam ilmu komputer. Algoritma ini dikenal karena efisiensinya dalam mengurutkan data dalam jumlah besar. Quick Sort termasuk dalam kategori divide and conquer, yang berarti memecah masalah besar menjadi sub-masalah yang lebih kecil, menyelesaikannya secara terpisah, dan kemudian menggabungkannya kembali untuk mendapatkan solusi akhir. Popularitas Quick Sort tidak lepas dari performanya yang baik dalam banyak kasus, menjadikannya pilihan utama dalam berbagai aplikasi pengolahan data.

Bagaimana Cara Kerja Quick Sort?

Quick Sort Algorithm Visualization
Image just for illustration

Quick Sort bekerja dengan prinsip yang cukup sederhana namun efektif. Inti dari algoritma ini terletak pada proses partisi dan rekursi. Mari kita bedah langkah-langkah utama dalam Quick Sort agar lebih mudah dipahami:

1. Pilih Pivot

Langkah pertama adalah memilih elemen pivot dari array atau daftar yang akan diurutkan. Pivot ini akan menjadi titik acuan dalam proses partisi. Ada berbagai cara untuk memilih pivot, beberapa strategi umum termasuk:

  • Pivot pertama: Memilih elemen pertama dalam array sebagai pivot.
  • Pivot terakhir: Memilih elemen terakhir sebagai pivot.
  • Pivot acak: Memilih pivot secara acak dari array.
  • Median-of-three: Memilih median dari tiga elemen (biasanya elemen pertama, tengah, dan terakhir) sebagai pivot.

Pemilihan pivot dapat mempengaruhi performa Quick Sort. Pivot yang baik idealnya adalah elemen median dari array, karena akan membagi array menjadi dua sub-array yang hampir sama besar. Namun, dalam praktiknya, memilih pivot secara acak atau median-of-three seringkali memberikan hasil yang cukup baik dan menghindari kasus terburuk.

2. Partisi (Partitioning)

Partitioning in Quick Sort
Image just for illustration

Setelah pivot dipilih, langkah selanjutnya adalah melakukan partisi. Proses partisi ini bertujuan untuk mengatur ulang array sehingga semua elemen yang lebih kecil dari pivot ditempatkan di sebelah kiri pivot, dan semua elemen yang lebih besar dari pivot ditempatkan di sebelah kanan pivot. Pivot sendiri akan berada pada posisi akhirnya dalam array yang sudah terurut.

Proses partisi biasanya dilakukan dengan menggunakan dua pointer, sebut saja left dan right. Pointer left dimulai dari awal array (setelah pivot) dan bergerak ke kanan mencari elemen yang lebih besar dari pivot. Pointer right dimulai dari akhir array dan bergerak ke kiri mencari elemen yang lebih kecil dari pivot.

Ketika left dan right berhenti (karena menemukan elemen yang tidak sesuai), elemen pada posisi left dan right ditukar. Proses ini diulang sampai left dan right pointer saling berpapasan atau left melewati right. Setelah proses partisi selesai, pivot ditempatkan pada posisi yang tepat di antara sub-array kiri dan kanan.

3. Rekursi (Recursion)

Quick Sort Recursion Tree
Image just for illustration

Setelah proses partisi, kita memiliki dua sub-array: sub-array kiri (elemen lebih kecil dari pivot) dan sub-array kanan (elemen lebih besar dari pivot). Langkah selanjutnya adalah melakukan rekursi pada kedua sub-array ini. Artinya, kita kembali menerapkan algoritma Quick Sort pada sub-array kiri dan sub-array kanan secara terpisah.

Proses rekursi ini akan terus berlanjut hingga sub-array menjadi kosong atau hanya berisi satu elemen. Sub-array dengan satu atau nol elemen sudah dianggap terurut, sehingga menjadi base case atau kondisi berhenti untuk rekursi.

4. Gabung (Combine - Implicit)

Dalam Quick Sort, proses penggabungan (combine) sebenarnya terjadi secara implisit. Karena proses partisi sudah menempatkan pivot pada posisi yang benar dan rekursi mengurutkan sub-array kiri dan kanan, maka ketika semua rekursi selesai, seluruh array secara otomatis sudah terurut. Tidak ada langkah penggabungan eksplisit seperti pada algoritma Merge Sort.

Contoh Sederhana Quick Sort

Mari kita lihat contoh sederhana bagaimana Quick Sort bekerja pada array berikut: [7, 2, 1, 6, 8, 5, 3, 4]

  1. Pilih Pivot: Misalkan kita memilih pivot pertama, yaitu 7.

  2. Partisi:

    • Array awal: [**7**, 2, 1, 6, 8, 5, 3, 4] (Pivot: 7)
    • Setelah partisi (misalnya, setelah beberapa iterasi proses pointer left dan right dan penukaran): [4, 2, 1, 6, 5, 3, **7**, 8]
    • Pivot 7 sekarang berada pada posisi yang benar. Sub-array kiri: [4, 2, 1, 6, 5, 3], Sub-array kanan: [8]

  3. Rekursi:

    • Quick Sort pada sub-array kiri: [4, 2, 1, 6, 5, 3]
      • Pilih pivot (misalnya, 4): [**4**, 2, 1, 6, 5, 3]
      • Partisi: [3, 2, 1, **4**, 6, 5]
      • Rekursi pada [3, 2, 1] dan [6, 5]
    • Quick Sort pada sub-array kanan: [8] (sudah terurut karena hanya satu elemen)

Proses rekursi ini terus berlanjut sampai semua sub-array terurut. Pada akhirnya, array akan menjadi: [1, 2, 3, 4, 5, 6, 7, 8].

Kelebihan dan Kekurangan Quick Sort

Setiap algoritma memiliki kelebihan dan kekurangan, dan Quick Sort juga tidak terkecuali. Memahami kelebihan dan kekurangan ini penting untuk menentukan kapan Quick Sort menjadi pilihan yang tepat.

Kelebihan Quick Sort:

  • Efisiensi Rata-rata: Quick Sort memiliki kompleksitas waktu rata-rata O(n log n), yang menjadikannya sangat efisien untuk mengurutkan data dalam jumlah besar. Dalam banyak kasus praktis, Quick Sort bekerja lebih cepat daripada algoritma pengurutan O(n log n) lainnya seperti Merge Sort.
  • In-place Sorting: Quick Sort adalah algoritma in-place, yang berarti hanya membutuhkan sedikit ruang memori tambahan selain array input. Ini karena Quick Sort tidak memerlukan array tambahan untuk menyimpan data sementara seperti yang dilakukan Merge Sort. Ruang memori tambahan yang dibutuhkan Quick Sort umumnya hanya untuk stack rekursi, yang logaritmik terhadap ukuran input (O(log n)).
  • Performa Cache yang Baik: Quick Sort cenderung memiliki performa cache yang baik karena operasinya yang berurutan dan lokal. Ini berarti Quick Sort lebih efisien dalam memanfaatkan cache memori, yang dapat meningkatkan kecepatan eksekusi.
  • Implementasi Relatif Sederhana: Meskipun konsep rekursi mungkin terlihat rumit, implementasi Quick Sort relatif sederhana dibandingkan beberapa algoritma pengurutan lainnya, terutama jika dibandingkan dengan algoritma pengurutan yang lebih kompleks seperti Heap Sort.

Kekurangan Quick Sort:

  • Kasus Terburuk O(n^2): Dalam kasus terburuk, kompleksitas waktu Quick Sort bisa mencapai O(n^2). Kasus terburuk ini terjadi ketika pivot yang dipilih selalu menjadi elemen terkecil atau terbesar dalam sub-array. Hal ini menyebabkan partisi yang tidak seimbang, di mana satu sub-array sangat kecil dan sub-array lainnya hampir sebesar array awal. Contoh kasus terburuk adalah ketika array sudah terurut atau hampir terurut dan kita selalu memilih pivot pertama atau terakhir.
  • Tidak Stabil: Quick Sort umumnya tidak stabil. Algoritma pengurutan stabil adalah algoritma yang mempertahankan urutan relatif elemen-elemen dengan nilai yang sama. Dalam Quick Sort, penukaran elemen selama partisi dapat mengubah urutan relatif elemen-elemen yang sama. Jika stabilitas pengurutan penting, algoritma lain seperti Merge Sort mungkin lebih cocok.
  • Rentan terhadap Pemilihan Pivot yang Buruk: Performa Quick Sort sangat bergantung pada pemilihan pivot. Pemilihan pivot yang buruk dapat menyebabkan kasus terburuk O(n^2). Meskipun strategi pemilihan pivot seperti pivot acak atau median-of-three dapat mengurangi risiko kasus terburuk, mereka tidak sepenuhnya menghilangkannya.
  • Overhead Rekursi: Quick Sort menggunakan rekursi, yang dapat menyebabkan overhead tambahan karena pemanggilan fungsi rekursif. Untuk array yang sangat kecil, overhead rekursi mungkin lebih besar daripada keuntungan dari efisiensi Quick Sort. Dalam kasus seperti ini, algoritma pengurutan sederhana seperti Insertion Sort mungkin lebih cepat.

Kapan Menggunakan Quick Sort?

Quick Sort adalah pilihan yang sangat baik dalam banyak situasi, terutama ketika:

  • Efisiensi Rata-rata Penting: Jika Anda membutuhkan algoritma pengurutan yang cepat dalam rata-rata kasus dan data yang akan diurutkan berukuran besar, Quick Sort adalah pilihan yang sangat baik.
  • Memori Terbatas: Jika memori adalah batasan dan Anda membutuhkan algoritma pengurutan in-place, Quick Sort lebih unggul dibandingkan Merge Sort yang membutuhkan ruang tambahan O(n).
  • Performa Cache Diperlukan: Jika performa cache penting untuk aplikasi Anda, Quick Sort seringkali memberikan hasil yang lebih baik daripada algoritma lain dengan kompleksitas waktu yang sama.

Namun, hindari menggunakan Quick Sort jika:

  • Stabilitas Pengurutan Penting: Jika Anda membutuhkan algoritma pengurutan yang stabil, Quick Sort bukanlah pilihan yang tepat. Pertimbangkan Merge Sort atau algoritma pengurutan stabil lainnya.
  • Kasus Terburuk Harus Dihindari: Jika Anda sangat khawatir tentang kemungkinan kasus terburuk O(n^2), dan Anda tidak yakin dengan distribusi data input, algoritma lain seperti Merge Sort atau Heap Sort yang memiliki kompleksitas waktu O(n log n) dalam semua kasus mungkin lebih aman.
  • Array Sangat Kecil: Untuk array yang sangat kecil, overhead rekursi Quick Sort mungkin tidak sebanding dengan keuntungannya. Algoritma pengurutan sederhana seperti Insertion Sort mungkin lebih efisien untuk array kecil.

Tips Optimasi Quick Sort

Meskipun Quick Sort sudah cukup efisien, ada beberapa teknik optimasi yang dapat meningkatkan performanya lebih lanjut:

  1. Pemilihan Pivot yang Lebih Baik: Seperti yang telah disebutkan, pemilihan pivot sangat penting. Menggunakan strategi seperti median-of-three atau pivot acak dapat mengurangi kemungkinan kasus terburuk. Median-of-three melibatkan pemilihan median dari elemen pertama, tengah, dan terakhir sebagai pivot. Pivot acak memilih pivot secara acak dari array.

  2. Insertion Sort untuk Sub-array Kecil: Untuk sub-array yang sangat kecil (misalnya, dengan ukuran kurang dari 10-20 elemen), overhead rekursi Quick Sort mungkin menjadi tidak efisien. Dalam kasus ini, beralih ke algoritma pengurutan sederhana seperti Insertion Sort untuk sub-array kecil dapat meningkatkan performa secara keseluruhan. Insertion Sort bekerja dengan baik pada array kecil dan hampir terurut.

  3. Tail Recursion Optimization: Beberapa bahasa pemrograman dan kompiler mendukung tail recursion optimization. Tail recursion adalah bentuk rekursi di mana panggilan rekursif terakhir dalam fungsi. Dalam kasus tail recursion, kompiler dapat mengoptimalkan rekursi menjadi iterasi, yang dapat mengurangi overhead rekursi dan mencegah stack overflow untuk array yang sangat besar. Meskipun Quick Sort rekursif tidak sepenuhnya tail recursive, teknik transformasi tertentu dapat diterapkan untuk membuatnya lebih cocok untuk tail recursion optimization.

  4. Randomisasi Input: Jika Anda khawatir tentang kemungkinan kasus terburuk yang disebabkan oleh input yang terurut atau hampir terurut, Anda dapat merandomisasi input array sebelum melakukan Quick Sort. Merandomisasi input akan secara efektif mengurangi kemungkinan pemilihan pivot yang buruk dan mendekati performa rata-rata.

Quick Sort dalam Berbagai Bahasa Pemrograman

Quick Sort adalah algoritma yang sangat umum dan diimplementasikan dalam hampir semua bahasa pemrograman populer. Berikut adalah contoh implementasi Quick Sort dalam beberapa bahasa:

Python:

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

# Contoh penggunaan
arr = [7, 2, 1, 6, 8, 5, 3, 4]
sorted_arr = quicksort(arr)
print(sorted_arr) # Output: [1, 2, 3, 4, 5, 6, 7, 8]

Java:

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return (i + 1);
    }

    public static void main(String[] args) {
        int[] arr = {7, 2, 1, 6, 8, 5, 3, 4};
        quickSort(arr, 0, arr.length - 1);
        System.out.print("Sorted array: ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

C++:

#include <iostream>
#include <vector>

using namespace std;

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    vector<int> arr = {7, 2, 1, 6, 8, 5, 3, 4};
    quickSort(arr, 0, arr.size() - 1);
    cout << "Sorted array: ";
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

Implementasi di atas hanyalah contoh dasar. Dalam praktiknya, Anda mungkin menemukan implementasi Quick Sort yang lebih kompleks dan dioptimalkan dalam library standar bahasa pemrograman.

Kesimpulan

Quick Sort adalah algoritma pengurutan yang powerfull dan efisien, terutama dalam rata-rata kasus. Dengan memahami cara kerjanya, kelebihan dan kekurangannya, serta teknik optimasinya, Anda dapat memanfaatkannya secara efektif dalam berbagai aplikasi pengolahan data. Meskipun memiliki potensi kasus terburuk, dengan pemilihan pivot yang baik dan optimasi lainnya, Quick Sort tetap menjadi salah satu algoritma pengurutan terpopuler dan terpraktis yang tersedia.

Bagaimana pengalamanmu dengan Quick Sort? Apakah ada tips atau trik lain yang ingin kamu bagikan? Yuk, diskusi di kolom komentar!

Posting Komentar