퀵 정렬 (quick sort)

퀵 정렬 (quick sort)

퀵 정렬은 평균적으로 매우 빠른 수행 속도를 자랑하는 방법 입니다.

퀵 정렬은 찰스 앤터니 리처드 호어가 개발한 범용 정렬 알고리즘입니다.

다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

분할정복법

퀵 정렬은 전체리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵정렬하는 전형적인 분할정복법을 사용합니다.

퀵정렬 방법

1. 리스트 안에 있는 한 요소를 피벗으로 선택하기

2. 피벗보다 작은 요소들을 왼쪽으로 옮기고 피벗보다 큰 요소들을 오른쪽으로 옮기기

3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하게 되면 전체 리스트가 정렬됨

C 언어 코드

#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;
}

Big O 표기법 시간 복잡도 O(n log n) (평균)

퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n²)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행합니다.