Toy 문제 16

문제

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

 

주의사항

• 퀵 정렬을 구현해야 합니다.
• arr.sort 사용은 금지됩니다.
  (갑자기 든 생각이지만 왜 있는 함수를 쓰지 말라는건 왜 일까요.? 난이도를 조금만 올릴려고 그러는걸까요?)
• 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.

Advanced

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

입출력 예시

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

 

수도코드(해석)

퀵정렬에 대해서

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

분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.

정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.

결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

 

출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

퀵정렬에 대해서 설명을 자세하게 써놔서 처음에는 어떤 것이구나 라고 이해하기에는 좋지만 참 어렵게 설명이 된것 같다고 생각이 듭니다.

 

쉽게 풀어서 이야기 하면

1. 숫자를 아무거나 고른다.

2. 그 숫자보다 작으면 선언한 왼쪽 배열에, 그 숫자보다 크면 선언한 오른쪽 배열에 푸쉬 하여 넣는다.

3. 그러면 각 두개의 배열이 생길 텐데. 그것을 각각 2번 방식으로 실행한다. 이 때 반복하는 일이 있기에 재귀를 사용한다.

4. 재귀 탈출 조건은 나눠진 배열이 1개만 출력 되었을때 그 자체를 리턴하는 것으로 한다.

5. 마지막 결과 리턴 값을 [... 왼쪽배열, 기준, ... 오른쪽배열] 로 리턴 한다.

 

결국 하나 기준 정해서 좌우 나누고 나눈 2개를 각각 또 좌우 나눠주는 것을 반복하는 방식을 사용합니다. 내림차순이면 반대로

그리고 어드벤스는 왜 넣었을까 하는 의문점이 들정도로 좀 불필요한 존재처럼 느껴서 크게 신경 안써도 될것 같습니다.

 

 

코드

function quickSort(arr, transform = (item) => item) {
  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]; // 결과 값 리턴
}