Data Structure - Sorting ( Quick Sort )

Quick Sort

quick sort는 불안전 정렬 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 비교 정렬에 속합니다. 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 속도를 자랑하는 정렬 방법입니다. 합병 정렬(merge sort)와 달리 퀵 정렬은 리스트를 비균등하게 분할합니다.

 

분할 정복(divide and conquer)방법

문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략입니다.
분할 정복 방법은 대개 순환 호출을 이용해서 구현합니다.

과정 설명

• 리스트 안에 있는 한 요소를 선택합니다. 이렇게 고른 원소를 피벗(pivot)이라고 합니다.
• 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨집니다. 
• 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬합니다.
  • 분할된 부분 리스트에 대하여 순환 호출을 이용하여 정렬을 반복합니다.
  • 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복합니다.
• 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복합니다.
  • 리스트의 크기가 0이나 1이 될 때까지 반복합니다.

/quick_sort.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define ARR_SIZE 100
 
int seqSearch(int a[], int k, int n)
{
    int i;
    for (i = 1; i < n && a[i] != k; i++)
        ;
 
    if (i >= n)
        return -1;
    return i;
}
 
int swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
 
void insertionSort(int a[], int n)
{
    /* sort a[0:n - 1] into nondecreasing order( 오름 차순 ) */
    int i, j, key;
    for (i = 1; i < n; i++)
    {
        key = a[i];
        // 현재 정렬된 배열은 i - 1까지 이므로 i - 1번째부터 역순으로 조사합니다.
        for (j = i - 1; j >= 0 && a[j] > key; j--)
            a[j + 1] = a[j];
        a[j + 1] = key;
    }
}
 
int partition(int list[], int left, int right)
{
    int pivot;
    int low, high;
 
    low = left;
    high = right + 1;
    pivot = list[left]; // 정렬할 리스트의 가장 왼쪽 데이터를 피벗으로 선택 ( 임의의 값을 피벗으로 선택 )
 
    /* low와 high가 교차할 때까지 반복 (low < high) */
    do
    {
        /* list[low]가 피벗보다 작으면 계속 low를 증가 시켜줘야 한다. */
        do
        {
            low++;
        } while (list[low] < pivot && low <= right); // low가 만약에 right이 된다면 멈처 주어야 합니다.
 
        do
        {
            high--;
        } while (list[high] > pivot && high >= left);
 
        // 만약 low와 high가 교차하지 않았으면 list[low]를 list[high]와 교환
        if (low < high)
            swap(list + low, list + high);
    } while (low < high);
 
    // low와 high가 교차했으면 반복문을 빠져나와 list[left]와 list[high]을 교환해줘야 한다.
    swap(list + left, list + high);
 
    // 피벗의 위치인 high를 반환해주어야 합니다.
    return high;
}
 
void quick_sort(int list[], int left, int right)
{
    /* 정렬할 범위가 2개 이상의 데이터가렴( 리스트의 크기가 0이나 1이 아니라면) */
    if (left < right)
    {
        // partition함수를 호출하여 피벗을 기준으로 리스트를 비균등 분할 - 분할(Divide)
        int q = partition(list, left, right);
 
        // 피벗을 제외한 2개의 부분 리스트를 대상으로 순환 호출
        quick_sort(list, left, q - 1);  // (left ~ 피벗 바로 앞) 앞쪽 부분 리스트 정렬 - 정복(Conquer)
        quick_sort(list, q + 1, right); // (피벗 바로 뒤 ~ right) 뒤쪽 부분 리스트 정렬 - 정복(Conquer)
    }
}
 
void printArr(int a[], int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
 
    putchar('\n');
}
 
int main(void)
{
    int sortArr[ARR_SIZE] = {0};
    int count = 0;
 
    FILE *fp_read = fopen("sort.txt", "r");
    while ((fscanf(fp_read, "%d", sortArr + count) != EOF))
    {
        count++;
    }
 
    printf("original array: ");
    printArr(sortArr, count);
 
    // printf("[ 4 ] is in index %d\n", seqSearch(sortArr, 4, count));
 
    int sortArr_2[ARR_SIZE];
    memcpy(sortArr_2, sortArr, sizeof(int) * ARR_SIZE);
    printf("insertion sort: ");
    insertionSort(sortArr_2, count);
    printArr(sortArr_2, count);
 
    int sortArr_3[ARR_SIZE];
    memcpy(sortArr_3, sortArr, sizeof(int) * ARR_SIZE);
    printf("quiuck sort:\t");
    quick_sort(sortArr_3, 0, count - 1);
    printArr(sortArr_3, count);
 
    return 0;
}
 
 
// original array: 3 2 4 1 9 8 
// insertion sort: 1 2 3 4 8 9 
// quiuck sort: 1 2 3 4 8 9

 

• 장점
  
  • 속도가 빠르다.
    • 시간 복잡도가 O(nlogn)을 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
  • 추가 메모리 공간을 필요로 하지 않는다.
    • 퀵 정렬은 O(logn)만큼의 메모리를 필요로 한다.
• 단점
  • 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.