퀵 정렬

개인적으로 모든 알고리즘 중에 가장 골아프게 하는 알고리즘.. 진짜 이거 만든 사람은 무슨 생각하다가 만든걸까?

퀵 정렬이란?

합병정렬과 같은 가정으로 작동하는 정렬 알고리즘 재귀를 통해 해결하기 쉬운(?) 방식 중 하나이다.

배열에 0개 or 1개의 항목이 남을 때까지 분할한 뒤에 개별적으로 정렬하는 방식이다 정렬하는 과정에서 피벗 포인트라고 부르는 단일 요소를 선택하여 수행하는데, 한 요소를 선택하면 해당 값보다 작은 숫자를 모두 왼쪽으로 옮기고, 큰 값은 오른쪽으로 옮긴다.

[5, 2, 1, 8, 4, 7, 6, 3]의 숫자가 있다고 생각해보자

처음에 5를 피벗이라고 생각하면 5보다 작은 숫자는 1,2,3,4 4개가 있다.
그렇다면 1.2,3,4를 왼쪽으로 옮기고 5의 인덱스를 피벗보다 작은 수의 끝 바로 오른쪽으로 옮긴다. 이 과정에서 옮기는 과정은 자기보다 작은 수들을 일단 바로 오른쪽으로 옮기면서 자기보다 큰 수는 좀 떨어져 있게 하고 옆으로 한칸씩 밀어서 옮긴다. 다 옮긴 후에는 자신보다 더 작은 수의 끝 인덱스와 자신을 옮기면서 마무리된다
그렇게 되면 [3, 2, 1, 4, 5, 7, 6, 8]의 순서대로 값들이 옮겨간다.
이 과정이 끝났으면 이러한 과정을 5을 중심으로 왼쪽과 오른쪽에서 재귀적으로 반복한다. 왼쪽과 오른쪽에서 어떤 요소를 사용하든 상관은 없다.
왼쪽부터 가장 첫 요소 3을 피벗으로 사용한다고 하면 위와 같은 과정을 반복했을 때 나오는 결과는 [1, 2, 3, 4, 5, 7, 6, 8]이다.
다시 3을 기준으로 했으니 왼쪽의 1을 피벗으로 잡고 돌리면 따로 변환 없이 그대로 나오게 되고, 이는 곧 왼쪽이 모두 분할되어 1개 이하의 요소들로만 남게 되었으므로 정렬이 완성되었음을 의미한다
오른쪽 또한 정렬이 필요하기 때문에 여기도 첫번째 요소 7을 피벗으로 잡고 이동시킨다.
7을 피벗으로 값들을 이동시키면[1, 2, 3, 4, 5, 6, 7, 8]이 되고, 나머지 요소들이 단일 요소가 되었으므로 정렬이 끝난다.

피벗 선택하기

퀵정렬의 시간은 어떤 피벗을 선택하느냐에 따라 속도가 달라질 수 있다.

데이터 집합의 중간값이 되도록 선택하는 것이 이상적이다. 하지만 데이터가 무엇인지, 순서가 어떻게 되어 있는지 알지 못한다면 이를 고려하여 피벗 또한 선택하는 것이 쉽지 않다.

그래서 다른 전략으로 첫번째, 마지막, 중간, 랜덤한 요소 등을 선택하는데, 여기서는 첫 번째 요소를 피벗으로 선택하려 한다.

구현

피벗 교환 알고리즘

//배열이 주어지면 요소를 피벗 포인트로 지정하여 배열 속 요소를 재배치하는 함수
function pivot(arr, sidx = 0, eidx = arr.length + 1) {
  // 배열의 두 위치를 바꾸기 위한 함수
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };
  let pivot = arr[sidx];
  let swapIdx = sidx;
  for (let i = sidx + 1; i < arr.length; i++) {
    if (pivot > arr[i]) {
      // 스왑할 공간을 만들어주기 위해 옆으로 밀기
      swapIdx++;
      // 만든 공간에 있는 값과 i에 있는 값을 교환
      swap(arr, swapIdx, i);
    }
  }
  //스왑 인덱스와 피벗의 위치를 교환하여 피벗의 왼쪽에 작은수, 오른쪽에 큰 수만 오도록 만듦
  swap(arr, sidx, swapIdx);
  //스왑 인덱스를 리턴하여 나중에 왼쪽과 오른쪽을 어떤 인덱스 기준으로 구분할 지 알 수 있음
  return swapIdx;
}

퀵 정렬(전체)

//배열이 주어지면 요소를 피벗 포인트로 지정하여 배열 속 요소를 재배치하는 함수
function pivot(arr, sidx = 0, eidx = arr.length + 1) {
  // 배열의 두 위치를 바꾸기 위한 함수
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };
  let pivot = arr[sidx];
  let swapIdx = sidx;
  for (let i = sidx + 1; i < arr.length; i++) {
    if (pivot > arr[i]) {
      // 스왑할 공간을 만들어주기 위해 옆으로 밀기
      swapIdx++;
      // 만든 공간에 있는 값과 i에 있는 값을 교환
      swap(arr, swapIdx, i);
    }
  }
  //스왑 인덱스와 피벗의 위치를 교환하여 피벗의 왼쪽에 작은수, 오른쪽에 큰 수만 오도록 만듦
  swap(arr, sidx, swapIdx);
  //스왑 인덱스를 리턴하여 나중에 왼쪽과 오른쪽을 어떤 인덱스 기준으로 구분할 지 알 수 있음
  return swapIdx;
}
 
function quickSort(arr, left = 0, right = arr.length - 1) {
  //하위배열이 작아질수록 왼쪽과 오른쪽은 가까워지고 하나의 요소만 남으면 왼쪽과 오른쪽이 같아지는 원리는 이용하여 바닥조건 설정
  if (left < right) {
    let pivotIndex = pivot(arr, left, right);
    //왼쪽
    quickSort(arr, left, pivotIndex - 1);
    //오른쪽
    quickSort(arr, pivotIndex + 1, right);
  }
  console.log(arr);
  return arr;
}
 
// [1, 2, 3, 4, 5, 6, 7, 8];
quickSort([4, 8, 2, 1, 5, 7, 6, 3]);

시간복잡도

베스트 케이스와 평균이 모두 합병 정렬과 같지만 워스트 케이스의 경우는 $O (n^{2})$ 이 걸리니 조심하자!

구분	시간복잡도
Average	트리 형태로 두개로 분할되어 계속 정렬을 실행하는데 걸리는 시간 $l o g (n)$ * 분해하는 단계마다 비교에 걸리는 시간 $O (n)$ = $O (n l o g n)$
Best Case	$O (n l o g n)$
Worst Case	$O (n^{2})$ 거의 정렬되어 있을 경우 피벗이 원래 위치에서 움직이지 않고 계속 옆으로만 옮겨가면서 비교를 최대한으로 하기 때문에 $O (n)$ 의 분해가 수행되기 때문에 비교까지 곱하면 $O (n^{2})$ 이 걸린다

여기서 워스트 케이스를 개선하는 방법은 무조건 첫 번째 요소를 피벗으로 정하는 것이 아닌 무작위로 하나의 요소를 골라 피벗으로 정하여 분해하면 시간이 개선될 수 있다.

🐢꾸준함의 미학

탐색기

정렬 - 퀵정렬(Quick Sort)