quick sort

#include <stdio.h>

void quick_sort(int arr[], int s, int e) {

    int left, right, pivot;

    // 처음에 s번째 값을 pivot로 정하였다.

    // 또 left가 s로 출발했기 때문에 pivot보다 큰 값을 발견하면

    // 이 left의 위치에 옮겨도 된다. (원래의 값은 pivot에 보관되어 있다)

    pivot=arr[s];

    left=s;

    right=e;

    

    // left가 right보다 작을 동안 계속해서 다음을 실행한다.

    while(left<right) {

        // 오른쪽에는 pivot보다 같거나 큰 값들이 온다.

        // 따라서 pivot보다 작을 값을 찾을 때 까지 왼쪽으로 이동한다.

        // 이 때에도 left가 right보다 작을 동안에만 이동을 한다.

        while(arr[right]>=pivot&&left<right) { right-=1; }

        // 이 곳에 오면 pivot보다 작은 값 arr[right]를 발견하였다.

        // 만약 left와 right가 같을 경우에는 바깥의 while문을 탈출하게 된다.

        // left와 right가 서로 다르다면 여전히 left<right를 만족한다.

        // 이 때 arr[left]의 값은 [출발시점에는] 이미 보관되어 있다.

        // 따라서 이 자리에 arr[right]의 값이 들어가도 된다.

        if(left!=right) { arr[left]=arr[right]; }      

        // 이후에 left는 pivot보다 큰 값을 찾아서 오른쪽으로 이동하게 된다.

        while(arr[left]<=pivot&&left<right) { left+=1; }

        // 만약 left와 right가 서로 다르다면 여전히 left<right이다.

        // 또 위에서 이미 arr[right]를 이동해서 보관했기 때문에 이 자리에

        // 바로 위에서 새로 구한 pivot보다 큰 값인 arr[left]를 이동시킬 수 있다.

        // 이렇게 이동시키고 나면 다시 while루프의 처음으로 돌아갔을 경우에

        // arr[left]의 자리에 pivot보다 작은 값을 이동 시킬 수 있는 준비를 여기에서 한 것이다

.

        // 이 경우에 right의값을 1 감소 시킨다.

        // 이 것은 무한 루프를 피하기 위해서 꼭 필요한 조치이다.

        if(left!=right) {

            arr[right]=arr[left];

            right-=1;

        }

    }

    // 탈출 후에는 left==right 라는 조건을 만족한다. 

    // 따라서 pivot값을 left또는 right어느쪽에 보관하더라도 같은 결과가 된다.

    // 위의 과정을 추적해 보면 이렇게 함으로써 분할이 완성된 다는 것을 알 수 있다.

    

    arr[left]=pivot; 

    pivot=left;     

    

    if(s+1<pivot) {     

        quick_sort(arr, s, pivot-1);

    }

    if(e>pivot+1) {     

        quick_sort(arr, pivot+1, e);

    }

}

int main() {

    int arr[10]={26,5,37,1,61,11,59,15,48,19};

    int i, n=10;

    for(i=0;i<n;i+=1) {

        printf("%d ", arr[i]);

    }

    printf("\n");

    quick_sort(arr,0,n-1);

    for(i=0;i<n;i+=1) {

        printf("%d ", arr[i]);

    }

    printf("\n");

    return 0;

}