JavaScript 재귀 함수로 스택 요소 제자리 정렬하기

정수 배열을 입력받아 재귀(recursion)와 배열의 push, pop 메서드만을 활용해 스택을 제자리(in-place)에서 오름차순으로 정렬하는 JavaScript 함수를 작성해 보겠습니다.

접근 방식

이 문제는 두 개의 재귀 함수를 조합하여 해결할 수 있습니다.

1. sortStack 함수: 스택의 최상단 요소를 pop으로 꺼낸 뒤, 남은 스택에 대해 자기 자신을 재귀 호출합니다. 재귀가 모두 끝나면 꺼내둔 요소를 sortedInsert를 통해 올바른 위치에 다시 삽입합니다.

2. sortedInsert 함수: 스택이 비어 있거나 삽입하려는 값이 최상단 요소보다 크면 그대로 push합니다. 그렇지 않다면 최상단 요소를 임시로 pop하고, 나머지 스택에 대해 재귀 호출한 후 꺼내둔 요소를 다시 push하여 정렬된 순서를 유지합니다.

예제 코드

const stack = [-3, 14, 18, -5, 30];

const sortStack = (stack = []) => {
    if (stack.length > 0) {
        let t = stack.pop();
        sortStack(stack);
        sortedInsert(stack, t);
    }
}

const sortedInsert = (stack, e) => {
    if (stack.length == 0 || e > stack[stack.length - 1]) {
        stack.push(e);
    } else {
        let x = stack.pop();
        sortedInsert(stack, e);
        stack.push(x);
    }
}

sortStack(stack);
console.log(stack);

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

[ -5, -3, 14, 18, 30 ]

동작 원리 살펴보기

sortStack은 재귀 호출을 통해 스택의 모든 요소를 하나씩 꺼내며 콜 스택에 저장합니다. 가장 깊은 재귀(스택이 빈 상태)에 도달하면 역순으로 되돌아오면서 각 요소를 sortedInsert로 정렬된 위치에 삽입합니다.

sortedInsert 역시 재귀적으로 동작하기 때문에, 별도의 반복문이나 임시 배열 없이 순수하게 push와 pop 연산만으로 스택 전체가 오름차순으로 정렬됩니다. 이 알고리즘의 시간 복잡도는 O(n²)이며, 공간 복잡도는 재귀 호출 스택으로 인해 O(n)입니다.