[JavaScript] 배열을 정렬하는 방법(정수, 문자열)

배열을 정렬하는 방법 (문자열, 오름차순, 내림차순)

Array.prototype.sort()

JavaScript의 sort() 메서드는 기본적으로 문자열의 유니코드 코드 포인트를 따른다.

const months = ['March', 'Jan', 'Feb', 'Dec'];
months.sort();
console.log(months);
// Array ["Dec", "Feb", "Jan", "March"]

const array1 = [1, 30, 4, 21, 100000];
array1.sort();
console.log(array1);
// Array [1, 100000, 21, 30, 4]

 

위 예제에서 볼 수 있듯이 배열의 정수값을 오름차순 정렬하기 위해 array1.sort()를 실행한 결과 정렬이 제대로 되지 않는것을 확인할 수 있다.

sort() 메서드의 정렬 방식은 배열 안의 각 요소들을 숫자 대신에 문자열로 변환하여 비교하므로(유니코드 코드 포인트 순서) 정수 배열을 정렬하려고 했을 때 예상한 순서와 다르게 정렬되는 것이다.

 

---

Array.prototype.sort([compareFunction])

sort() 메서드에 비교함수를 매개변수로 주면 비교함수의 return 값에 따라 정렬 순서를 결정한다.

compareFunction(a,b)

- return 값이 0보다 작은 경우 (음수)
: 첫 번째 요소(a)가 배열의 앞쪽에 위치하게 된다. (오름차순 정렬)

- return 값이 0보다 큰 경우 (양수)
: 첫 번째 요소(a)가 배열의 뒤쪽에 위치하게 된다 (내림차순 정렬)

 

배열 오름차순 정렬

const array = [10, 5, 20, 3];
array.sort((a, b) => a - b); // 오름차순
console.log(array); // [3, 5, 10, 20]

compareFunction이 매개변수 a와 b를 받고

a - b의 값이 음수다? => a가 b보다 크다 => a는 b의 앞쪽에 위치한다.

a - b의 값이 양수다? => a가 b보다 작다 => a는 b의 뒤쪽에 위치한다.

따라서 sort의 compareFunction()으로 (a,b)=>a-b 를 전달하면 오름차순 정렬이 된다.

 

배열 내림차순 정렬

const array = [10, 5, 20, 3];
array.sort((a, b) => b - a); // 내림차순
console.log(array); // [20, 10, 5, 3]

반대로 compareFunction으로 (a,b)=>b-a를 전달하면 내림차순 정렬이 된다.

 

---

사용하는 알고리즘과 시간 복잡도

V8 엔진의 JavaScript sort() 메서드는 일반적으로  퀵소트(QuickSort) 알고리즘을 사용하여 배열을 정렬한다.

브라우저마다 JavaScript의 엔진이 다르고 엔진마다 내부적으로 정렬 알고리즘을 최적화하기 위해 다양한 전략을 채택할 수 있다.

 

퀵소트 알고리즘의 경우 일반적으로 평균적인 경우에 O(nlogn)의 시간 복잡도를 가지지만, 최악의 경우에는 O(n^2)의 시간 복잡도를 가진다. 최악의 경우는 이미 정렬이 됐거나 거의 정렬이 된 배열과 같이 피벗(pivot)을 선택하는 방식에 따라 발생한다.

 

JavaScript의 sort()메서드는 대부분의 경우에 효율적으로 동작하며, 대부분의 상황에서 O(nlogn)의 시간 복잡도를 보장한다.