Udemy - 퀵 정렬

---

퀵 정렬이란?

병합 정렬과 비슷하게 분할과 재귀함수를 사용하여 정렬한다.
하지만 퀵 정렬에서의 분할(피버팅)은 병합에서의 분할과는 조금 다르다.

위에서 보이는 바와 같이 특정 피벗(pivot)숫자를 하나 고르고, 그 숫자를 기준으로 그 숫자보다 작은 수는 자신의 왼쪽으로 무작위로 보내고, 큰 수는 우측으로 무작위로 보낸다. 그리고 좌측 숫자들을 다시 포인터를 내려가며 순회 정렬하고 우측 또한 마찬가지로 정렬하면 된다. 쉽게 생각하면 피벗숫자를 기준으로 배열을 이등분 하고 각 배열들의 숫자들을 차례대로 정렬하는 것이다.

---

피벗 헬퍼 알고리즘 (step 1)

위에서 설명했듯이, 퀵정렬을 하기 위해선 피벗 헬퍼 함수를 활용해야 한다.
우선 특정 숫자 기준 작은 수들은 좌측으로, 큰 수들은 우측으로 옮겨준다.

기본 코드 예시

function pivot(arr, start = 0, end = arr.length - 1) {
  // 1. 첫 번째 숫자를 pivot 숫자로 삼는다 arr[start].
  let swapIdx = start;
  // 2. 해당 숫자를 기준으로 자신보다 작은 수를 우선 우측에 배치시킨다.
  for (let i = start + 1; i <= end; i++) {
    if (arr[start] > arr[i]) {
      swapIdx++;
      [arr[swapIdx], arr[i]] = [arr[i], arr[swapIdx]];
    }
  }
  // 3. 그리고 그 작은 숫자들의 가장 끝 인덱스와 자리를 바꾼다.
  [arr[swapIdx], arr[start]] = [arr[start], arr[swapIdx]];
  // 4. 그러면 이제 좌측에는 자신보다 작은 숫자들만 존재하고, 우측에는 자신보다 큰 숫자들만 존재하게 된다.
  console.log(arr);
  return swapIdx;
}

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

---

퀵 정렬 구현 (step 2)

이제 pivot helper 함수를 구현해 뒀으니, 퀵 정렬 알고리즘만 구현하면 된다.
상당히 재귀 과정이 복잡하고 어렵다…

// javascript에서는 함수 매개변수가 undefined(완전 처음 실행 시)일 경우에 default값을 아래와 같이 지정해줄 수 있다.
function quickSort(arr, left = 0, right = arr.length - 1) {
  // 재귀함수의 endpoint는 right가 left에 닿았을 때이다 (arr.length === 1이 될 때)
  if (left < right) {
    // 우선 초기 배열을 피버팅 해준다. => 그러면 첫 배열 pivot값이 정렬 됐을 때의 index값이 리턴된다.
    let pivotIdx = pivot(arr, left, right); //3
    //left
    // 여기부터 재귀함수가 실행된다. 배열 전체가 보내지지만 left ~ pivotIdx-1 까지만 피버팅이 다시 되도록 한다.
    // 먼저 pivotIdx를 기준으로 좌측 부분들이 모두 정렬될 때 까지 아래의 함수는 실행되지 않는다.
    quickSort(arr, left, pivotIdx - 1);
    //right
    // 좌측이 모두 정렬되면 이제 쌓여있던 콜스택이 비워지고 이 함수호출이 실행된다.
    // 계속 재귀함수를 실행하며 우측 또한 마찬가지로 정렬된다.
    quickSort(arr, pivotIdx + 1, right);
  }
  // 그러면 이제 최종적으로 정렬된 arr이 최하단 콜스택에 의해 반환된다.
  return arr;
}

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

---

퀵 정렬의 시간복잡도

1. 시간 복잡도 : O(nlogn)

   하지만, 퀵 정렬은 잘 정렬되어 있는 배열에 대해서는 비효율적일 수 있다

---