이번 글에서는 숫자 배열을 인자로 받아 요소들을 교차(번갈아) 방식으로 재배열하는 JavaScript 함수를 작성해 보겠습니다.
교차 정렬이란?
여기서 말하는 '교차 정렬'은 배열의 요소들이 다음과 같은 패턴을 따르도록 배치하는 것을 의미합니다.
arr[0] < arr[1] > arr[2] < arr[3]
즉, 첫 번째 요소보다 두 번째 요소가 크고, 두 번째 요소보다 세 번째 요소가 작으며, 이런 식으로 크기가 번갈아 나타나는 형태입니다. 하나의 배열에 대해 가능한 결과는 여러 가지일 수 있으며, 우리는 그중 아무거나 하나만 반환하면 됩니다.
예시
입력 배열이 다음과 같다면,
const arr = [1, 2, 3, 4, 5, 6];
가능한 출력 중 하나는 다음과 같습니다.
const output = [ 3, 6, 2, 5, 1, 4 ];
결과를 확인해 보면 3 < 6 > 2 < 5 > 1 < 4 로 교차 패턴이 성립하는 것을 알 수 있습니다.
구현 방법
핵심 아이디어는 간단합니다.
- 먼저 배열을 오름차순으로 정렬합니다.
- 배열을 절반으로 나누어 작은 값 그룹(small)과 큰 값 그룹(big)으로 분리합니다.
- 짝수 인덱스에는 작은 그룹에서 큰 값부터 꺼내 채우고, 홀수 인덱스에는 큰 그룹에서 큰 값부터 꺼내 채웁니다.
정렬된 상태에서 각 그룹의 뒤쪽(큰 값)부터 꺼내면 자연스럽게 교차 패턴이 만들어집니다. 전체 코드는 다음과 같습니다.
const arr = [1, 2, 3, 4, 5, 6];
const alternateSort = (arr = []) => {
// 1단계: 오름차순 정렬
arr.sort((a, b) => a - b);
const N = arr.length;
let mid = Math.floor(N / 2);
// 요소 개수가 홀수라면 작은 그룹에 하나 더 포함
if (N % 2 !== 0) {
mid++;
};
// 2단계: 작은 값 그룹과 큰 값 그룹으로 분리
const small = arr.splice(0, mid);
const big = arr.splice(0, arr.length);
// 3단계: 짝수/홀수 인덱스에 번갈아 배치
for (let i = 0; i < N; i++) {
if (i % 2 === 0) {
arr[i] = small.pop();
} else {
arr[i] = big.pop();
};
};
};
alternateSort(arr);
console.log(arr);실행 결과
콘솔 출력 결과는 다음과 같습니다.
[ 3, 6, 2, 5, 1, 4 ]
동작 원리 상세 설명
코드가 어떻게 동작하는지 단계별로 살펴보겠습니다.
1. 정렬 및 분할
[1, 2, 3, 4, 5, 6]을 오름차순 정렬한 후, 요소가 6개이므로 mid는 3이 됩니다. splice 메서드를 통해 앞의 3개 [1, 2, 3]은 small 그룹으로, 남은 [4, 5, 6]은 big 그룹으로 분리됩니다.
2. pop()으로 역순 배치
pop()은 배열의 마지막 요소를 제거하며 반환합니다. 따라서 small 그룹에서는 3, 2, 1 순서로, big 그룹에서는 6, 5, 4 순서로 꺼내지게 됩니다.
- 인덱스 0(짝수): small.pop() → 3
- 인덱스 1(홀수): big.pop() → 6
- 인덱스 2(짝수): small.pop() → 2
- 인덱스 3(홀수): big.pop() → 5
- 인덱스 4(짝수): small.pop() → 1
- 인덱스 5(홀수): big.pop() → 4
그 결과 최종적으로 [3, 6, 2, 5, 1, 4]라는 교차 정렬 배열이 완성됩니다.
마무리
이 알고리즘은 정렬에 O(N log N), 배치에 O(N)이 소요되므로 전체 시간 복잡도는 O(N log N)입니다. 추가 배열 없이 원본 배열을 직접 수정(in-place)한다는 점도 참고하시기 바랍니다. 이 패턴은 '웨이브 정렬(wave sort)'이라고도 불리며, 코딩 테스트에서 자주 등장하는 유형이니 익혀두면 유용합니다.