퀵 정렬 (Quick Sort)

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

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);

}}

댓글