[JavaScript] sort() 원리 알아보고 이해하기

코딩테스트 알고리즘 문제를 풀다보면, array.sort() 함수를 자주 사용하게 되는데, 쓰다보면 매우 유용하고 다양하게 응용 가능한 걸 느낄 수 있다.
 
문득 제대로 알고 쓰기보단 "이러면 오름차순, 이러면 내림차순" 이렇게 암기식으로 사용하고 있다는 걸 느꼈다.
 
따라서 자바스크립트의 sort를 정리하는 글을 쓰려고 한다. 잘 정리 했으니 읽어보고 도움이 됐으면 좋겠는 바람이다!

---

구문부터 보자

compareFunction은 생략이 가능하며, 생략할 시에는 배열 각 요소를 string으로 처리하고,  각 문자의 유니코드 값에 따라 정렬된다.
 
다음 예시를 보면 바로 이해가 될 것이다.
 

 
만약, compareFunction을 넣어주면, 이 함수의 반환값에 따라 정렬된다.
 

 
분명 둘다 오름차순 정렬을 했는데 compareFunction의 존재 유무에 따라 다른 결과가 나왔음을 알 수있다.

---

그러면  compareFunction 넌 뭔대?

mdn 공식 사이트와 여러 자료를 정리하면 다음과 같다.
 
compareFunction이 제공이 되면, compareFunction의 반환값을 이용하기 시작한다.
 
배열의 요소 2개를 전달 받고, compareFunction이 반환하는 값을 기준으로 정렬한다.
 
그리고 반환값은, 양수, 음수, 0 딱 3가지로 구분한다.
 
양수일 때 : b가 a보다 앞에 있어야한다.
음수일 때 : a가 b보다 앞에 있어야한다.
0일 때: a와 b의 순서를 바꾸지 않는다.
 
이제 mdn에 나와있는 오름차순 정렬 기본형식이 이해가 될 것이다.
양수, 음수, 0 에 따라 반환값을 고정해 놨을 뿐이다.

function compare(a, b) {
  if (a < b, 즉 a - b가 음수일 때) {
    return -1;
  }
  if (a > b, 즉 a - b가 양수일 때) {
    return 1;
  }
  //a = b, 즉 a와 b가 같을 때
  return 0;
}

array.sort(compare);

 
예)
[5,2,3] 배열이 주어 졌다고 해보자 
 
현재 배열: [5, 2, 3]
5와 2를 비교 -> 5 - 2 = 양수 -> 1반환 -> b가 a보다 앞에 있어야한다. -> 5, 2 자리 바꾸기
현재 배열: [2, 5, 3]
2와 3을 비교 -> 2 - 3 = 음수 -> -1반환 -> a가 b보다 앞에 있어야한다. -> 자리 그대로
현재 배열: [2, 5, 3]
5와 3을 비교 -> 5 - 3 = 양수 -> 1반환 -> b가 a보다 앞에 있어야한다. -> 5, 3 자리 바꾸기
현재 배열: [2, 3, 5]
 
이런 식으로 정렬이 완료된다.
 
물론 a와 b를 비교하는 순서는 실제 js동작과 다를 수 있지만, 이해하기 쉬운 예시를 들어 보았다.
 
이런 토대를 기반으로 해서 탄생된게 바로 우리가 숫자를 정렬 할 때 사용하는 형식이다.

array.sort((a, b) => a - b);

내림차순 정렬을 하고 싶다면 a - b를 b - a로 바꾸어 실행하면 된다.
 
*이러면 양수와 음수의 조건이 반전 되기 때문에 내림차순 정렬이 된다.

array.sort((a, b) => b - a);

---

결론

핵심은, 세 가지 종류에 반환값에 따라 자리를 바꿀지 말지 결정을 하는 것이였다.
sort()함수의 시간복잡도는 O(nlogn)으로 병합정렬과 유사하다하는데, 비교하는 과정에 있어서 엄청난 알고리즘을 사용하지 않았을까 라는 개인적인 추측을해본다.
 
다음 글에서는 sort()정렬을 응용하는 방법을 알아보자!