[알고리즘👽] 10. 퀵 정렬 (Quick sort)

퀵정렬 소개

퀵정렬

 

퀵 정렬은 합병 정렬과 같은 방법으로 작동한다. 바로 재귀이다. 이건 기본적으로 데이터를 분할하여 배열에 0개 또는 1개의 항목이 남을 때까지 분할하고 개별적으로 정렬하는 방식이다.

이때 피벗포인트라고 불리는 단일 요소를 선택하여 수행한다. 어떤 배열에서 어떤 요소를 선택하든 중요하지 않다. 그저 만약 한 요소를 선택했다면 해당 요소보다 작은 것은 왼쪽으로 큰 것은 오른쪽으로 옮겨야한다. 이건 정렬이 아니라 그저 옮기에 가깝다.

즉 배열을 순회하면서 선택한 수보다 작은 것을 모두 선택해서 왼쪽으로 옮긴다. 모두 확인한 다음에 가져온 것끼리 배열한다.

피봇 helper 소개

배열이 주어질 때 한 요소를 피벗 포인터로 지정한다. 그 후 배열 속 요소를 재배치하는 함수를 작성한다. 피벗보다 작은 값은 왼쪽으로 이동하며 피벗보다 큰 값은 모두 오른쪽으로 이동한다. 이때 양쪽의 순서는 중요하지 않다.

여기서 중요한 건 헬퍼가 제자리에서 수행해야 한다는 것이다. 새배열을 만들면 안되고 인덱스를 반환해야한다.

피벗 고르기

퀵 정렬의 실행 시간은 피벗의 위치 선택에 따라 달라진다. 이상적으로는 데이터 집합의 중간값이 되어야한다. 하지만 데이터가 무엇인지, 무슨 순서인지 모른다면 중간값을 고르기 어렵다.

대신 첫 번째나 마지막이나 중간요소나 아무거나 선택해도 상관없다. 일단 여기서는 첫 번째 값을 선택한다.

let arr = [5,2,1,8,4,7,6,3]

pivot(arr); // 4

arr;
// [2,1,4,3,5,8,7,6]
// [1,4,3,2,5,7,8,6]
// [3,2,1,4,5,7,8,6]
// [4,1,2,3,5,6,8,7]
// 왼쪽과 오른쪽의 순서는 중요하지 않다.

피봇 의사코드

• 3개의 인자를 받는다 : 배열, 시작 index, 끝 index (기본값으로 시작 인덱스는 0, 끝 인덱스는 배열 길이 -1이다)
• 배열의 시작점을 피벗으로 잡는다
• 변수에 현재 피벗 인덱스를 저장한다.
• 처음부터 끝까지 루프를 돌린다
  • 만약 피벗이 현재 요소보다 크다면 피벗 인덱스 변수를 증가시키고 현재 요소와 피벗 인덱스의 요소를 바꾼다
• 피벗 인덱스에 시작 엘리번트를 스왑한다
• 피벗 인덱스를 반환한다.

피봇 helper 함수 구현

// First Version
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;
}

// Version with ES2015 Syntax
function pivot(arr, start = 0, end = arr.length - 1) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };

  // We are assuming the pivot is always the first element
  let pivot = arr[start];
  let swapIdx = start;

  for (let i = start + 1; i <= end; i++) {
    if (pivot > arr[i]) {
      swapIdx++;
      swap(arr, swapIdx, i);
    }
  }

  // Swap the pivot from the start the swapPoint
  swap(arr, start, swapIdx);
  return swapIdx;
}

pivot([4,8,2,1,5,7,6,3])

퀵 정렬 구현

새로운 배열을 만들지 않고 제자리에서 일어난다

function quickSort(arr, left = 0, right = arr.length - 1) {
    if( left < right) {
        let pivotIndex = pivot(arr, left, right); // 3
        // left
        quickSort(arr, left, pivotIndex -1);    
        // right
        quickSort(arr, pivotIndex + 1, right);    
    }
    return arr
}

quickSort([4,6,9,1,2,5,3])

퀵 정렬을 위한 빅오 복잡도

시간복잡도(Best)	시간복잡도(평균)	시간복잡도(최악)	공간복잡도
O(n log n)	O(n log n)	O(n^2)	O(log n)

최악의 케이스는 항상 작은 요소나 항상 큰 요소를 선택할 때. 즉 정렬된 상태일 때 문제가 발생한다