[알고리즘 JS] 퀵 정렬(Quick sort)과 피벗(pivot)

🐣 퀵 정렬

---

설명

• 퀵 정렬은 합병 정렬과 같은 가정으로 작동
• 재귀를 통해 해결하기 가장 쉬운 방식 중 하나
• 기본적으로 데이터를 분할하여 배열에 0개 또는 1개의 항목이 남을 때까지 분할하여 개별적으로 정렬되는 방식
• 항목은 하나 배열
• 피벗 포인트라 부르는 단일 요소를 선택하여 수행
• 어떤 배열에서 어떤 요소를 선택하든 사실상 문제가 되지 않음
• 중앙에 있는 요소 선택했을 경우, 해당 숫자보다 작은 숫자를 왼쪽으로 옮기고, 그 숫자보다 큰 숫자는 오른쪽으로 옮김
• 모두 정렬하려는게 아닌 한쪽으로 옮기는 것
• 그 숫자 하나만 올바른 위치이고, 다른 숫자들이 오른쪽이나 왼쪽에 있지만 정확한 위치는 모름
• 위의 과정을 왼쪽과 오른쪽에 반복

 

예시

• [5,2,1,8,4,7,6,3] 있을 경우
• 5보다 작은 2,1,4,3은 왼쪽으로 옮겨짐
• [2,1,4,3,'5',8,7,6] 이렇게 5는 제 위치를 찾은 것
• 이 과정을 계속해서 반복
• 재귀를 작성하고 코드를 시각화하려면 살짝 까다로울 수 있음
• 실제 동작할 때는 [5,2,1,4,3,8,7,6] 이렇게 한 다음에 5를 제 위치로 옮김

 

🐣 피봇 helper

---

퀵 정렬 첫 번째

• 파티션, 피벗 같은 의미
• 배열이 주어지면 요소를 피벗 포인트로 지정하여 배열 속 요소를 재배치하는 함수를 작성
• 피벗보다 작은 값은 모두 왼쪽으로 이동하며 피벗보다 큰 값은 모두 오른쪽으로 이동
• 양쪽의 순서는 중요하지 않고, 올바른 쪽에서 피벗보다 작거나 커야 함
• 중요한 것은 헬퍼가 제자리에서 수행해야 함
• 새 배열을 만들면 안 되고, 피벗 인덱스를 반환해야 함
• 제자리에서 모두 수행하기 때문에 새 배열을 만들지 않음
• 퀵 정렬의 실행 시간은 피벗 선택 위치에 따라 달라질 수 있기 때문에 피벗 선택은 중요한 것임
• 이상적으로 데이터 집합의 중간값이 되도록 선택해야 함
• 하지만 데이터가 무엇인지, 순서가 어떻게 되어 있는지 모른다면 쉽지 않음
• 다른 전략으로는 첫 번째 요소, 아니면 마지막 요소, 아니면 중간, 무작위 요소를 선택
• 우리는 첫 번째 요소만 선택해보겠음. 빅오에 영향을 미치긴 하지만..간단히 하기 위해서!

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

pivot(arr); //4

arr;

// any one of these is an acceptable mutation:
// [2,1,4,3,5,8,7,6]
// [1,4,3,1,5,7,6,8]
// [3,2,1,4,5,7,6,8]
// [4,1,2,3,5,6,8,7]
// there are other acceptable mutations too

• 위의 배열이 있고 피벗 함수를 호출한다면 인덱스 4를 반환
• 주의할 점은 배열을 반환하지 않음
• 하지만 arr 호출했을때 배열이 바뀐 것을 볼 수 있는데 이러한 구성 모두 타당함
• 첫 번재 요소를 골라서 피벗으로 선택
• 5를 선택하고, 5기준으로 작은 숫자 왼쪽에 배열 재배치
• 1,2,3,4의 순서는 상관없음 5 기준으로 왼쪽에 작은 숫자가 있으면 됨
• 반대로 5 오른쪽에는 순서상관없이 5보다 큰 숫자 6,7,8이 있음
• 가능한 모든 조합 가능. 순서 상관 없음!_!
• 중요한 것은 5가 최종 위치에 정렬된 위치에 있다는 것. 의사코드임

 

방법

