[알고리즘]퀵 정렬(Quick Sort)_JS

퀵 정렬

퀵 정렬은 분할정렬과 비슷하게 배열에서 임의의 값을 하나 정해서 그 값보다 작으면 왼쪽으로, 중간값보다 크면 오른쪽으로 보내는 과정을 통해 정렬을 진행한다.

분할정렬과 다른점이 있다면 분할정렬은 새로 배열을 만들어 메모리를 비교적 많이 차지한다는 점이고, 퀵 정렬은 재귀를 통해 정렬하는 과정이므로 비교적 메모리를 적게 소모한다는 점이다.

3

22

14

59

1

92

9

이런 배열이 있다고 가정해보자

배열의 중간 값과 나머지 배열과 비교해 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 정렬한다 ([3, 22, 14, 1, 9], 중간 값 59, [92])
재귀함수로 나누어진 왼쪽과 오른쪽 배열에도 똑같은 과정을 거친다. ([3, 1, 9], 중간 값 14, [22])
그렇게 모든 배열이 정렬될 때까지 과정을 반복하고 ([1], 중간 값 3, [9])
정렬이 완료되면 왼쪽 인덱스의 값 들, 중간 값, 오른쪽 인덱스의 값들을 합친다. ([1, 3, 9, 14, 22, 59, 92])

퀵 정렬로 구현해본 코드이다.

const quickSort = function (arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[0];
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] <= pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }

  const leftSorted = quickSort(left);
  const rightSorted = quickSort(right);
  return [...leftSorted, pivot, ...rightSorted];
};

처음에는 배열의 중간 값을 pivot의 초기값으로 두고 값을 비교하려고 했지만 Math.floor(arr.length/2)으로 계산을 한번 더 해주느니 배열의 0번째 인덱스와 나머지 값을 비교하는 방법도 결과는 동일하다는 것을 깨닫고 초기 값을 배열의 0번째로 설정했다.

console로 과정을 찍어봤다.

가장 앞의 인덱스 값과 나머지 값들을 비교 해 작은 값들은 왼쪽 배열에, 큰 값은 오른쪽 배열에 넣어두고 재귀를 통해 모든 값들을 정렬한다.