정렬 비교 함수 (compare)

정렬 비교 함수는 어렵지 않지만, 특별한 원리가 보이진 않습니다. "그냥 그렇게 설계됐다 - 라고 받아들여져서요"

이해의 필요성이 떨어지니, 조금만 사용하지 않더라도 이내 헷갈리고 빠르게 디버깅하며 코드를 작성하게 되더라고요.

그래서 관계성에 더 집중해서 기억해보고자 합니다.

 

물론 더 정확히 판단하려면, C++, JS의 sort 함수에서 사용하고 있는 정렬 알고리즘을 면밀히 파악해야합니다.

C++ : IntroSort (불안정 정렬, QuickSort+HeapSort+Insertion Sort)
JS: TimSort (안정 정렬), 작은 배열에는 Insertion Sort

불안정 정렬은, 중복된 값이 있을 때 입력된 순서가 유지되지 않을 수도 있는 정렬을 의미합니다.

를 사용하는데, 이 알고리즘 파악이 해당 아티클의 목적은 아닙니다.

 

해당 아티클의 목적은

"오름차순, 내림차순으로 정렬할 때 알면 도움되는 compare 의 개념을 정립" 해보고자 합니다.

 

앞으로  이 비교 함수를 compare(a, b) 함수로 명명하겠습니다.
또한 초기 배열에서 a는 앞에 있는 요소, b는 뒤에 있는 요소를 의미합니다.

참고로, compare 함수를 제공하지 않으면 C++이나 JS에서는 오름차순으로 정렬합니다.

 

C++ 에서의 비교 함수

c++은 명확하게 타입을 지정해주어야하는 강타입 언어입니다.

따라서, sort 함수에 사용되는 비교함수가 return 하는 값은 bool 이어야만 합니다. 

즉, true - false만 사용합니다. (그리고 true: 0이 아닌 값, false: 0 입니다.)

compare(a,b) 의 의미 : a를 b 앞에 냅둘거야? (true면 그대로 냅둠, false면 바꿈)

 

sort 함수는 compare 함수를 실행한 결과,

만약 true를 반환한다면 그대로 냅두고, false를 반환한다면 자리를 바꿉니다. 

 

그럼 아래의 함수는 어떻게 값을 정렬하고자 하는 것일까요?

bool compare(int a, int b) {
	return a > b; 
}

이 함수는 a > b 여야만 true가 됩니다.

즉, 만약 a가 값이 더 작거나 같으면 false를 반환하게 됩니다. 

false를 반환하면 자리를 바꿉니다. 

 

따라서 해당 함수는 "내림차순" 으로 정렬하는데 쓰이는 비교함수입니다.

 

cf) 참고로 priority_queue에서는 compare 함수를 다르게 사용합니다.

less<int>가 a < b를 의미하고, greater<int>가 a > b를 의미한다고 해봅시다.

//만약 pair를 담는다면 사전순으로 정렬 (따라서 first를 먼저 봄)
std::priority_queue<int> pq; //기본, max-heap을 의미
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;

greater는 a > b 를 의미하니까, 내림차순으로 정렬되어야할 것 같은데 사실상 min-heap을 정의하게 되며 오름차순으로 정렬됩니다.

그 이유는 priority queue에서는 비교 함수에서 반환하는 true를 a를 b보다 낮은 우선 순위로 둘 것이냐?(a가 b보다 뒤에 둘 것이냐)
를 의미하기 때문입니다.

따라서 a > b 일때는 a가 b보다 클 때 우선 순위가 낮아지므로, a가 b보다 뒤에 있어야하고, 결국 a가 작을 때 앞에 오게 됩니다.

따라서 큰 값이 앞에 오게 됩니다. sort에서 사용하는 compare와 완전히 반대죠?

 

이 사실을 통해 compare는 사실 절대적이지 않다라는 점만 알고, 사용 방식만 숙지하면 됩니다.

아니면 헷갈린다면 빠르게 테스트해보면서 코딩하는 것도 방법입니다.

 

 

Javascript 에서의 비교 함수

자바스크립트는 타입을 지정할 필요 없는 동적인 언어입니다. 

여튼 타입 지정 여부가 중요한 건 아니고, 자바스크립트에서는 compare 함수가 number를 반환하기를 원합니다.

즉 sort 함수에 사용되는 비교함수는 음수, 0, 양수 를 반환해야만 합니다.

compare(a,b) 의 의미 : 음수가 되도록 하는 로직에 맞춰 정렬할거야 ~

 

친절하게 타입스크립트에서는 아래와 같이 설명해주고 있네요. 

 

그런데 저는 이 설명이 오히려 헷갈리더라고요.

음수면 a를 작다고 여긴다는 건데, 그럼 (a,b) => b-a 로 하면 a가 더 클 때 음수가 되잖아요..

 

그렇다고 음수면 '제자리에 냅둔다' 라고 판단할 근거를 찾아보려 테스트해보니,

[1,2,3].sort((a,b)=>-1)의 결과는 왜 [3,2,1]이 되더라고요. 양수,음수, 0 이라는 값이 중요해보이지 않았어요.

결국 인자와의 관계를 sort에서 자체적으로 판단한다는거겠죠?

 

cf) 사실 완전히 이해하려면 sort가 어떤 알고리즘을 사용하고 있는지 면밀히 알아야하는데, 해당 아티클에서는 그게 목적이 아니라고 했습니다. 따라서 compare에 대한 의미를 음수가 되도록 하는 로직에 맞춰 정렬할거야 ~ 정도로만 이해하도록 합시다.

 

그럼 동일하게, 내림차순으로 정렬하는 compare 함수를 만들고 싶다면?

function compare(a, b) {
	return b - a; 
}


//사용 시
const arr = [1,2,3,4];

arr.sort(compare);
//혹은
arr.sort((a,b) => b - a);

 

이 됩니다.

이유는 음수가 되도록 하는 로직으로 정렬해준다고 했으니까, 해당 값이 음수가 되려면 b의 값이 더 작아야겠죠?

b는 뒤에 있는 값을 의미한다고 초반에 언급해뒀기 때문에, 뒤에 있는 값이 작다 === 내림차순 이라는 의미가 됩니다.

 

Javascript 에서의 비교 함수 작성 시 주의 사항

만약 JS에서 number가 아닌 boolean 값을 반환하는 함수를 작성했다면, 아예 동작하지 않습니다. 

JS에서는 절대 아래와 같은 compare 함수를 작성하지 마세요.

function compare(a,b) = {
	return b < a;
}

 

동작하지 않는 이유는, sort의 내부 구현의 차이 때문입니다.

C++ 에서는 어차피 true/false 값을 직접적으로 반환하지 않더라도, 형변환이 일어나서 결국 bool 값이 됩니다.

 

하지만 자바스크립트에서는 true == 1, false == 0으로 변환되기는 하는데, 그럼 음수를 표현하지 못합니다.

따라서 정렬이 전혀 안됩니다. 혹은 이상하게 되어버립니다. 

 

마찬가지로 , 상수를 반환하는 함수도 작성하지 마세요.

//절대 작성하지 말것. timesort를 사용하는데, 내부적으로 혼선이 옴
function compare(a,b) = {
	return 1;
}

function compare(a,b) = {
	return 0;
}

function compare(a,b) = {
	return -1;
}

 

결국 compare 함수는 sort 함수가 어떤 의사결정을 하는데 사용하는 함수인데, 저렇게 항상 상수값을 반환하면 내부적인 혼선을 빚게 되고, 이상하게 정렬이 됩니다.