[알고리즘] Sort() 정확하게 쓰는 법

Sort 잘못 쓰면 님 코딩 인생 ㄹㅇ 망함

Sort는 배열을 정렬할 때 쓰인다. 숫자나 문자열을 정렬할 때 쓰이는데, 문제가 하나 있다. 일단 숫자 요소를 정렬할 때 숫자를 문자열로 변환해서 정렬 알고리즘을 돌린다. 근데 각 요소를 비교할 때 숫자를 문자열로 비교하다보니 두 자릿수 이상의 숫자를 비교하면 맨 앞 자릿수만 비교를 한다. 그래서 순서가 꼬여버리는 상황이 생긴다.

const array = [1, 2, 10];
console.log(array.sort());

// 1, 10, 2

문자열은 유니코드로 계산되고, 대문자가 작은 수로 계산이 되기 때문에, 대소문자 구분 없이 정렬할 때 난감한 상황이 생긴다.

const array = ["apple", "Orange", "orange"];
console.log(array.sort());

// "Orange", "apple" , "orange"

해결법: 고차함수 쓰셈

Sort의 문제점을 해결하려면 Sort에 고차함수를 넣어주면 된다. 이 고차함수는 두개의 배열 요소를 비교하여 정렬을 정확하게 해준다. 문자열과 숫자 타입 모두 대응하기 위해 아래와 같은 고차함수를 사용하면 편하다.

let ascending_order = function(x, y) {
	if (typeof x === "string") x = x.toUpperCase();
    if (typeof y === "string") y = y.toUpperCase();
    
    return x > y ? 1 : -1;
};

let descending_order = function(x, y) {
	if (typeof x === "string") x = x.toUpperCase();
    if (typeof y === "string") y = y.toUpperCase();
    
    return x < y ? 1 : -1;
};

const array1 = [1, 2, 10];
console.log(array.sort(ascending_order));
// 1, 2, 10

const array2 = [1, 2, 10];
console.log(array.sort(descending_order));
// 10, 2, 1

const array3 = ["apple", "Orange", "orange"];
console.log(array.sort(ascending_order));
// "apple", "Orange", "orange"

const array4 = ["apple", "Orange", "orange"];
console.log(array.sort(descending_order));
// "orange", "Orange", "apple"

정렬을 위해 x와 y를 비교할 때 결과 값이 +면 x가 y 뒤로 가고, -면 앞으로 온다. 순방향 정렬의 상황에서 2와 4를 비교하면, 2 - 4 = -2가 된다. 결과 값이 음수이기에, x인 2가 4 앞으로 온다.

응용 예시

list라는 배열 안엔 객체가 들어 있다. 만약 값이 같은데, 인덱스가 낮은 순으로 정렬하고, 그외엔 값이 높은 순서로 정렬하고 싶다면, sort를 이렇게 쓰면 된다.

list.sort((a, b) => {
			if (b.temp === a.temp) {
				return a.index - b.index;
			}
			return b.temp - a.temp;
		})