JavaScript로 퀵정렬(quick sort)알고리즘 구현하기

퀵정렬

pivot(중심축) 을 정하고, 중심축 보다 작은 값들은 왼쪽으로 큰 값들은 오른쪽으로 보내는 것이다.
이렇게 pivot을 정해서 왼쪽 오른쪽으로 나누고 다시금 왼쪽 오른쪽에 대해 재귀적으로 pivot을 정해서 왼쪽 오른쪽을 나누고,, 이 과정을 반복하면 결국 정렬이 완성 된다.

퀵정렬 알고리즘의 구체적인 개념

• 하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
• 퀵 정렬은 다음의 단계들로 이루어진다.

1. 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
2. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
4. 순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

수도코드

1. 먼저, 배열의 길이가 1과 같거나 작게 될 경우 배열을 바로 리턴한다.

2. 리스트 가운데 하나의 원소를 고르고 pivot 이라고 한다. : 첫번째 인덱스를 pivot으로 정했다.

3. 배열 안에서 pivot을 제외한 모든 요소를 탐색해서 pivot보다 작으면 left, 크면 right라는 배열에 넣는다.

        -> let left = []; let right = [];

        -> 이 과정은 인덱스가 arr.length만큼 반복한다

4. left와 right에 값이 모두 넣어졌으면 각각의 배열에 대해 quickSort를 재귀하도록 해서 다시 정렬한다.

5. left, pivot, right를 합쳐서 리턴한다.

코드로 나타내보면

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 lSorted = quickSort(left);
  const rSorted = quickSort(right);
  return [...lSorted, pivot, ...rSorted];
};

퀵정렬과 병합정렬

퀵 정렬에 대해서 구글링해보니 병합정렬(merge sort)와 많이 비교하는 것 같았다.
<퀵 정렬, 병합 정렬 공통점>

• Divide and Conquer(분할-정복) 알고리즘에 속한다.
• 둘 다 점점 탐색할 배열의 크기를 쪼개서 재귀함수에 넘겨준다.

<퀵 정렬, 병합 정렬 차이점>

• 병합정렬은 배열을 분할하는 방식이 반으로 쪼개는 것
• 퀵 정렬은 크게 두 가지 분할 방법이 있다.
• 퀵 정렬은 병합정렬과 달리 다른 메모리 공간을 사용하지 않는다. (오직 재귀 콜 스택을 위한 메모리만 사용됨, 그에 반면 병합정렬은 매 번 새로운 배열을 만들어 내므로 메모리 사용량이 더 큼)
• 드물지만, 파티션의 방법에 따라 최악의 경우에 O(n²) 까지 성능이 낮아질 수 있음.
• 병합정렬은 stable 하지만, 퀵 정렬은 unstable 하다. (원소들 중에 같은 값이 있는 경우에 정렬 이후 순서가 초기 순서와 달라 질 수 있기 때문에)