Quicksort

Quicksort란?

평균적으로 가장 빠른 정렬
O(n logn)의 시간복잡도를 가진다

정렬 방법

1. 리스트 안에 한 요소를 피벗으로 설정한다.
2. 피벗보다 작은 요소를 피벗의 왼쪽, 피벗보다 큰 요소는 피벗의 오른쪽으로 옮긴다.
3. 정렬되어 있는 피벗이 아닌 리스트들을 다시 이러한 방법으로 정렬한다.

구현 코드

#include <stdio.h>
#define swap(x,y,t) ((t)=(x), (x)=(y), (y)=(t))
int partition(int list[], int left,int right)
{
    int pivot,temp,low,high;
    low = left;
    high= right+1;
    pivot=list[left];
    do
    {
        do
        {
            low++;
        }while(list[low]<pivot && low<=right);
        do
        {
            high--;
        }while(list[high]>pivot);

        if(low<high)
        {
            swap(list[low],list[high],temp);
        }
    }while(low<high);
    swap(list[left],list[high],temp);
    return high;
}

void quicksort(int list[], int left,int right)
{
    if(left<right)
    {
        int q=partition(list, left, right);
        quicksort(list,left,q-1);
        quicksort(list,q+1,right);
    }
}


int main()
{
    int list[6]={10,2,20,7,50,1};
    quicksort(list,0,5);
    for(int i=0; i<6; i++)
    {
        printf("%d ",list[i]);
    }
    return 0;
}

코드 설명

변수 설명 - pivot : 정렬 기준, low : 피벗 보다 큰 값을 가르킬 인덱스, high : 피벗보다 작은 값을 가르킬 인덱스

함수 partition
[반복]
피벗을 맨앞 수로 잡고 list[low]의 값이 피벗보다 클 때까지 증가시키고
high값을 list[high]값이 피벗보다 작을 때까지 감소시킨다.
swap을 써서 list[low]값과 list[high]값을 바꾼다.
[반복]
마지막으로 피벗을 list[high]값과 바꿔주면 피벗을 기준으로 왼쪽에는 작은 값 오른쪽에는 큰 값이 들어가고 피벗의 인덱스를 반환한다.

함수 quicksort
[반복]
partition 함수에서 받아온 피벗의 인덱스를 받고
피벗의 인덱스를 기준으로 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
[반복]