• 피벗 또는 파티션이라 불리는 함수 작성
• 이 함수는 배열, 시작 인덱스, 끝 인덱스 세 개의 인수 받음
• 기본값으로 시작 인덱스 0, 끝 인덱스는 배열.length -1
• 배열 시작 부분에서 피벗 선택(중간이나 마지막, 무작위 위치로 변경 가능)
• 편의상 맨 첫 부분 선택, 현재의 피벗 인덱스를 변수로 저장
• 마지막에 피벗을 바꿀 위치를 계속 확인
• 시작부터 끝까지 배열에 루프를 수행
• 살펴보는 요소보다 피벗이 클 경우 피벗 인덱스 변수를 증가시킨 다음 현재 요소와 피벗 인덱스 요소를 교환
• 맨 마지막에는 시작했던 피벗과 피벗 인덱스를 바꾼 다음 피벗 인덱스 반환

  [28,41,4,11,16,1,40,14,36,37,42,18]

• 예를들어 이렇게 있을 경우
• 처음에 첫 번째 요소 28를 피벗으로 선택
• 다른 요소에서 모든 루프를 수행. 28과 41 비교. 41이 더 크기 때문에 아무것도 하지 않음
• 두번째는 4임. 28이 4보다 크기 때문에 4를 28 왼쪽에 둬야함. 하지만 여기서는 옮겨두고 28왼쪽으로 옮기는건 나중에 함
• 그리고 피벗 인덱스라는 변수를 지정
• 28보다 작은 요수의 수를 계속해서 파악해서 맨 마지막에 28을 올바른 위치로 교환하게 됨
• 4를 옮김. 피벗 뒤로
• 그다음 11을 보면 28보다 작음 . 41과 값을 바꾸고 피벗 인덱스를 1만큼 증가 (= 28보다 작은 값 현재 2개)
• 16의 경우도 동일 (= 28보다 작은 값 현재 3개)
• 1,14,18도 동일 (= 28보다 작은 값 현재 6개)
• 피벗 인덱스도 6임. 작은 값을 찾을 때마다 +1 했기 때문
• 28의 경우 인덱스 6에 들어가면 되고, 작았던 값들은 그 왼쪽에 위치 시키면 됨 (인덱스 6에 들어감 / 피벗보다 작은값은 6개 존재, 즉 7번째 위치)

 

피봇 helper 함수 구현

pivot.js

// 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])

• pivot 에 start index 값 넣고 즉 위에서는 4임
• swapIdx에는 start 0 값
• for(var i = start + 1; i < arr.length; i++)는 i는 0이 아닌 start+1값이고, length 길이만큼
• 즉 4와 4를 비교한 다음 8로 넘어가는게 아니라 그냥 4로 지정한 뒤 바로 8로 넘어가면서 루프 시작
• if(pivot > arr[i]) 피벗(4)와 arr[i] 즉 4와 8를 비교하여 더 클 경우 옮기는데, 이 경우는 그대로임. 반복문 한번 끝나고 다시 돌음
• i++해서 피벗(4)와 arr[i] 즉 4와 2를 비교
• 2가 더 작기 때문에 if문 작동하고 swapIdx++ 해서 1됨
• 그리고 바꿔주면 되는데 swap 함수에 넣어서 위치 바꿔주기. 2가 현재 index 2에 위치하고 있는데, swapIdx는 1이고 i는 2이기 때문에 둘의 위치를 변경해줌
• [4,8,2,1 ...] 에서 [4,2,8,1 ...]로 됨
• 계속해서 반복하여 [4,2,1,3...] 이렇게 위치하게 되고, 반복문 종료됨
• 그 다음 swap함수 한번더 동작하여서 arr의 start위치와 swapIdx 위치로 변경해줌
• 즉 4보다 작은 값이 3개 있기 때문에 swapIdx는 3이 되었고, start는 0이니 두개 위치를 바꾸면 [3,2,1,4...]로 변경
• 아래는 자세한 과정
• 요점은 마지막에 swapIdx를 반환하는 것임
• 실행하면 3을 반환함

  pivot([4,8,2,1,5,7,6,3])
  [4,8,2,1,5,7,6,3] // 4와 8
  [4,2,8,1,5,7,6,3] // 4와 2 , 2와 8 위치 변경(swapIdx=1, i=2)
  [4,2,1,8,5,7,6,3] // 4와 1 , 1과 8 위치 변경(swapIdx=2, i=3)
  [4,2,1,8,5,7,6,3] // 4와 5 , 변경 없음 (i=4)
  [4,2,1,8,5,7,6,3] // 4와 7 , 변경 없음 (i=5)
  [4,2,1,8,5,7,6,3] // 4와 6 , 변경 없음 (i=6)
  [4,2,1,3,5,7,6,8] // 4와 3 , 3과 8 위치 변경(swapIdx=3, i=7)
  [3,2,1,4,5,7,6,8] // swapIdx랑 start 변경, 3과 4 위치 변경(swapIdx=3, start=0)

 

