숫자로 이루어진 배열을 인자로 받아 정렬된 결과를 반환하는 자바스크립트 함수를 작성한다고 가정해 봅시다. 보통은 Array.prototype.sort() 메서드를 사용하면 간단히 해결되지만, 이번 문제에서는 sort()를 사용하지 않고 반드시 Array.prototype.reduce() 메서드만으로 배열을 정렬해야 합니다.
접근 방식: 삽입 정렬 + reduce()
핵심 아이디어는 고전적인 삽입 정렬(Insertion Sort) 알고리즘입니다. reduce()로 빈 배열([])에서 시작하는 누적 배열(acc)을 만들고, 원본 배열의 각 요소(val)를 하나씩 순회하며 다음 과정을 반복합니다.
- 누적 배열을 왼쪽부터 훑으면서 현재 값보다 작거나 같은 요소를 만날 때까지 위치(ind)를 이동합니다.
- 찾은 위치에 splice()로 값을 삽입합니다.
- 모든 요소에 대해 이 과정이 끝나면 누적 배열은 자연스럽게 오름차순으로 정렬됩니다.
코드 예제
const arr = [4, 56, 5, 3, 34, 37, 89, 57, 98];
const sortWithReduce = arr => {
return arr.reduce((acc, val) => {
// 현재 값(val)이 들어갈 올바른 위치를 찾습니다
let ind = 0;
while (ind < acc.length && val > acc[ind]) {
ind++;
}
// 찾은 위치에 값을 삽입합니다
acc.splice(ind, 0, val);
return acc;
}, []);
};
console.log(sortWithReduce(arr));
출력 결과
콘솔에는 다음과 같이 오름차순으로 정렬된 배열이 출력됩니다.
[ 3, 4, 5, 34, 37, 56, 57, 89, 98 ]
동작 원리 살펴보기
예제 배열을 기준으로 누적 배열이 어떻게 변하는지 단계별로 확인해 보겠습니다.
- 4 처리 → 누적 배열: [4]
- 56 처리 → 4보다 크므로 맨 뒤에 삽입: [4, 56]
- 5 처리 → 4 다음, 56 앞에 삽입: [4, 5, 56]
- 3 처리 → 맨 앞에 삽입: [3, 4, 5, 56]
- 이후 34, 37, 89, 57, 98도 같은 방식으로 제자리를 찾아 삽입됩니다.
모든 요소의 순회가 끝나면 reduce()의 반환값인 누적 배열이 곧 정렬된 배열이 됩니다.
참고 사항
이 방식은 이중 반복 구조를 가지므로 시간 복잡도가 O(n²)입니다. 따라서 내부적으로 최적화된 정렬 알고리즘을 사용하는 sort()보다 성능이 떨어지며, 실무에서는 sort()를 사용하는 것이 좋습니다. 다만 reduce()의 동작 원리와 삽입 정렬 개념을 학습하기에는 매우 좋은 예제입니다. 또한 while 조건의 비교 연산자를 val < acc[ind]로 바꾸면 간단히 내림차순 정렬로 변경할 수 있습니다.