QuickSort

퀵 정렬 알고리즘

• 불안정 정렬으로, 다른 요소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
• 합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다.
• 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법

분할 정복(divide and conquer)
문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다.
문제를 분리하여 각각 해결한 후, 결과를 모아 본 문제를 해결하는 전략.

정렬 알고리즘 문제와 고속 푸리에 변환(FFT) 문제가 대표적이다.

보통 분할 정복 알고리즘은 재귀 함수로 구현하는데, 재귀 호출은 함수 호출 오버헤드 때문에 실행 속도가 늦어진다. 따라서 분할한 부문제를 푸는 알고리즘은 임의로 선택할 수 있다.

다시 말해, 빠른 실행이나 부문제 해결 순서 선택을 위해 스택, 큐(queue) 등의 자료구조를 이용하여 분할 정복법을 구현하는 것도 가능하다.

퀵 정렬 과정

리스트 안에 있는 한 요소를 선택해 정렬의 기준 피벗(pivot)으로 정한다.
피벗을 기준으로 큰 요소와 작은 요소를 담을 배열을 각각 생성한다.
순환하며 피벗을 기준으로 작은 요소들은 모두 피벗의 왼쪽 배열로,
큰 요소들은 모두 피벗의 오른쪽 배열에 추가한다.
(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)
피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
분할된 부분 리스트에 대하여 순환 호출을 이용하여 정렬을 반복한다.
부분 리스트에서도 다시 피벗을 정하고 2개의 부분 리스트로 나누는 과정을 반복한다.
부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
리스트의 크기가 0이나 1이 될 때까지 반복한다.

const quickSort = function (arr) {

  let pivot = arr[0]; // 정렬 기준을 첫 요소로
  let left = []; // 피봇 기준으로 작은 것들 담을 배열
  let right = []; // 피봇 기준 큰 것들 담을 배열

  if (arr.length <= 1) return arr; // base. 주어진 배열의 요소가 하나 이하면 그냥 리턴.

  for (let i = 1; i < arr.length; i++) { // 이제 피봇 제외 요소부터 순환하며 
    if (arr[i] <= pivot) left.push(arr[i]); // 피봇보다 작은 것은 왼쪽 배열에
    else right.push(arr[i]); // 큰 것은 오른쪽 배열에!
  }

  let allLeftsorted = quickSort(left); // 재귀로 왼쪽 배열 모두 정렬
  let allRightSorted = quickSort(right); // 재귀로 오른쪽 배열 모두 정렬
  return [...allLeftsorted, pivot, ...allRightSorted]; // 합치기
};

🔥 더 간결하고 명시적인 코드로 작성할 수 있다.

const quickSort = function (arr) {

  if (arr.length <= 1) return arr; 

  let pivot = arr[0]; 
  let list = arr.slice(1) // 피봇을 제외한 배열
  let left = list.filter(el => el <= pivot);
  let right = list.filter(el => el > pivot); 

  return [...quickSort(left), pivot, ...quickSort(right)]; 
};