퀵 정렬 (Quick Sort)

퀵 정렬

퀵 정렬은 1) 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑합니다. 

 

1) 분할 정복

분할 정복은 문제를 2개의 문제로 분리하여 각각 해결하고, 결과를 모아 원래의 문제를 해결하는 전략입니다.

 

https://visualgo.net/en/sorting

 

퀵 정렬의 진행 과정은 다음과 같습니다.

 

1. 데이터들의 배열에서 하나의 원소를 선택합니다. 선택된 원소를 피벗(pivot)이라고 부릅니다.
2. 피벗을 기준으로 왼쪽에는 피벗보다 작은 값, 오른쪽에는 피벗보다 높은 값이 오도록 배열을 분할합니다. 
3. 피벗을 제외한 왼쪽 배열과 오른쪽 배열을 다시 정렬합니다.
4. 더이상 분할이 불가능할 때까지 반복합니다. 

퀵 정렬은 피벗을 기준으로 배열을 나누는 분할, 분할된 배열을 정렬하는 정복, 정렬된 분할 배열들을 다시 합치는 결합의 단계들로 이루어져 있습니다. 정복의 과정에서 분할된 배열의 크기가 충분히 작아지지 않았다면, 다시 분할과 정복의 과정을 재귀 호출합니다. 이때, 한 번의 반복에 최소한 피벗의 위치가 정해 지므로, 반드시 끝나는 알고리즘이라는 것을 알 수 있습니다.

 

시간 복잡도

1) 최악의 경우

퀵 정렬의 최악의 경우는 오름차순이나 내림차순으로 이미 정렬이 되어있는 경우입니다.

먼저, 오름차순으로 정렬되어 있을 때, 가장 왼쪽의 원소를 피벗으로 잡는 경우를 살펴보겠습니다. 이 경우에는 위의 그림과 같이 오른쪽에 분열된 배열만 생성될 것입니다. 이를 피벗을 설정하는 n번의 과정과, 재귀호출마다 n번의 비교 연산으로, 피벗을 설정하는 횟수 * 비교 연산 = $O(n^2)$의 시간 복잡도를 가지게 됩니다.

 

2) 최선의 경우

퀵 정렬의 최선의 경우에는 피벗이 중앙에 위치하여 원소들을 절반으로 분할 하였을 경우입니다.

만약, 데이터가 8개 일 경우, 중간 값이 피벗으로 선택되면 8개, 4개, 2개, 1개 순으로 3번에 걸쳐 데이터가 분할됩니다. 이는 n개의 데이터가 1개로 분할되기까지 $\log{n}$으로 표현할 수 있습니다. 분할의 횟수는 $\log{n}$이고, 분할될 때마다 각각 n번의 비교 연산이 이루어져 최선의 경우는 $O(n\log{n})$의 시간 복잡도를 가집니다.

 

자바스크립트 코드

function quickSort(arr){
  if(arr.length < 2){
    return arr;
  }
  
  let pivot = arr[0];
  let left = [];
  let right = [];
  
  for(let i = 1; i < arr.length; i++){
    if(arr[i] < pivot){
      left.push(arr[i]);
    }
    else if(arr[i] > pivot){
      right.push(arr[i]);
    }
    else{
      pivot.push(arr[i]);
    }
  }
  console.log(`left: ${left}, pivot: ${pivot}, right: ${right}`);
  return quickSort(left).concat(pivot, quickSort(right));
}

console.log(quickSort([13, 1, 3, 7, 9, 11, 5]));

 

장점

• 시간 복잡도가  $O(n\log{n})$인 다른 알고리즘들과 비교했을 때 속도가 빠르다는 장점을 가지고 있습니다.
• 제자리 정렬로 다른 추가적인 메모리가 필요하지 않습니다.

단점

• 정렬된 배열에 대해서는 오히려 시간이 많이 걸린다는 단점을 가집니다.
• 입력 순서와 정렬 순서가 일치하지 않을 수 있는 불안정 정렬입니다.

 

정리

퀵 정렬은 다른 알고리즘들에 비해 빈번하게 사용되고, 효율적인 알고리즘입니다. 그러나 퀵 정렬의 불균형 분할을 방지하기 위하여 피벗을 선택할 때, 데이터들을 균등하게 분할할 수 있는 원소를 선택해야 특징을 가집니다. 실제 사용할 때 이점을 꼭 기억하고 사용합시다! : )