[TypeScript] 자료 구조로 담아내기. #7 - 배열(with. 정렬 유지)

이번 편은 이전 편으로부터 이어집니다.

지난 편에서 다룬 이진 탐색은 정렬되지 않은 배열을 대상으로 사용할 수 없습니다. 그렇다면 배열을 어떻게 정렬 상태로 유지할 수 있을까요?

가장 가까운 후임자 찾기

정렬 상태를 유지함은 삽입이 임의의 위치가 아닌 적절한 위치에 되어야 함을 의미합니다. 그럼 적절한 위치를 어떻게 결정할 수 있을까요? 새 요소의 위치는 현재 이보다 후임자이면서 가장 가까운 위치에 있어야 합니다. 이는 이진 탐색을 조금 변형하여 구현할 수 있습니다.

function binarySearchForNearestSuccessor<T>(
    l: number,
    r: number,
    cmp: (i: number) => number
): number {
    if(r < l) { return l; }

    const i = (l + r) >> 1;
    return cmp(i) <= 0 ?
        binarySearchForNearestSuccessor(l, i - 1, cmp) :
        binarySearchForNearestSuccessor(i + 1, r, cmp);
}

기존 이진 탐색과 크게 차이 나지 않습니다. 가장 큰 차이점은 함수 이름이 길어졌다는 것이겠네요. 주요 차이점은 아래와 같습니다.

1. 좌측 탐색의 조건이 음수에서 0 이하로 변경.

2. 끝 인덱스가 시작 인덱스보다 작을 때가 유일한 반환 조건이 되며, 시작 인덱스를 반환.

이해해 봅시다. 현재 인덱스를 의미하는 i는 조건에 따라 분주하게 움직일 것입니다. 그러나 마지막 비교 대상은 둘 중 하나일 것입니다.

3. 후임자

4. 동등하거나 선임자

마지막 비교 대상이 후임자라면 바로 앞의 요소는 동등하거나 선임자가 됩니다. 즉, 마지막 비교 대상의 위치가 탐색 목표이며. 위치는 l(i)과 같습니다.

반대의 경우, 바로 뒤는 후임자이거나 인덱스가 length인 위치가 됩니다. 즉, 마지막 비교 대상의 다음 위치가 우리가 원하는 목표이며. 위치는 l(i + 1)과 같습니다.

따라서 모든 경우에 l을 반환해야 한다는 결론이 됩니다.

적용

class SortedArrayImpl<T> implements SortedArray<T> {
    set(index: number, element: T): void {
        checkBounds(0, this.slots.length - 1, index);

        const newIndex = binarySearchForNearestSuccessor(
            this.slots, 0, this.slots.length - 1,
            e => this.compare(element, e)
        );

        shl(this.slots, index + 1, newIndex);
        this.slots[newIndex] = element;
    }

    insert(element: T): void {
        const index = binarySearchForNearestSuccessor(
            this.slots, 0, this.slots.length - 1,
            e => this.compare(element, e)
        );

        this.slots.length++;
        shr(this.slots, index, this.slots.length - 2);
        this.slots[index] = element;
    }

    // ...
}

삽입은 탐색 함수를 통해 인덱스를 찾고, 기존 삽입 연산 과정을 연결하면 끝입니다.

설정은 삭제와 삽입이 동시에 일어난다고 생각하면 됩니다. 변경 후 요소의 위치를 찾고, 기존 인덱스부터 새 인덱스까지 범위를 왼쪽으로 시프트합니다. 이렇게 하면 기존 인덱스 요소를 제거함과 동시에 새 인덱스 위치에 공간을 확보할 수 있습니다. 이후 새 인덱스 위치에 새 요소를 저장합니다.

시리즈는 다음 편에서 계속됩니다. 읽어주셔서 감사합니다!

묻고 답하기

개인적인 판단에 의해 적절하다고 여겨지는 경우, 모두가 볼 수 있도록 이곳에 문답이 추가됩니다. 그렇지 않더라도 질문에 대한 답변은 별도로 이루어집니다.