JS 정렬(sort) 만들기

Eamon·2021년 4월 12일

js 알고리즘

algorithm

목록 보기

3/7

`Sort` 의 `compareFunction`

sort 함수는 js 에서 정렬된 배열을 생성하는 함수입니다. sort는 정렬을 할때 compareFunction 를 이용하는데 아래의 규칙을 따릅니다.

compareFunction이 제공되면 배열 요소는 compare 함수의 반환 값에 따라 정렬됩니다. a와 b가 비교되는 두 요소라면,

compareFunction(a, b)이 0보다 작은 경우 a를 b보다 낮은 색인으로 정렬합니다. 즉, a가 먼저옵니다.
compareFunction(a, b)이 0을 반환하면 a와 b를 서로에 대해 변경하지 않고 모든 다른 요소에 대해 정렬합니다.
compareFunction(a, b)이 0보다 큰 경우, b를 a보다 낮은 인덱스로 소트합니다.
compareFunction(a, b)은 요소 a와 b의 특정 쌍이 두 개의 인수로 주어질 때 항상 동일한 값을 반환해야합니다. 일치하지 않는 결과가 반환되면 정렬 순서는 정의되지 않습니다.

1) bubbleSort

버블 정렬은 O(n^2)이기 때문에 성능이 좋지 않습니다. 거기에 성능이 안 좋은 정렬 중에서도 가장 안 좋은 편에 속하는 정렬입니다. 하지만 로직이 단순해서 sort를 이해하기엔 더할나위 없는 연습문제입니다.

버블 정렬은 두 개의 for 문으로 만듭니다.

function bubbleSort(arr, compare) {
  for (let i = 0; i < arr.length - 1; i++) { // 첫 번째 for 문 
    for (let j = 0; j < arr.length - 1 - i; j++) {// 두 번째 for 문
      if (compare(arr[j], arr[j + 1]) > 0) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

버블 정렬의 버블은 두 개의 array의 인자를 각각 비교하면서 두번째 for문을 돌아가는 것을 뜻합니다.

일반적인 sort 함수로 가정하기 위해 compare 함수는 (a,b) => b-a 로 가정합니다.

[ 3,4,5,2,7] 이라는 배열로 예시를 들어보면

첫번째 for 문의 i index 가 0 일때

[ (3,4),5,2,7] 3과 4를 비교하여 compare 함수에서 양수가 나오면 자리를 바꿔줍니다.

[ 4,(3,5),2,7] 3과 5를 비교하여 양수가 나오기 때문에 바꿔줍니다.

[ 4,5,(3,2),7] 3과 2를 비교하여 음수가 나오기 때문에 그대로 둡니다.

[ 4,5,3,(2,7)] 2과 7를 비교하여 양수가 나오기 때문에 바꿔줍니다.

[ 4,5,3,7,2] 가장 작은 2 가 가장 끝에 와있음을 알수 있습니다. (2의 sort는 끝남)

그렇기 때문에 i index 가 1일 때 부터는 j는 length - 1 - i 만큼만 비교해가면서 자리를 바꾸면 됩니다.

2) MergeSort

합병 정렬은 O(NlogN)이기 때문에 성능이 준수합니다. 다만 30개 이하의 숫자를 정렬할 때는 삽입 정렬과 별 차이도 없고, 정렬하는데 추가적인 메모리가 필요하다는 단점이 있습니다. 보통은 재귀 함수를 사용해서 만듭니다.

js sort 메소드가 이 MergeSort 알고리즘으로 구동되고 있습니다.

구현방법은 Divide and conquer 의 형식으로 앞에서 말했듯 재귀함수로 구현을 보통합니다.

정렬되지 않은 하나의 배열을 단일 요소를 가진 배열이 될 때 까지 나눈다. (Divide)
단일 요소를 가진 배열을 합친다. (conquer)

sort((a,b) => b-a)

b + a - (a + b)

이것도 역시 [ 3,4,5,2,7] 이라는 배열로 예시를 들어보면

[ 3,4,5 | 2,7] [(3),4,5] [ (2),7] 2하고 3을 비교해서 큰 것을 sort 에 넣는다.

[ 4,5 | 2,7] [(4),5] [ (2),7] [3] 4하고 2을 비교해서 큰 것을 sort 에 넣는다.

[5,2 | 7] [(5),2] [(7)] [3,4] 5하고 7을 비교해서 큰 것을 sort 에 넣는다.

흠.. 그런데 이런식으로 하다간 sort 가 되지 않는다. 왜냐하면 맨첫줄 [ 3,4,5 | 2,7] 여기서의 각각의 left right 배열들은 이미 sort 가 되어있어야 하기 때문이다. 그렇기 때문에 재귀가 필요하다.

우리는 분할을 다 해놓은 다음에 그 분할된 array들을 병합하면서 재귀로 백트래킹 해오면서 sortedArr 에 push 해 옵니다.

function merge(left, right, compare) {
  const sortedArr = [];
  while (left.length && right.length) {
    //left[0]이 더작을 경우 같을때는 누가 먼저 들어가도 상관X
    //left[0], right[0] 가 compare 함수에서 음수를 리턴하면 왼쪽에서 push 양수나 0 을 리턴하면 오른쪽에서 push 
    if (compare(left[0], right[0]) < 0) {
      sortedArr.push(left.shift());
    } else {
      sortedArr.push(right.shift());
    }
  }
  //left,right 둘 중 하나는 요소가 남아있기 때문에 sortedArr 뒤에 붙여서 출력
  //비어있으면 spread Syntax에도 아무것도 없기 때문에 그냥 다 붙여준다.
  return [...sortedArr, ...left, ...right];
}

function mergeSort(arr, compare) {
  if (arr.length === 1) return arr;
  const boundary = Math.ceil(arr.length / 2);
  //slice로 해주기 때문에 원본 arr은 손상 없다.
  const left = arr.slice(0, boundary);
  const right = arr.slice(boundary);
  //요소가 1개 일 때까지 재귀를 실행해 요소가 1개일 때 두 left,right부터
  //차근차근 merge(정렬해서 합치기)해주면 된다.
  return merge(mergeSort(left, compare), mergeSort(right, compare), compare);
}