Quick Sort

ALGORITHM/Theory

Quick Sort

Harimad 2022. 4. 28. 18:08

퀵정렬 소개
피봇 helper 소개
피봇 helper 함수 구현
퀵 정렬 구현
퀵 정렬 스택 호출 소개
퀵 정렬을 위한 빅오 복잡도

퀵정렬 소개

https://www.toptal.com/developers/sorting-algorithms

1. 배열에 0개 또는 1개의 항목이 남을 때까지 분할하여 개별적으로 정렬되는 방식이다.
2. 피벗 포인트라 부르는 단일 요소를 선택하여 수행한다. 어떤 배열에서 어떤 요소를 선택하든 문제가 되지 않는다.
3. 중앙에 있는 요소를 선택했다고 가정한다.
이제 할 일은 해당 숫자보다 작은 숫자를 왼쪽으로 옮기는 것이다.
그리고 그 숫자보다 큰 숫자는 오른쪽으로 옮긴다.

피봇 helper 소개

피봇 헬퍼 함수
1. 병합 정렬을 구현하려면 먼저 피벗의 양쪽에 있는 배열에서 요소를 배열하는 기능을 구현하는 것이 유용하다.
2. 배열이 주어지면 이 helper함수는 한 요소를 피벗으로 지정해야 한다.
3. 그런 다음 배열의 요소를 재정렬하여 피벗보다 작은 값은 모두 피벗 왼쪽으로 이동하고 피벗보다 큰 값은 모두 피벗 오른쪽으로 이동해야 한다.
4. 피벗의 양쪽에 있는 요소의 순서는 중요하지 않다!
5. helper 함수는 작업을 제자리에서 수행해야 한다. 즉, 새 배열을 만들지 않아야 한다.
6. 완료되면 helper 함수가 피벗의 인덱스를 반환해야 한다.

피벗 고르기
1. 빠른 정렬의 런타임은 부분적으로 피벗을 선택하는 방법에 따라 달라진다.
2. 이상적으로 피벗은 정렬 중인 데이터 집합에서 대략 중앙값이 되도록 선택해야 한다.
3. 단순화를 위해, 항상 피벗을 첫 번째 요소로 선택한다.

피봇 헬퍼 함수 예시

중요한 것은 5가 인덱스 4에 있고 작은 값이 왼쪽에 있고 큰 값이 오른쪽에 있는 것임.

피봇 의사코드

1. 3가지 인자를 받는게 도움된다 : 배열, 시작 인덱스(0), 끝 인덱스(배열길이-1)
2. 배열의 맨 처음요소를 피봇으로 정한다.
3. 현재 피봇 인덱스를 변수에 저장한다. (피봇이 끝나야 할 위치를 추적)
4. 배열을 처음부터 끝까지 반복순환
4-1. 피벗이 현재 요소보다 큰 경우 피벗 인덱스 변수를 늘린 다음, 현재 요소를 피벗 인덱스의 요소와 교환
5. 시작 요소(즉, 피봇)를 피봇 인덱스와 스왑한다.
6. 피봇 인덱스를 반환한다.

피봇 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;
  }
  // Version with ES2015 Syntax
  //const swap = (arr, idx1, idx2) => {
  //  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  //};

  // We are assuming the pivot is always the first element
  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 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([100,-3,2,4,6,9,1,2,5,3,23])

// [4,6,9,1,2,5,3]
// [3,2,1,4,6,9,5]
//        4
//  3,2,1    6,9,5
//      3      6
//  2,1      5  9
//    2
//  1