[코딩테스트] 01. 배열 정렬하기 (feat. sort() 메서드와 comcompareFunction)

문제
정수 배열을 정렬해서 반환하는 solution() 함수를 완성하세요.

제약 조건
- 정수 배열의 길이는 2 이상 10^5 이하
- 정수 배열의 각 데이터 값은 -100,000 이상 100,000 이하

입출력의 예

입력	출력
[1, -5, 2, 4, 3]	[-5, 1, 2, 3, 4]

문제 분석하고 풀기
문제만 놓고 보면 간단해 보이지만 제약 조건의 데이터의 개수는 최대 10^5이기 때문에, 제한시간이 3초라면 O(N^2) 알고리즘은 사용할 수 없다.

 

해당 문제를 풀기 위해서는 sort() 메서드를 사용해야 하는데 해당 메서드의 개념부터 잡고가려고 한다!

sort() 메서드?

JavaScript의 Array.prototype.sort()는 기본적으로 배열 요소를 문자열로 변환해서 정렬한다.

[100, 3, 20].sort(); // => [100, 20, 3] → 틀린 결과

 

그래서, 이런 식으로 의도한 바와 다르게 정렬이 되곤 하는데!

이 때 compareFunction을 넣어줘야 정수 기준으로 정확한 정렬이 가능해 진다.

 

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

 

compareFn(a, b) 결과                                             정렬 방식 설명

음수 반환 (< 0)	a는 b보다 앞에 와야 함
양수 반환 (> 0)	a는 b보다 뒤에 와야 함
0 반환 (=== 0)	순서 그대로 유지

 

자바스크립트는 sort(compareFn)을 사용할 때, 내부적으로 정렬 알고리즘에 따라 두 요소를 비교하면서 정렬 순서를 결정한다.
우리가 넘겨준 compareFn 함수는 단순히 정렬 알고리즘에게 "누가 앞에 와야 할지"를 알려주는 역할을 한다.

즉, compareFn이 음수를 반환하면 자바스크립트는

"아, a가 더 작다는 뜻이구나. 그럼 a를 앞에 두자!"

 

이런 방식으로 우리가 숫자 비교를 직접 해주면, 문자열이 아닌 숫자 기준으로 정확하게 정렬할 수 있다.

 

정답 코드

function solution(arr) {
	arr.sort((a, b) => a - b);
    return arr;
}

 

O(N^2) 정렬 알고리즘으로 정렬하는 연산 - 비효율적인 코드

function bubbleSort(arr) {
	const n = arr.length;
    for (let i = 0; i < n; i++){
		for (let j = 0; j < n - i - 1; j++){
        	if (arr[j + 1] < arr[j]){
            const tmp = arr[j +1];
            arr[j + 1] = arr[j];
            arr[j] = tmp;
            }
        }
    }
	return arr;
}