삽입 정렬과 퀵 정렬의 비교 횟수

꿍은 자료구조를 공부하다가, 정렬마다 비교 횟수를 세어 보라는 문제에 진력이 나서 세상에서 가장 얄궂은 문제를 만들어 보기로 했다.

정수 N과 X가 주어진다. 1부터 N까지의 정수로 이루어진 순열 중에서, 삽입 정렬이 퀵 정렬보다 비교를 더 하되 그 차이가 최대 X번인 순열의 개수를 세어야 한다. 즉, 한 순열에 대해 삽입 정렬의 비교 횟수를 NI, 퀵 정렬의 비교 횟수를 NQ라 할 때 1 ≤ NI - NQ ≤ X 를 만족하는 순열의 개수를 구한다. 값이 매우 커질 수 있으므로 1234567 로 나눈 나머지를 출력한다.

아래는 삽입 정렬의 의사 코드이며, 비교 횟수도 함께 센다. 감시자 A[0] = -무한대 를 둔다.

procedure insertionSort(N, A[1..N]):
    A[0] := -infinity
    for i := 2 to N:
        j := i
        comparisons := comparisons + 1
        while A[j - 1] > A[j]:
            swap(A[j - 1], A[j])
            j := j - 1
            comparisons := comparisons + 1

아래는 퀵 정렬의 의사 코드다. 정렬하려는 배열의 길이가 L이면 분할(partition) 과정에서 L - 1번의 비교가 일어난다.

procedure quickSort(A):
    if length(A) <= 1:
        return A
    less := empty list
    greater := empty list
    pivot := A[1]
    for i := 2 to length(A):
        comparisons := comparisons + 1
        if A[i] < pivot:
            append A[i] to less
        else:
            append A[i] to greater
    return concatenate(quickSort(less), pivot, quickSort(greater))

예를 들어 순열 (3, 1, 4, 2) 를 생각하자. 삽입 정렬의 비교 횟수는 총 6회로, i=2일 때 2회, i=3일 때 1회, i=4일 때 3회의 비교가 이루어진다. 퀵 정렬의 비교 횟수는 총 4회다. 피벗이 3일 때 3회를 비교한 뒤 (1, 2) 와 (4) 로 분할되고, 이어서 (1, 2) 에서 1회의 비교가 더 일어나 총 4회가 된다.

첫째 줄에 두 정수 N과 X가 공백으로 구분되어 주어진다.

• 1 < N < 32
• 1 ≤ X ≤ N²

삽입 정렬이 퀵 정렬보다 비교를 1번 이상, X번 이하로 더 하는 순열, 즉 1 ≤ NI - NQ ≤ X 를 만족하는 1부터 N까지의 순열의 개수를 1234567 로 나눈 나머지를 한 줄에 출력한다.

N = 3일 때 가능한 6개의 순열과 각 경우의 비교 횟수(NI = 삽입 정렬, NQ = 퀵 정렬)는 다음과 같다.

1 2 3 - NI = 2, NQ = 3
1 3 2 - NI = 3, NQ = 3
2 1 3 - NI = 3, NQ = 2
2 3 1 - NI = 4, NQ = 2
3 1 2 - NI = 4, NQ = 3
3 2 1 - NI = 5, NQ = 3

각 순열의 차이 NI - NQ 는 차례로 -1, 0, 1, 2, 1, 2 이다. X = 1이면 1 ≤ NI - NQ ≤ 1 을 만족하는 순열은 (2 1 3) 과 (3 1 2) 두 개뿐이므로 답은 2가 된다.