QuickSort 정리

목표

• QuickSort 알고리즘 이해
• QuickSort 알고리즘을 자바스크립트로 구현
• QuickSort 특징 이해
• QuickSort 시간복잡도 이해

QuickSort 알고리즘 개념

• 불안정 정렬이며 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬이다.

 

• 정렬 속도가 매우 빠르다.

 

• 분할 정복 알고리즘이다.
  • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 후, 결과들을 모아서 원래의 문제를 해결하는 전략
  • 리스트를 두개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 부분 리스트를 다시 합하여 전체가 정렬되도록 하는 방법
    • 분할(Divide) : 입력 배열(arr)을 arr[0](pivot)을 기준으로 비균등 하게 2개의 부분 배열로 분할한다.
    • 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 재귀 호출한다.
    • 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.

 

QuickSort 예시

https://needjarvis.tistory.com/583

QuickSort 자바스크립트 코드

const quickSort = function (arr,func = el => el) {

  // 첫 요소를 pivot으로 정한다.
  // left배열, right배열을 만들고 pivot보다 작은것은 left배열에 push하고 
  // pivot보다 큰것은 right배열에 push한다.
  // arr = [...left,pivot,...right]
  // quickSort(left), quickSort(right)를 한다.


  //quickSort([])일때는 빈배열을 리턴
  if(arr.length===0){
    return []
  }
  let pivot = arr[0]
  let left = [];
  let right = [];
  for(let i = 1;i<arr.length;i++){
    if(func(arr[i])<func(pivot)){
      left.push(arr[i])
    }
    else{
      right.push(arr[i])
    }
    //pivot과 같은 값은 없다.

  }

  return [...quickSort(left),pivot,...quickSort(right)]

};

QuickSort 알고리즘의 특징

• 장점
  • 빠르다.
    • 불필요한 데이터 이동을 줄이고 먼거리의 데이터를 교환하면서 한 번 결정된 피벗들이 다음 연산에서 제외되기 때문이다.
  • 추가 메모리 공간을 필요로 하지 않는다.
    • O(logN)만큼의 메모리를 필요로 함

 

 

• 단점
  • 정렬된 리스트에 대해서는 불균형 분할에 의해 오히려 수행시간이 길어진다.

 

• 퀵 정렬의 불균형 분할을 방지하기 위해 pivot을 선택할 때 가장 적절한 데이터를 선택한다. (ex: 중간값)

QuickSort 시간복잡도

 

• 최상 : 분할되는 배열들의 크기가 같을경우 ->O(nlog₂n)

• 최악 : 분할되는 배열들의 크기가 극단적으로 비균등할 경우(예를들면 이미 정렬되어 있는 경우)

arr=[0,1,2,3,4,5,6,7,8]
->[0]+[1,2,3,4,5,6,7,8]
->[0,1]+[2,3,4,5,6,7,8]
->[0,1,2]+[3,4,5,6,7,8]
->[0,1,2,3]+[4,5,6,7,8]
.
.
.
->[]+[0,1,2,3,4,5,6,7,8]
->[0,1,2,3,4,5,6,7,8]

• 첫단계에서 n-1번, 두번째 단계에서 n-2번,..k번째 단계에서 n-k번, .. 3번,2번,1번 비교하므로 O(n^2)이다.

• 

 

정렬 알고리즘 시간복잡도 비교

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

• 단순, 비효율 : 삽입정렬, 선택정렬, 버블정렬
• 복잡, 효율 : 퀵정렬, 힙정렬, 합병정렬, 기수정렬