[바미] Sorting algorithm - quickSort 알고리즘 구현하기

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

  let pivot = arr[arr.length - 1];
  let left = [];
  let right = [];

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

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

 

코드 설명

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

quickSort 함수는 재귀 호출을 사용해 구현하여 이 함수는 매개변수로 배열, 시작 인덱스, 끝 인덱스를 받습니다. 처음에는 호출이 되면서 매개변수로 전달된 배열 전체와 인덱스의 범위를 기준으로 정렬하려는 부분 배열을 지정합니다.

 

  let pivot = arr[arr.length - 1];
  let left = [];
  let right = [];

 

pivot을 구성하는 원소를 결정하기 위해 마지막 원소를 pivot으로 선택합니다.

 

if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }

pivot을 기준으로 큰 원소와 작은 원소를 구분하여 pivot의 위치를 정합니다. pivot 위치를 정하기 위해서는 pivot보다 작은 원소들을 pivot의 왼쪽으로 옮기고, pivot보다 큰 원소들을 pivot의 오른쪽으로 옮깁니다. pivot의 위치를 정하면, pivot의 왼쪽에는 pivot보다 작은 원소들, pivot의 오른쪽에는 pivot보다 큰 원소들이 나누어져 있게 됩니다.

 

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

pivot의 왼쪽과 오른쪽에 있는 부분 배열에 대해 동일한 절차를 반복하여 정렬합니다. 각 부분 배열은 pivot보다 작은 원소와 pivot보다 큰 원소로 구분되므로, 두 부분 배열을 각각 정렬할 수 있습니다. 이 과정을 재귀적으로 반복하고, 각 부분 배열의 크기가 0이 될 때까지 정렬하면 모든 원소들이 정렬되게 됩니다.

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

정렬이 끝난 후에는 pivot의 위치에 있는 원소를 기준으로 왼쪽 부분 배열과 오른쪽 부분 배열이 정렬된 상태이므로, 이 두 부분을 합쳐서 전체 배열이 정렬된 상태가 됩니다.

 

왜 quickSort 함수는 재귀 호출을 사용하였는가?

QuickSort는 분할 정복 알고리즘이기 때문에 재귀 함수를 사용하여 구현하는 것이 가장 적합합니다. QuickSort는 배열을 pivot을 기준으로 왼쪽 부분 배열과 오른쪽 부분 배열로 나눈 다음 각 부분 배열에 대해 재귀적으로 정렬을 수행하는데 이 과정은 재귀 호출을 사용하여 구현하기 쉽고, 코드도 깔끔하게 작성할 수 있어서 자주 사용되고 있습니다.