[자료구조/알고리즘] 211028 퀵정렬 구현하기 #기준점 #while문 #pivot정하기 #콜백함수

📌 퀵 정렬 구현

sort메서드는 금지되어 있다는 전제하에, 배열을 오름차순으로 정렬해야 한다.

입력

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

출력

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

advaced 문제로는 콜백함수를 이용하라고 하였다. 콜백함수를 이용하는건 시간복잡도의 개선을 위함인듯 하다.
퀵 정렬로 구현하라는데 도대체 퀵 정렬이 뭔지를 몰라서 검색해서 좀 찾아 보았다.

☑ 처음 접근방법

arr의 길이는 0개에서 100,000개가 될 수 있으므로 길이가 0 그리고 1일 때는 배열 자체를 리턴할 수 있게 한다. 그리고 앞서 진행했던 문제들과 비슷하게 기준점을 잡는다. 기준점 pivot 은 배열의 0번째 인덱스, 그리고 맨 왼쪽은 1(0번째는 이미 pivot이니까) , 인덱스의 마지막은 arr.length-1 로 잡는다. 이후 대략적인 수도코드는 아래와 같다.

• while문(마지막인덱스가 가장 0번째 인덱스보다 클때)으로 배열을 계속 조회한다.
• while문 내에서 왼쪽 인덱스의 값이 pivot보다 크고 오른쪽 수가 pivot보다 작으면 위치를 바꾼다
• 왼쪽 인덱스의 값는 pivot보다 작으면 다음으로 넘어가고, 크면 가만히 있는다.
• 오른쪽 인덱스의 값이 pivot보다 크면 다음으로 넘어가고, 작으면 가만히 있는다.
• while문에 속하지 않을 때의 경우도 고려한다.

if (arr.length < 2) return arr;
  const pivot = arr[0];
  let leftCursor = 1;
  let rightCursor = arr.length - 1;
  while(leftCursor <= rightCursor) {
    // 왼쪽수가 기준보다 크고 오른쪽 수가 기준보다 작으면 위치를 바꿈 (swap)
    if (arr[leftCursor] > pivot && arr[rightCursor] < pivot) {
      [arr[leftCursor], arr[rightCursor]] = [arr[rightCursor], arr[leftCursor]];
      leftCursor++;
      rightCursor--;
    }
    // 왼쪽 수는 기준보다 작으면 다음으로 넘어가고, 크면 가만히 있기
    if (arr[leftCursor] <= pivot) {
      leftCursor++;
    }
    // 오른쪽 수는 기준보다 크면 다음으로 넘어가고, 작으면 가만히 있기
    if (arr[rightCursor] >= pivot) {
      rightCursor--;
    }
  }
  [arr[0], arr[leftCursor-1]] = [arr[leftCursor-1], arr[0]];
  const left = arr.splice(0, leftCursor-1);
  const mid = arr.splice(0, 1);
  const right = arr;
  return [
    ...quickSort(left),
    ...mid,
    ...quickSort(right)
  ];
}

☑ 다른 접근방법

이 접근방법은 콜백함수를 사용하지 않았는데, naive solution이라고 명시되어있던 코드였다. (naive solution이란 요령없이 단순하게 해결하는 솔루션인 거 같다. 내가 보통 접근할 땐 이런 식이 나오곤한다ㅠ)

이것도 3개의 변수를 할당한다. pivot은 arr[0], left라는 빈 배열(왼쪽 뭉텅이), right 라는 빈 배열(오른쪽 뭉텅이). 배열의 길이가 2보다 작을 때는 배열 그대로 리턴.

• for문으로 배열을 차례대로 조회하되, 만약 pivot보다 작을땐 왼쪽배열에 push한다. 그렇지 않은경우(pivot보다 큰 경우엔) 오른쪽 배열에 push한다.
• 또 다른 두개의 변수를 설정한다. 왼쪽 뭉텅이엔 재귀를 이용해서 정렬하는 lSorted와 오른쪽 뭉텅이엔 재귀를 이용해서 정렬하는 rSorted.
• lSorted, pivot, rSorted 전개구문 리턴

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];
 };

역시 난 이게 훨씬 더 이해하기 편하다..ㅠ

☑ best practice

이건 레퍼코드다. 문제에서 원하는 방향은 바로 콜백함수를 사용하라는 것이었다. 비교가 진행될 때마다 콜백함수의 호출이 이뤄져야 한다. Naive solution에서 살짝 변경이 있다.

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];
}

디버거를 찍어보니 transform이 호출될때마다 콜백함수가 실행. 첫번째 라인으로 다시 돌아간다.