Tuesday, November 29, 2011

Quick Sort dalam bahasa C


#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

#define MAX 30
#define INPUT 'i'
#define OUTPUT 'o'
#define TRUE 1
#define FALSE 0
#define _MY_DEBUG
#if defined(_MY_DEBUG)
    #define TRACE_LINE printf("\n\n- Program Statistics :\n1. File : %s\n2. Date : %s\n3. Time : %s\n",__FILE__,__DATE__,__TIME__);
#else
    #define TRACE_LINE
#endif

int ChoosePivot(int, int);
    void InputOutput(int*, const int, const char),
        QuickSort(int*, int, int),
    Swap(int*, int*),
FreeBuffer(int*);

int main(int argc, char *argv[]) {
    system("COLOR 5");
    int *buffer = NULL, max;
    printf("Implementasi Quick Sort [Ascending]\nJumlah data [MAX:30] : ");
    scanf("%d",&max);
    fflush(stdin);
    if((max > FALSE) && (max <= MAX)) {
        buffer = (int*)calloc(max,sizeof(int));
        InputOutput(buffer,max,INPUT);
        printf("\n1. Data yang anda masukkan : ");
        InputOutput(buffer,max,OUTPUT);
        QuickSort(buffer,FALSE,(max-TRUE));
        printf("\n2. Data setelah disorting : ");
        InputOutput(buffer,max,OUTPUT);
        FreeBuffer(buffer);
    }
    TRACE_LINE;
    getch();
    fflush(stdin);
    return(EXIT_SUCCESS);
}

void InputOutput(int* buffer, int max, const char STAT) {
    int i;
    if(INPUT == STAT) {
        for(i = 0; i < max; ++i) {
            printf("%d. Data ke-%d : ",(i+TRUE),(i+TRUE));
            scanf("%d",&buffer[i]);
            fflush(stdin);
        }
    } else if(OUTPUT == STAT) {
        for(i = 0; i < max; ++i) {
            printf("%d ",buffer[i]);
        }
    }
}

int ChoosePivot(int top, int bottom) {
    return((top+bottom)/2);
}

void QuickSort(int* buffer, int bottom, int top) {
    int i, j, k, pivot; // m = bottom, n = top;
    if(bottom < top) {
        pivot = ChoosePivot(bottom,top);
        Swap(&buffer[bottom],&buffer[pivot]);
        i = bottom+TRUE; j = top; k = buffer[bottom];
        while(i <= j) {
            while((i <= top) && (buffer[i] <= k)) {
                ++i;
            }
            while((j >= bottom) && (buffer[j] > k)) {
                --j;
            }
            if(i < j) {
                Swap(&buffer[i],&buffer[j]);
            }
        }
        Swap(&buffer[bottom],&buffer[j]);
        QuickSort(buffer,bottom,(j-TRUE));
        QuickSort(buffer,(j+TRUE),top);
    }
}

void Swap(int* buffer1, int* buffer2) {
    int tmp = *buffer1;
    *buffer1 = *buffer2;
    *buffer2 = tmp;
}

void FreeBuffer(int* buffer) {
    free(buffer);
    buffer = NULL;
}

No comments:

Post a Comment