[알고리즘 문제 풀이] 퀵 정렬, 정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.

 

💡 퀵 정렬 (Quick Sort)

 

- '찰스 앤터니 리처드 호어' 가 개발한 알고리즘.

- 퀵 정렬은 불안정 저렬에 속하며, 다른 원소와 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

- 분할 정보 알고리즘의 하나로, 평균적으로 매우 빠른 속도를 자랑함.

 

방법

1) 리스트 안에 있는 한 요소를 서택한다. 이렇게 고른 원소의 크기를 피벗이라고 한다.

2) 피벗을 기준으로 피벗보다 작은 요소들은 왼쪽, 큰 요소들은 오른쪽에 옮긴다.

3) 부분 리스트들이 더이상 불가능할 때까지 반복한다.

 

quickSort

문제

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.

입력

인자 1 : arr

• number 타입을 요소로 갖는 배열
• arr[i]는 정수
• arr.length는 100,000 이하

출력

• number 타입을 요소로 갖는 배열을 리턴해야 합니다.
• 배열의 요소는 오름차순으로 정렬되어야 합니다.
• arr[i] <= arr[j] (i < j)

주의사항

• 퀵 정렬을 구현해야 합니다.
• arr.sort 사용은 금지됩니다.
• 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.

입출력 예시

let output = quickSort([3, 1, 21]);
console.log(output); // --> [1, 3, 21]

Advanced

• quickSort 함수의 두 번째 인자로 callback 함수를 받아서, 그 함수의 리턴값을 기준으로 요소들을 정렬해 보세요.

 

💡두 번째 인자 callback 함수 안 쓰고 구현

const quickSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
   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];
};

 

💡두 번째 인자 callback 함수 쓰고 구현

const quickSort = function (arr, transform=(item) => item) {
  // TODO: 여기에 코드를 작성합니다.
  if (arr.length <= 1) return arr;

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

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

    const lSorted = quickSort(left, transform);
    const rSorted = quickSort(right, transform);
    return [...lSorted, pivot, ...rSorted];
};

 

사실 이 두개의 큰 차이를 아직은 모르겠다. 더 공부해봐야지!