퀵 정렬(Quick Sort)

Quick Sort은 '분할 정복(divide and conquer) 방법' 을 통해 주어진 배열을 정렬한다.

 

[분할 정복(divide and conquer) 방법]
문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.

 

Quick Sort은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 또한 Merge Sort와 달리 Quick Sort는 배열을 비균등하게 분할한다.

 

JavaScript Code

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])
    }
  }
  return quickSort(left).concat(pivot, quickSort(right))
}

• arr의 요소가 하나이면 arr 자체를 그대로 반환
• quickSort 초기 배열을 선언 첫 pivot 배열의 첫 번째 요소이다.
• for문을 돌면서 pivot보다 작은 것은 왼쪽 큰 것은 오른쪽 그렇지 않은 것은 pivot에 넣어준다
• quickSort 진행상황을 단계별로 보여주기 위한 코드
  - //console.log(`left: ${left}, pivot: ${pivot}, right: ${right}`)
• 재귀함수 구조로 다시 선언해서 끝날때까지 시작한다.

퀵 정렬은 다음의 단계들로 이루어진다.

• 정복 (Conquer)
  - 부분 배열을 정렬한다.
    부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
• 분할 (Divide)
  - 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열
    (피벗을 중심으로 왼쪽 : 피벗보다 작은 요소들, 오른쪽 : 피벗보다 큰 요소들) 로 분할한다.

 

장점

• 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

단점

• '불안정 정렬(Unstable Sort)' 이다.
• 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.

* 틀린 부분이 있다면 말씀 부탁드립니다!