ALGORITMA STRUKTUR DATA SORTING DENGAN METODE QUICK SHORT

ALGORITMA STRUKTUR DATA SORTING DENGAN METODE QUICK SHORT

Pengantar Quick Short


        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:
  1. Ambil sebuah elemen, yang disebut dengan pivot, pada sebuah daftar.
  2. 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.
  3. 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 :
#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;
}
view raw quickshort.c hosted with ❤ by GitHub


ini merupakan gambar simulasi dari quick short
quick short
simulasi quick short

semoga bermanfaat dan berkah ammin..

Formulir Kontak

Shipping & Returns

Email : wahyuumaya@gmail.com
Instagram : wahyuumaya
Telegram : wahyuumaya
Facebook : wahyuumaya
Whatsapp : Klik aja disini

Info Section

Closet 2.0