[알고리즘 | JS] sorting algorithm(정렬 알고리즘)5 - quick sort

Quick Sort (퀵 정렬)

: 퀵 정렬은 합병 정렬과 같은 가정으로 작동한다. 재귀를 통해 해결하기 가장 쉬운 방식 중 하나다.

합병 정렬처럼 0또는 1개의 정렬된 요소를 배열로 쪼갠다. 

피벗(pivot) 포인트라 부르는 단일 요소를 선택하여 수행한다. 예시로 첫번째에 위치하는 5를 피벗으로 골랐다면 5를 기준으로 왼쪽 오른쪽 섹션을 나누게 된다. 그리고 왼쪽 섹션에서 새로운 피벗을 고른다. 이 과정을 반복해준다. 

*피벗 포인트로 선택된 요소는 어찌됐든 정렬된 데이터가 된다.(e.g.)5를 선택했다면 5를 기준으로 작은 값 큰 값을 나누기 때문이다.) 

퀵 소트 피벗 동작 예시

1-1. Pivot Helper 

- 파티션 or 피봇이라 부른다. -> 같은 의미

- 배열이 주어지면 요소를 피벗 포인트로 지정하여 배열 속 요소를 재배치하는 함수

• 피봇보다 작은 값은 모두 왼쪽으로 이동하며 피벗보다 큰 값은 모두 오른쪽으로 이동한다. 양쪽의 순서는 중요하지 않다. 올바른 쪽에서 피봇(피봇이 된 요소, 기준되는 요소)보다 작거나 커야할 뿐이다. ( 왼쪽 오른쪽으로 피벗을 기준으로 하여 작은 값 큰 값으로 요소를 배치하지만 아직 각각의 포지션에서 정렬된 상태가 아니어도 된다는 소리)
• 헬퍼가 제자리에서 수행해야 한다. -> 새 배열을 만들면 안되고, 피봇 인덱스를 반환해야 한다. 

1) Picking a pivot (피봇 포인트 고르기)

• 퀵 정렬의 실행 시간은 피봇 선택 위치에 따라 달라질 수 있다. 
• 이상적으로는 데이터 집합의 중간값이 되도록 선택해야 한다. 
• 중간 값을 고를 수 없다면 대안적으로 첫 번째 요소, 마지막 요소, 중간, 무작위 요소(값이 아니라 위치적으로)를 선택한다. 
• 강의에서는 편의상 항상 첫 번째 요소를 피봇으로 선택하였지만 빅오에 안 좋은 영향을 미칩니다.

// TODO: 1) pivot helper 만들기 -> 배열을 재가공하지 않고 해당 배열에서 pivot위치(index)를 return하는 함수
// 1-1 pivot helper 는 인자로 3개를 받는다 배열, 첫번째 배열요소 index, 마지막 배열요소 index

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

    let pivot = arr[start];
    //swapIdx는 pivot 이 마지막에 어디로 스왑해야하는 지 알려주는 지표이다.
    let swapIdx = start;
    //for문에서 pivot으로 선택된 요소는 순회할 필요없기 때문에 start +1 을 초기값으로 설정

    for (let i = start + 1; i < arr.length; i++) {
      if (pivot > arr[i]) {
        swapIdx++;
        swap(arr, swapIdx, i);
        console.log(arr);
      }
    }
    swap(arr, start, swapIdx);
    console.log('the final form of array: ', arr);
    return swapIdx;
  }
  console.log(pivot([4, 6, 2, 7, 1, 3, 8, 9])); //pivot index: 3

• pivot helper에서 index를 반환하는 과정은 중요하다-> 퀵 정렬 함수에서 수행하려는 것은 전체 배열의 가장 앞에서 피봇 헬퍼 함수를 호출하는 것이기 때문이다.

1-2. 퀵 정렬 구현하기

• 대략적인 로직은, 업데이트된 피봇 인덱스를 헬퍼가 반환하면 피봇 헬퍼를 재귀적으로 왼쪽과 오른쪽에 호출한다.
• 새 배열을 만들지않고 모두 제자리에서 일어난다.
• 베이스 케이스(base case)는 하위 배열에 2개 미만의 요소가 있을 때 수행된다. (0, 1개의 요소만 존재할 때)

  function quickSort(arr, left = 0, right = arr.length - 1) {
    //if문에 베이스케이스를 잡아주지 않으면 스택오버플로우가 걸림
    // ? 베이스 케이스: 결국 하위 배열로 갈수록 l r의 거리가 가까워지는 것이므로 더이상 쪼개지지않는 경우라면 중단
    if (left < right) {
      let pivotIndex = pivot(arr, left, right);
      //left(pivotIndex 부분은 포함시키지 않아야 한다. )
      quickSort(arr, left, pivotIndex - 1);
      //right
      quickSort(arr, pivotIndex + 1, right);
    }
    // 배열을 꼭 리턴해야한다. 재귀적으로 돌아가고 있기 때문에 퀵 정렬 함수의 결과를 기다리고 있기 때문
    return arr;
  }
  console.log(quickSort([3, 5, 1, 8, 6, 9, 10, 44, 13]));
  /*
    [
    1,  3,  5,  6, 8,
    9, 10, 13, 44
    ]
   */

 

📌 quickSort함수가 재귀적으로 하위 배열을 다시 시작하기 때문에 하위 배열은 시작포인트, 엔드포인트가 다르다.  pivot함수의 인자값으로 left, right를 새롭게 지정하여 보내줘야 pivotIndex값을 제대로 받을 수 있다. 

2. 퀵 정렬의 시간복잡도(Big O)

최상, 평균: O(n log n)

최악의 경우: O(n^2) ,

• 이미 정렬된 배열에서 퀵 정렬을 하려고 할 때
• 최댓값이나 최솟값을 pivot으로 사용할 경우에 문제가 발생한다. (매번 첫 번째 요소를 선택하는 대신 무작위 수나 중간 값을 선택하는 이유) -> 이미 정렬된 배열이라면 매번 첫번째 요소나 마지막 요소를 pivot으로 선택했을 때 그 위치의 값이 최솟값 최댓값이기 때문임
• 피하는 방법: 랜덤값이나 중간값을 pivot으로 삼는다.

* 공간 복잡도: O(log n)