Sorting Algorithm: Quick Sort

Sekilas Mengenai Algoritma Pengurutan: Quick Sort

Algoritma Quick Sort adalah sebuah algoritma pengurutan yang ditemukan oleh Tony Hoare pada tahun 1960. Algoritma ini menggunakan teknik pembagian dan conquers (divide and conquer) yang membagi data menjadi dua bagian dan mengurutkan masing-masing bagian secara independen.

Quick Sort mengambil elemen acak dari data yang akan diurutkan dan menempatkannya sebagai pivot. Elemen-elemen lain yang lebih kecil dari pivot akan ditempatkan di sebelah kiri pivot, dan elemen-elemen yang lebih besar dari pivot akan ditempatkan di sebelah kanan pivot. Proses ini akan dilakukan berulang-ulang pada setiap bagian data yang dihasilkan sampai data terurut.

Quick Sort menjadi populer karena efisiensi waktu yang baik. Pada kondisi terbaik, rata-rata, dan paling buruk, algoritma ini memiliki kompleksitas waktu O(n log n), yang membuatnya lebih cepat dibanding algoritma pengurutan lain seperti bubble sort dan insertion sort.

Selain itu, Quick Sort juga dapat digunakan dalam berbagai aplikasi, seperti sorting array, sorting linked list, dan sorting data dalam file.

Proses Algoritma Pengurutan: Quick Sort

Proses Algoritma Quick Sort adalah sebagai berikut:

1. Pilih elemen acak dari data yang akan diurutkan sebagai pivot. 
2. Tempatkan semua elemen yang lebih kecil dari pivot ke sebelah kiri pivot dan semua elemen yang lebih besar dari pivot ke sebelah kanan pivot. Ini dapat dilakukan dengan menukar posisi elemen pada array.
3. Panggil rekursif quick sort pada bagian kiri dan bagian kanan dari pivot. 
4. Proses ini akan berlanjut hingga tidak ada bagian yang harus diurutkan lagi. 

Secara lebih rinci, Algoritma Quick Sort mengikuti tiga langkah utama:

1. Pembagian: Pilih elemen pivot dari data yang akan diurutkan. Kemudian, pisahkan data menjadi dua bagian, yaitu bagian yang elemennya lebih kecil dari pivot dan bagian yang elemennya lebih besar dari pivot. 
2. Penaklukan: Terapkan quick sort rekursif pada bagian yang elemennya lebih kecil dari pivot dan bagian yang elemennya lebih besar dari pivot. 
3. Penyatuan: Gabungkan bagian yang sudah terurut dengan pivot yang sudah dipilih sebelumnya

Quick Sort biasanya menggunakan teknik “partitioning” untuk memisahkan data menjadi dua bagian yang diinginkan. Pada teknik ini, kita memiliki dua pointer, yaitu pointer kiri dan pointer kanan. pointer kiri akan bergerak dari awal data sampai pivot dan pointer kanan akan bergerak dari akhir data sampai pivot. Kemudian jika pointer kiri menemukan elemen yang lebih besar dari pivot dan pointer kanan menemukan elemen yang lebih kecil dari pivot, maka kedua pointer akan bertukar posisi. Setelah kedua pointer bertemu, maka pivot akan ditempatkan di posisi yang tepat.

Dalam kondisi terbaik, Quick Sort memiliki kompleksitas waktu O(n log n), yang membuatnya cukup cepat untuk mengurutkan data dengan jumlah elemen yang besar. Namun dalam kondisi terburuk, ketika pivot selalu dipilih dengan cara yang salah, kompleksitas waktu bisa menjadi O(n^2).

Itu sebabnya, dalam implementasi Quick Sort, sering digunakan metode yang dinamakan “median-of-three” yang memilih pivot dengan cara mengambil median dari tiga elemen acak dari data yang akan diurutkan, sehingga memperkecil kemungkinan kondisi terburuk terjadi.

Note: Kotak yang memiliki warna ungu merupakan Pipot yang dipilih

Contoh Implementasi Dalam Bentuk Code Bahasa Pemrograman C

#include <stdio.h>
// fungsi untuk menukar posisi dua elemen
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
// fungsi partition untuk memisahkan elemen
int partition (int arr[], int low, int high)
{
int pivot = arr[high];    // pivot adalah elemen terakhir
int i = (low - 1);  // indeks elemen yang lebih kecil dari pivot
for (int j = low; j <= high- 1; j++)
{
if (arr[j] > pivot) // jika elemen saat ini lebih besar dari pivot
{
i++;    // increment index of smaller element
swap(&arr[i], &arr[j]);  // tukar posisi elemen saat ini dengan elemen yang lebih kecil
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
/* arr[] --> Array to be sorted,
low  --> Starting index,
high  --> Ending index */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);
// urutkan bagian sebelum dan sesudah partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// fungsi utama untuk mencetak array yang diurutkan
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("n");
}
int main()
{
int arr[] = {90, 87, 162, 22, 9, 1};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
printf("Array yang diurutkan: ");
printArray(arr, n);
return 0;
}

Kode di atas adalah implementasi dari algoritma pengurutan cepat (Quick Sort) dalam bahasa C. Algoritma ini digunakan untuk mengurutkan elemen dalam suatu array.

Pertama, kode tersebut menyertakan header file stdio.h yang digunakan untuk mengakses fungsi-fungsi input-output seperti printf(). Kemudian, kode tersebut mendefinisikan dua fungsi bantuan yaitu “swap()” dan “partition()”. Fungsi “swap()” digunakan untuk menukar posisi dua elemen dalam suatu array, sedangkan fungsi “partition()” digunakan untuk memisahkan elemen dalam suatu array menjadi dua bagian, yaitu bagian yang lebih besar dan bagian yang lebih kecil dari pivot.

Kemudian, kode tersebut mendefinisikan fungsi utama yaitu “quickSort()” yang menerima input berupa array, indeks awal, dan indeks akhir dari array tersebut. Fungsi ini menggunakan rekursi untuk mengurutkan elemen dalam array tersebut dengan menggunakan fungsi “partition()” sebagai dasar pengurutannya. Setelah array terurut, kode tersebut mencetak array yang sudah diurutkan dengan menggunakan fungsi “printArray()” yang didefinisikan sebelumnya.

Akhirnya, kode tersebut mendefinisikan fungsi main() yang digunakan untuk menguji implementasi algoritma pengurutan cepat dengan menggunakan array yang sudah ditentukan. Kemudian, kode tersebut mengurutkan array tersebut dengan menggunakan fungsi “quickSort()” dan mencetak array yang sudah diurutkan.

• Best Case: ketika array sudah diurutkan atau pivot yang dipilih selalu membagi array menjadi dua bagian yang seimbang.
• Average Case: ketika elemen dalam array acak.
• Worst Case: ketika array sudah terurut dalam urutan yang sama atau pivot yang dipilih selalu membagi array menjadi dua bagian yang tidak seimbang.

*n is the number of elements in the array.

Tabel di atas menunjukkan kompleksitas waktu dari algoritma Quick Sort dalam kondisi terbaik, rata-rata, dan terburuk. Pada kondisi terbaik, algoritma memiliki kompleksitas O(n log n), yang merupakan kompleksitas waktu yang baik untuk algoritma pengurutan. Namun, pada kondisi terburuk, kompleksitas algoritma menjadi O(n^2) yang dapat menyebabkan performa yang buruk jika diterapkan pada array yang besar.

Referensi:

1. https://www.programiz.com/dsa/quick-sort
2. https://www.tutorialspoint.com/data_structures_algorithms/quick_sort_algorithm.htm