I. 퀵 정렬 (Quick Sort)의 개요

가. 퀵 정렬의 정의

Pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 위치시키는 분할과 정복에 기반한 알고리즘

 

나. 퀵 정렬의 특징

  • 분할과 정복 기반
  • 재귀호출 구조
  • 정렬을 위한 별도의 스택이 필요
  • 수행시간 복잡도: O(n·log2n)
 

Ⅱ. 퀵 정렬의 단계 및 사례

가. 퀵 정렬의 단계

 

  • 정렬할 원소들의 집합에서 Pivot 값을 설정

  • Pivot보다 큰 값은 오른쪽, 작은 값은 왼쪽

  • 분할된 집합의 크기가 1이 될 때까지 반복
  •  

    나. 퀵 정렬의 사례

     

    void quicksort(element list[], int left, int right) {

    int pivot, i, j; element temp;

    if(left < right) {
    i = left; j = right + 1;
    pivot = list[left].key;

    do {
    do
    i++;

    while(list[i].key < pivot && i<=right);
    do
    j--;

    while(list[j].key > pivot);

    if(i < j)
    SWAP(list[i], list[j], temp);
    } while(i < j);

    SWAP(list[left], list[j], temp);

    quicksort(list, left, j - 1);

    quicksort(list, j + 1, right);

    }}