Quick Sort

Quick Sort adalah salah satu teknik mengurutkan data dengan cara memindahkan suatu data ke indeks yang benar.

Kelebihan: Cepat untuk jumlah data yang banyak dan acak
Kekurangan: Tidak efektif untuk list data yang hampir terurut

Kompleksitas: O(n.log n)

Animasi visualnya dapat dilihat di visualgo.net/sorting.html

Berikut implementasinya dalam bahasa C.

#include <stdio.h>

void QuickSort(int *arr, int kiri, int kanan);
void swap(int *arr, int i, int j);

int main()
{   /* Input */
    int n;
    scanf("%d", &n);

    int arr[n], i;
    for(i = 0; i < n; i++)
        scanf("%d", &arr[i]);
   
    /* Process */
    QuickSort(arr, 0, n - 1);
   
    /* Output */
    for(i = 0; i < n; i++)
        printf("%d ", arr[i]);
}

/* Fungsi utama Quick Sort */
void QuickSort(int *arr, int kiri, int kanan)
{   if(kiri >= kanan) return;

    int indeks_pivot = kiri, pivot = arr[indeks_pivot];
    int i = kiri + 1, j;

    for(j = i; j <= kanan; j++)
        if(arr[j] < pivot)
            swap(arr, i++, j);

    swap(arr, indeks_pivot, i - 1);
    indeks_pivot = i - 1;

    QuickSort(arr, kiri, indeks_pivot - 1);
    QuickSort(arr, indeks_pivot + 1, kanan);
}

/* Fungsi untuk menukar nilai array di indeks 'i' dengan nilai array di indeks 'j' */
void swap(int *arr, int i, int j)
{   int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

Contoh Input:
8
56 74 23 12 11 16 23 41

Contoh Output:
11 12 16 23 23 41 56 74