퀵소트

http://www.algolist.net/Algorithms/Sorting/Quicksort

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

void quickSort(int a[], int, int);

int main() {

    int data[10000];

    int i, j, n, x;

    srand(time(NULL));

    printf("자료의 갯수: ");

    scanf("%d", &n);

    printf("\n정렬전:\n");

    for(i=0;i<n;++i) data[i]=rand();

    for(i=0;i<n;++i) printf("%8d", data[i]);

    printf("\n정렬후:\n");

    quickSort(data, 0, n-1);

    for(i=0;i<n;++i) printf("%8d", data[i]);

    return 0;

}

void quickSort(int arr[], int left, int right) {

    int i=left, j=right;

    int tmp;

    // 피봇(축값)으로 left와 right의 중간에 있는 값을 정한다.

    int pivot=arr[(left+right)/2];

 

    /* partition */

    // 축값보다 작은 부분과 축값보다 큰 부분으로 나눈다.

    while(i<=j) {

        // 앞부분은 축값보다 작은 값이 오기 때문에 작은 값이면 넘어가고

        // 축값보다 같거나 큰 값이 나오면 멈춘다. 

        // 축값이 가운데 있기 때문에 반드시 멈추는 것이 보장되어 있다.

        // 다른 말로는 i값의 범위에 대해서 걱정을 하지 않고  

        // 늘여갈 수 있다는 뜻이다.

        // 뒷부분은 축값보다 큰 값이 오기 때문에 큰값이면 넘어가고

        // 축값보다 같거나 작은 값이 나오면 멈춘다.

        // 축값이 가운데 있기 때문에 반드시 멈추는 것이 보장되어 있다.

        // 다른 말로는 j값의 범위에 대해서 걱정을 하지 않고  

        // 줄여갈 수 있다는 뜻이다.

        // 피봇이 있던 장소를 넘어 가게 되어도 

        // i 의 경우에는 축값보다 같거나 큰 값이 기다리고 있다.

        // 피봇이 있던 장소를 넘어 가게 되어도 

        // j 의 경우에는 축값보다 같거나 작은 값이 기다리고 있다.

        // 따라서 i나 j의 범위에 신경을 쓰지 않고도 늘리거나 줄일수 있다.

        // 이 점이 이렇게 중간에 위치한 값을 피봇(축값)으로 사용하는

        // 이점이라고 할 수 있다.

        while (arr[i]<pivot) ++i;

        while (arr[j]>pivot) --j;

        if(i<=j) {

            // 여기서는 앞부분에서 찾은 큰 값과 

            // 뒷부분에서 찾은 작은 값을 서로 바꾸어 주고

            // i의 값을 증가, j의 값을 감소 시킨다.

            // 사실 i==j일 때는 SWAP을 해줄 필요는 없다.

            // 하지만 if문을 매번 물어보는 비용과

            // 한번 불필요한 SWAP을 해주는 비용을 비교해 보면

            // 이렇게 불필요한 경우에도 SWAP을 해주는 것이 이익일수 있다. 

            tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; 

            ++i; --j;

        }

    }

 

    /* recursion */

    // 여기서 이 퀵정렬이 다른 버전과 조금 다른 점이 있다.

    // 보통 쓰는 버전은 left위치, 혹은 right위치의 값을 축값으로 사용한다.

    // 나중에 축값의 위치가 정해지면 SWAP을 한번 해주어야 한다. 

    // 앞에서 부터 이 축값의 위치보다 한칸 앞까지 퀵정렬을 하고

    // 이 축값의 위치보다 한칸 뒤에서 부터 끝까지 퀵정렬을 하는 방식으로

    // 순환호출을 한다. 

    // 여기서는 j의 위치와 i의 위치를 가지고 바로 순환호출을 하게 된다.

    // 이렇게 하는 것도 조금은 퀵정렬의 범위를 줄이는 효과를 가져온다.

    if(left<j) quickSort(arr, left, j);

    if(i<right) quickSort(arr, i, right);

}