[알고리즘] 퀵 정렬(QuickSort)

퀵 정렬

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

---

특징

• 불안정 정렬이다.
• 속도가 빠른 정렬 알고리즘이다.
• 추가 메모리 공간을 필요로 하지 않는다.
• 피벗을 선택하는 위치에 따라 시간복잡도가 달라질 수 있다.

과정

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

구현

코드(C++)

int partition(int list[], int left, int right){
  int pivot, temp;
  int low, high;

  low = left;
  high = right + 1;
  pivot = list[left]; 

  do{
    do {
      low++; 
    } while (low<=right && list[low]<pivot);

    do {
      high--; 
    } while (high>=left && list[high]>pivot);

    if(low<high){
      SWAP(list[low], list[high], temp);
    }
  } while (low<high);

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

  return high;
}

// 퀵 정렬
void quick_sort(int list[], int left, int right){

  if(left<right){
   
    int q = partition(list, left, right); 
    
    quick_sort(list, left, q-1);
    quick_sort(list, q+1, right);
  }

}