퀵 정렬 소개

배열 의 한 요소를 선택해서 적절한 위치에 배치시키는 것을 반복하는 정렬 방법 입니다.
랜덤으로 고르게 되는 요소를 피벗(Pivot)이라고 부릅니다.
피벗이 정렬된 위치에 자리잡으면, 퀵정렬을 피벗을 양쪽 사이드에 실행하는 것을 반복합니다.

Pivot helper 함수

퀵 정렬을 수행하기 위해서 피벗을 기준으로 배열을 재배치하는 함수를 만들어야 합니다.

• 원본 배열이 주어지고, 이 helper 함수가 pivot을 하나 지정한다.
• 피벗보다 작은 값들은 피벗의 왼쪽으로 이동시키고 피벗보다 큰 값들은 우측으로 이동시킴
• 피벗의 양쪽에 배치된 요소의 순서는 중요하지 않음
• 피벗보다 작은지 큰지만 따짐
• helper는 새 배열을 만들지 않음
• 완료되면, helper는 피벗의 Index를 반환

피벗 선택하기

퀵 정렬의 실행시간은 피벗의 선택 방법에 따라 달라질 수 있습니다. 이상적으로는 데이터 집합의 중간값이 되도록 선택해야 합니다.
이 글에서 퀵 정렬을 및 Pivot helper 함수를 구현하기 위해서 편의상 첫 번째 요소를 피벗으로 선택하겠습니다.

Pivot helper 구현하기

function pivot(arr, start=0, end=arr.length-1){
  function swap(array, i, j) {
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }

  var pivot = arr[start];
  var swapIdx = start;

  for(var i = start + 1; i < arr.length; i++){
    if(pivot > arr[i]){
      swapIdx++;
      swap(arr,swapIdx,i);
    }
  }
  swap(arr,start,swapIdx);
  return swapIdx;
}

• 배열, 시작 idx 라는 두개의 인수를 받음
• 그리고 기본 값으로 시작 인덱스는 0
• 배열의 시작 요소가 피벗이다
• 피벗 indx를 변수로 저장한다. (마지막에 바꿔줄 피벗의 위치를 계속해서 확인하기 위해)
• 살펴보는 요소보다 피벗이 클 경우에 피벗 인덱스 변수를 증가시킨 후 다음 요소와 피벗 인덱스의 요소를 교환한다.
• 반복
• 그리고 마지막에는 시작했던 피벗과 피벗 인덱스에 위치한 요소를 바꿔준다.
• 피벗 인덱스를 반환.

퀵 정렬 구현하기

• pivot helper를 호출하고
• 피벗 인덱스가 반환되면 그것을 기준으로 왼쪽과 오른족에 pivot helper 함수를 호출한다.

function quickSort(arr, left = 0, right = arr.length -1){
    if(left < right){
        let pivotIndex = pivot(arr, left) 
        // 피벗의 왼쪽
        quickSort(arr,left,pivotIndex-1);
        // 피벗의 오른쪽
        quickSort(arr,pivotIndex+1);
      }
     return arr;
} 

퀵 정렬 Big-O

O(n log n) - 최고
O(n log n) - 평균
O(n2) - 최악