Quick sort source

퀵소트

1. Pivot(기준값)을 정한다.

2. Pivot보다 작은 원소들은 왼쪽으로, pivot보다 큰 원소들은 오른쪽으로 보낸다.

3. pivot을 기준으로 왼쪽 배열과 오른쪽 배열을 새로운 배열로 정하고, 각 배열 구간에 대해 1번 과정을 재귀적으로 반복한다.

* 일반적으로 처음의 원소 또는 가장 마지막 원소를 pivot으로 잡는방법을 이용

#include<stdio.h>
#define SWAP(A,B) {int temp = A; A=B; B=temp;}
int arr[101];
 
void quick_sort(int s, int e)
{
    if(s>=e) return;
    int p = s;
    int l = s+1;
    int r = e;
 
    while(l<=r)
    {
        while((l<=e) && (arr[l]<=arr[p])) l++;
        while((r>=s+1) && (arr[r]>=arr[p])) r--;
        if(l<r)
            SWAP(arr[l], arr[r]);
    }
 
    SWAP(arr[p], arr[r]);
    quick_sort(s, r-1);
    quick_sort(r+1, e);
}
 
 
int main()
{
    int cnt = 0;
    int i=0;
    scanf("%d", &cnt);
 
 
    for(; i<cnt; i++)
        scanf("%d", &arr[i]);
 
    quick_sort(0, cnt-1);
 
    for(i=0; i<cnt; i++)
        printf("%d ", arr[i]);
 
    printf("\n");
    return 0;
}