[알고리즘] 퀵정렬

1. 퀵정렬

데이터를 분할하여 배열에 0개 또는 1개의 항목이 남을때까지 분할하여 개별적으로 정렬되는 방식

피벗포인트라 부르는 단일 요소를 선택하여 수행한다.

그러니 어떤 배열에서 어떤 요소를 선택하든 사실상 문제가 되지 않는다.

 

2. 퀵정렬 순서

선택한 숫자보다 작은숫자를 왼쪽으로 옮긴다

선택한 숫자보다 큰숫자를 오른쪽으로 옮긴다.

이 때 선택한 숫자는 올바른 위치이다.

이 과정을 왼쪽과 오른쪽에 반복한다.

 

예시)

[5,2,1,8,4,7,6,3]
5선택
3,2,1,4 5 7,6,8
왼쪽 다루기
1,2,3,4 5 7,6,8
오른쪽 다루기
1,2,3,4,5,6,7,8

3. 구현

(1) pivot 함수

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

  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(arr, start, swapIdx);
  return swapIdx;
}

(2) 퀵정렬 전체

const quickSort = (arr, left = 0, right = arr.length - 1) => {
  if (left < right) {
    let pivotIdx = pivot(arr, left, right);
    quickSort(arr, left, pivotIdx - 1);
    quickSort(arr, pivotIdx + 1, right);
  }
  return arr;
};

4. 퀵정렬 빅O

시간복잡도(최고)	시간복잡도(평균)	시간복잡도(최악)	공간복잡도
O(nlogn)	O(nlogn)	O(n^2)	O(logn)