Berdasar dari wikipedia Quicksort merupakan Algoritma Sorting yang dikembangkan oleh Tony Hoare yang, secara kasus rata-rata, membuat pengurutan O(n log n) untuk mengurutkan n item. Algoritma ini juga dikenal sebagai Partition-Exchange Sort atau disebut sebagai Sorting Pergantian Pembagi. Pada kasus terburuknya, algoritma ini membuat perbandingan O(n2), malaupun kejadian seperti ini sangat langka. Quicksort sering lebih cepat dalam praktiknya dari pada algoritma O(n log n) yang lainnya.[1] Dan juga, urutan dan referensi lokalisasi memori quicksort bekerja lebih baik dengan menggunakan cache CPU, jadi keseluruhan sorting dapat dilakukan hanya dengan ruang tambahan O(log n. Quicksort merupakan sorting pembanding dan pada implementasi efisien tidak merupakan algoritma sorting yang stabil.
Algoritma
Quicksort merupakan Algoritma Pembagi. Pertama sekali quicksort membagi list yang besar menjadi dua buah sub list yang lebih kecil: element kecil dan element besar. Quicksort kemudian dapat menyortir sub list itu secara rekursif.
Langkah-Langkah pengerjaannya ialah:
- Ambil sebuah elemen, yang disebut dengan pivot, pada sebuah daftar.
- Urutkan kembali sebuah list sehingga elemen dengan nilai yang kecil dari pivot berada sebelum pivot, sedangkan seluruh element yang memiliki nilai yang lebih besar dari pivot berada setelahnya (nilai yang sama dapat berada pada pivot setelahnya). Setelah pemisahan, pivot berada pada posisi akhirnya. Operasi ini disebut Partition.
- Sub list kemudian disortir secara recursif dari elemen yang lebih kecil dan sub list dari elemen yang lebih besar.
Kasus dasar dari rekusrif ialah list dari besaran nol atau satu, yang tidak perlu untuk di sorting.
berikut kode quick short versi ane sebagai contoh saja :
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#include <time.h> | |
#define max 100000 | |
int s; | |
//unsigned int t1, t2, t3; | |
void input (int n, int [max]); | |
void quick_sort(int [max], int , int , int ); | |
void tukar_data(int *, int *); | |
main(){ | |
int Dekla [max] = {3, 10, 4, 6, 8, 9, 7, 2, 1, 5}; | |
int pil, n, j = 0, i; | |
double t1, t2, t3; | |
puts("\t-- Sorting --"); | |
puts("\t-- Quick Sort --\n"); | |
puts("-- MENU --"); | |
puts("1. data sudah di Deklarasi"); | |
puts("2. Inputan"); | |
puts("3. Random"); | |
puts("------------------"); | |
printf("Pilih : "); scanf("%d", &pil); | |
fflush(stdin); | |
switch(pil){ | |
case 1: | |
puts("=============================================="); | |
printf("Data sebelum Diurutkan : "); | |
for(n = 0; n < 10; n++){ | |
printf("%d ", Dekla[n]); | |
} | |
puts("\n=============================================="); | |
quick_sort(Dekla, 10, 0, 10-1); | |
puts("\n=============================================="); | |
printf("Data setelah Diurutkan : "); | |
for(n = 0; n < 10; n++){ | |
printf("%d ", Dekla[n]); | |
} | |
puts("\n=============================================="); | |
break; | |
case 2: | |
puts("---------------------------------"); | |
printf("Masukkan Jumlah Data : "); scanf("%d", &n); | |
puts("---------------------------------"); | |
fflush(stdin); | |
input(n, Dekla); | |
puts("\n=============================================="); | |
printf("Data sebelum Diurutkan : "); | |
for(j = 0; j < n; j++){ | |
printf("%d ", Dekla[j]); | |
} | |
puts("\n=============================================="); | |
quick_sort(Dekla, n, 0, n-1); | |
puts(""); | |
printf("Data sesudah Diurutkan : "); | |
for(j = 0; j < n; j++){ | |
printf("%d ", Dekla[j]); | |
} | |
puts("\n=============================================="); | |
break; | |
case 3: | |
puts("---------------------------------"); | |
printf("Masukkan Jumlah Data : "); scanf("%d", &n); | |
puts("---------------------------------"); | |
fflush(stdin); | |
for(i = 0; i < n; i++){ | |
//srand(time(&s)*(i+1)); | |
Dekla[i] = rand()%100000; | |
} | |
puts("\n=============================================="); | |
/*printf("Data sebelum Diurutkan : "); | |
for(j = 0; j < n; j++){ | |
printf("%d ", Dekla[j]); | |
}*/ | |
puts("\n=============================================="); | |
//t1 = GetTickCount(); | |
t1 = clock(); | |
quick_sort(Dekla, n, 0, n-1); | |
//t2 = GetTickCount(); | |
t2 = clock(); | |
t3 = t2 - t1; | |
// puts(""); | |
/*printf("Data sesudah Diurutkan : "); | |
for(j = 0; j < n; j++){ | |
printf("%d ", Dekla[j]); | |
}*/ | |
// puts("\n=============================================="); | |
// puts("------------------------------------------"); | |
//printf("Waktu Komputasi : %d\n", t3); | |
printf("Waktu Komputasi : %f\n", t3); | |
puts("------------------------------------------"); | |
break; | |
default: | |
exit(0); | |
break; | |
} | |
} | |
void input (int n, int var[100000]){ | |
int i = 0; | |
for(; i < n; i++){ | |
printf("Masukkan data ke-%d = ", i+1); scanf("%d", &var[i]); | |
fflush(stdin); | |
} | |
} | |
void quick_sort(int var [100000], int n, int L, int R){ | |
int x, i, j; | |
x = var[(L+R)/2]; | |
i = L; | |
j = R; | |
while(i <= j){ | |
while(var[i] < x){ | |
i++; | |
} | |
while(x < var[j]){ | |
j--; | |
} | |
if(i <= j){ | |
tukar_data(&var[i], &var[j]); | |
i++; | |
j--; | |
} | |
} | |
if(L < j){ | |
quick_sort(var, n, L, j); | |
} | |
if(i < R){ | |
quick_sort(var, n, i, R); | |
} | |
} | |
void tukar_data(int *a, int *b){ | |
int temp; | |
temp = *a; | |
*a = *b; | |
*b = temp; | |
} | |
ini merupakan gambar simulasi dari quick short
simulasi quick short |
semoga bermanfaat dan berkah ammin..