🐣 퀵 정렬 구현

---

설명

• 앞에서 살펴 본 것처럼 처음 4라는 피벗을 찾아 인덱스를 옮기는 과정까지 하고 나면
• 다음에 할 것은 퀵 정렬을 호출 하는 것
• 예를들어 [4,6,9,1,2,5,3]일 경우
• [3,2,1,4,5,7,6,8]로 4가 이동하고 나면 [3,2,1] 즉 피벗인 4를 제외 한 앞에 것을 퀵 정렬
• 대략적인 로직은, 업데이트된 피벗 인덱스를 헬퍼가 반환하면 피벗 헬퍼를 재귀적으로 왼쪽과 오른쪽에 호출
• 중요한 것은 새로운 배열을 만들지 않고 제자리에서 발생(같은 배열에서 발생)
• 베이스 케이스는 단순히 배열의 아이템 길이나 배열에 하나의 항목이 있는지 확인하는 것이 아니라 하위배열에 항목 하나가 있도록 확인하는 것 [3,2,1], [2,1], [1]
• 이는 하위배열에 2개 미만의 요소가 있을 때 수행

 

구현

quicksort.js

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])

아래는 전체 코드

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;
}


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

• 피벗이 배열, 시작, 끝을 받지만 중요한 것은 가장 처음할 때 전체 배열을 호출한 다음, 재귀 함수가 하위 배열을 다시 시작하기 때문에, 이 하위 배열은 시작 포인트, 끝 포인트가 다름
• 배열의 끝에 도달할 때까지 기본값이 0인 것이 아님
• let pivotIndex = pivot(arr, left, right) 한다는 것은 arr배열 보내고 left에 0 즉 start값 0, end값 arr.lenght가 right값
• 처음에 피벗함수가 3을 반환함 let pivotIndex = pivot(arr, left, right) //3
• 그 다음 같은 작업을 왼쪽편에서 반복. 시작점에서 left에서 시작
• quickSort(arr, left, pivotIndex - 1); 할 경우 왼쪽
• 피벗 반환값 3보다 1작은 2를 right(=end)값으로 보냄. 피벗 인덱스 2 / [2,1] 일때는 피벗 인덱스 1
• 왼쪽 호출 2번 반복
• quickSort(arr, pivotIndex + 1, right); 오른쪽
• 피벗 값보다 1 큰 값을 left(=start) 값으로 보냄
• 처음 피벗 인덱스 4(=피벗값6) 6보다 작은거 앞으로
• 모든 부분 배열 정리되면 최종배열
• [1,2,3,4,5,6,9] 나옴

 

🐣 퀵 정렬 : 빅오 복잡도

---

퀵정렬 빅

 

[시간 복잡도]

• 64개 요소가 있다면 6번 분해 o(log n)
• 각 분해단계마다 피벗 정할 때 O(n)번 비교 수행 필요
• O(n log n)

 

퀵정렬 빅오 n log n 인 이유

 

[최악의 상황]

• O(n^2)
• 이미 정렬되어 있는 배열. 정렬되어 있는 줄 모름
• 분해할 때마다 1개 남음. 전체 하위 배열 남음
• 이미 정렬되어 있기 때문에 첫번째 항목만 남음
• 각 수행 되니 O(n) 분해
• 각 분해할 때마다 O(n) 비교 수행, 최악 케이스로 O(n^2) 시간 초래
• 기본적으로 피벗 고를 때 매번 가장 작은 요소만 선택하거나 항상 가장 큰 요소만 선택할 때 문제 발생
• 정렬되어 있는 예시의 경우 첫 번째 배열이 아닌 무작위로 피벗 고르면 됨
• 반복적으로 최솟값이나 최댓값을 피벗으로 정하면 제곱 시간 됨

퀵정렬 최악의 경우

---

퀵 정렬을 정리해보았꼬! 다음에는 기수 정렬에 대해서 정리해볼 것이당!

 

[알고리즘 JS] 합병 정렬 (merge sort) 나누고 정복해!