알고리즘 테마: Merge Sort

통합 정렬(Merge Sort)을 말하자면 정렬계에서의 지위가 낮지 않다. 왜냐하면 O(nlogn)가 비교적 정렬하는 3대 정렬 방법은 바로 Quick Sort, Merge Sort와 Heap Sort이다.병합 정렬은 전형적인 분리 치료 방법이다. 먼저 가장 간단한 분류 실현을 보자.

def merge_sort(lst):
    """Sortsthe input list using the merge sort algorithm.

    # >>> lst = [4, 5, 1, 6, 3]
    # >>> merge_sort(lst)
    [1, 3, 4, 5, 6]
    """
    if len(lst) <= 1:
        return lst
    mid = len(lst) // 2
    left = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])
    return merge(left, right)

def merge(left, right):
    """Takestwo sorted lists and returns a single sorted list by comparing the
    elements one at a time.

    # >>> left = [1, 5, 6]
    # >>> right = [2, 3, 4]
    # >>> merge(left, right)
    [1, 2, 3, 4, 5, 6]
    """
    if not left:
        return right
    if not right:
        return left
    if left[0] < right[0]:
        return [left[0]] + merge(left[1:], right)
    return [right[0]] + merge(left, right[1:])

분명히 병합 정렬은 전형적인 분할 치료(Divide and Conquer, D&C) 알고리즘이다. 사상은 먼저 두 개의 데이터를 각각 정렬한 다음에 병합하는 것이다.이렇게 하면 T(n) = 2T(n/2) + O(n), Master Theorem에서 얻을 수 있는 시간 복잡도는 O(nlogn)이다.구체적인 실현을 다시 보다.정렬 주체 함수는 귀속을 사용하는데 귀합 알고리즘은 일반적으로 이렇다.merge 부분도 사실 교체로 완성할 수 있다.

def merge_2(left, right):
    p1 = p2 = 0
    temp = []
    while p1 < len(left) and p2 < len(right):
        if left[p1] <= right[p2]:
            temp.append(left[p1])
            p1 += 1
        else:
            temp.append(right[p2])
            p2 += 1
    while p1 < len(left):
        temp.append(left[p1])
        p1 += 1
    while p2 < len(right):
        temp.append(right[p2])
        p2 += 1
    return temp 

단순히 이 상황에 대해 말하자면, 교체된merge는 지루하고 효율이 향상되지 않았다.그러나 그 장점은 적용성이 넓다는 것이다. 왜냐하면mergesort의 변형이 많아서merge 함수를 귀속적으로 호출하기 불편하기 때문이다.변형:mergesort는 tweak의 응용이 많은데 대부분이 수조의 전후 관계를 고려해야 한다.
예1.하나의 수조nums를 제시하려면 모든 수의 index 다음에 그것보다 큰 수의 개수에 대해 화합을 구해야 합니다.예를 들어 [7, 4, 5, 2, 8, 9, 0, 1]을 제시하고 11을 되돌려줍니다. 7 뒤에 8, 9 두 개가 그보다 크기 때문입니다. 4는 3개, 5는 2개, 2는 2개, 8은 1개, 0은 1개로 총 2+3+2+11=11입니다.
[해] Method1: 하나의naive 방법은 모든 수에 대해 그 뒤에 있는 것보다 큰 수를 두루 검색하는 것이다. 분명히 시간 복잡도는 O(n^2)이다.
Method 2: 또 하나의 방법은 Segment Tree를 고려하여 min에서 max까지의 라인 트리, O(max(n)-min(n)을 먼저 구축하는 것입니다. 초기count는 모두 0입니다.그리고 반대방향으로 생각해서 앞에 작은 것이 몇 개인지 생각해 보세요.즉, 어떤 n[i]에 대해 [min(n), n[i]-1] 구간 안에 몇 개의 count가 있는지 고려한다.끝나면 n[i]의count++.이 예를 들어 먼저 7을 넣고 4가 들어올 때 [0,3] 구간을 검색한다. 4보다 작기 때문에 4의count를 1로 설정한다.이렇게 하면 5가 들어올 때 4의 존재를 검색할 수 있다.이 알고리즘의 다음 단계는 O(nlogn)이지만 라인 트리를 만들어야 합니다. 만약max가 매우 크다면 적합하지 않습니다.물론 argue가 말하기를 나는 아예 가장 작고 가장 큰 32개의 int를 포괄하는 라인 트리를 구성할 수 있다. 이것은 역시 O(1)일까 XD일까.
Method 3: 이 해법은mergesort의 tweak를 사용하는 것을 고려합니다.n[i] 다음에 그것보다 큰 수를 요구하기 때문에 나누어 다스릴 수 있는 사상을 사용할 수 있다. 즉, 앞쪽이 몇 개인지, 뒤쪽이 몇 개인지를 고려한 다음에 그 사이에 몇 개가 있는지 고려할 수 있다.이 예로 말하자면 마지막 메르지 이전의 모습을 고려한다:[2,4,5,7][0,1,8,9]. 이때 양쪽 모두 계산이 끝났고merge에서 발생한 결과만 계산하면 된다.분명히 결과는 8이었다. 왜냐하면 앞부분의 네 수가 모두 8과 9보다 적기 때문이다.그런데 어떻게 계산하나요?후반이 이미 순서를 정했음을 감안하면, 후반에 대해binarysearch를 사용한다면, 당연히 첫 번째로 앞반의 어느 수보다 큰 index를 얻을 수 있고, 이 수보다 큰 모든 수를 얻을 수 있다.그러니까 이merge가 O(nlogn)라는 거야.그러면 전체적으로 T(n)=T(n/2)+O(nlogn)이고 Master Theorem에서 알 수 있는 복잡도는 O(n(logn)^2)이다.
Method4: 단, 위의 이merge 방법은 앞부분도 순서를 정하는 조건이 없기 때문에 더 잘할 수 있습니다.두 개의 지침 p1과 p2를 고려하여 각각 앞반과 뒤반을 가리킨다.p1은 처음에 2, p2는 0이었다. 왜냐하면 이때 n[p2]=n[p2]이 반쪽이 늘어나기 때문에 뒤쪽의 긍정도 n[p2]보다 크기 때문에 뒤로 볼 필요가 없다. 개수를 직접 계산할 수 있다. p1-s, s는 차례로 사용하는 시작의 index이고 여기는 0이다.즉, n[p2]보다 작은 것은 없다.그리고 p2를 점차적으로 증가하지만 주의해야 할 것은 p1이 리셋하지 않는 것이 매우 관건적인 점이다.왜?왜냐하면 p1이 멈추는 조건은 이미 절반을 쓸었거나 현재의 n[p1]이 n[p2-1]보다 크다. 즉, 현재의 p1은 n[p2-1]보다 작고 n[p2]>n[p2-1]이기 때문에 앞의 것들은 비교할 필요가 없기 때문에 결론을 알 수 있고 이전의 p1의 위치를 그대로 사용할 수 있다.이 예에서 비교적 뚜렷한 것은 8과 9이다.8에 대해 p1은 절반의 길이로 점차 증가할 것이다. 즉, 전체 절반이 8보다 작다는 것이다. 그러면 9에 대해 8보다 크기 때문에 전체 절반도 9보다 작기 때문에 다시 처음부터 비교할 필요가 없다.다시 일반적인 예를 들자면[2,4,5,7][0,1,6,8], 6,p1은 7 위에 멈추고 계수는 3이다.p2가 점차적으로 증가한 후에 8에 대해 p1이 앞에 6보다 작다는 것을 알 수 있다. 그러면 틀림없이 8보다 작다는 것을 알 수 있다. 따라서 p1이 7에서 시작하여 마지막 계수는 4이다.이렇게 되면merge 함수 두 개의 바늘은 되돌아갈 필요가 없다. 효율 O(n), 전체 효율은 O(nlogn), 공간 복잡도 O(n)이다.물론 구체적으로 실현될 때에는 두 개의 진정한 merge를 순서대로 배열해야 한다. 왜냐하면 위의 계산은 모두 양쪽이 순서를 배열한 상황에서 진행되기 때문이다.원소가 하나밖에 없을 때 바로 0으로 돌아갈 수 있다.코드는 다음과 같습니다.

# count number that larger than it and after it
def dc2(self, n, s, e):
    if s >= e:
        return 0
    m = (s + e) // 2
    ans = self.dc2(n, s, m) + self.dc2(n, m + 1, e)
    p1 = s
    for q in range(m + 1, e + 1):
        while p1 <= m and n[q] > n[p1]:
            p1 += 1
        ans += p1 - s
    # merge
    temp = []
    p1, p2 = s, m + 1
    while p1 <= m and p2 <= e:
        if n[p1] <= n[p2]:
            temp.append(n[p1])
            p1 += 1
        else:
            temp.append(n[p2])
            p2 += 1
    while p1 <= m:
        temp.append(n[p1])
        p1 += 1
    while p2 <= m:
        temp.append(n[p2])
        p2 += 1
    for i in range(len(temp)):
        n[i + s] = temp[i]
    return ans 

예2.하나의 수조 n과 하나의 범위 [a, b]를 제시하고 n이 몇 개의 하위 구간의 합이 [a, b] 안에 있는지 구한다.가령 수조 n의 원소와 a, b는 모두 정수이다.예를 들어[2,3,4,1]과 범위[3,5]를 제시하면 자구간[3][4][2,3][4,1]은 모두 조건을 만족시키고 4로 돌아간다.
[해] Method1:naive 방법은 모든 하위 구간을 찾아서 몇 개의 만족 조건이 있는지 보는 것이다.복잡도가 매우 높다.
Method2: 하위 구간의 합을 보면 prefixsum이 생각납니다.즉, 하나의 수조s를 만들 수 있다는 것이다. 모든 원소 s[i]=n[0]+...+n[i].그러면 모든 하위 구역은 n[0]을 제외하고 s의 다음 원소로 이전 원소를 빼서 얻을 수 있다.즉, 문제는 하나의 수조 s를 제시하고 몇 쌍의 ij를 계산하여 s[i]-s[j] in[a,b] 그리고 iMethod3: 하위 구역 간prefixsum을 바탕으로mergesort의tweak를 고려합니다.가령 n=[7, 4, 5, 2, 8, 9, 0, 1], a=0, b=7.마지막 merge 이전의 상황을 고려한다:[2,4,5,7][0,1,8,9].이전 문제에서 깨우침을 얻었다. 만약에 반의 모든 숫자 s[i]에 대해 반의 2분에서 첫 번째가 s[i]+a보다 큰 index1을 찾아라. 만약에 index1이 존재하지 않는다면 더 이상 찾을 필요가 없고 조건에 부합되지 않는다.s[i]+b보다 큰 첫 번째 index2와 존재하지 않는다면 index2=e는 end의 index입니다.그러면 자연스럽게 개수 index2 - index1을 얻을 수 있습니다.이렇게merge의 복잡도는 O(nlogn), 전체 O(n(logn)^2)이다.
Method 4: Method 3을 기반으로 개선예1과 유사하게 Method 3의 문제는 여전히 절반의 순서를 정하는 조건을 이용하지 않았다는 데 있다.세 가지 지침을 고려하면 p1p2와 q, p1p2는 모두 반쪽을 가리키고 p2는 반쪽을 가리킨다.반정렬의 조건을 이용해야 하기 때문에 고정적으로 점차적으로 증가한다.s[q]에 대해서는 s[q]-s[i]가 구간[a,b]에 있어야 한다.즉, s[q]-s[i]>=a, s[i]<=s[q]-a;s[q] - s[i] <= b, s[i] >= s[q] - b. 따라서 두 개의 지침 p1p2, p1은 s[p1]<=s[q]-a, p2는 s[p2]=a를 만족시켰고, p2 이후의 것은 모두 s[q]-s[i]<=b, p1p2 사이의 것은 조건을 만족시켰다. 즉count+=p1-p2.그리고 점차적으로 q를 증가시킨다. 왜냐하면 s[q]>=s[q-1]이기 때문에 이전 p1p2의 위치는 계속될 수 있다. 즉, s[q]-a>=s[q-1]-a>=s[i]이다. 즉, p1 이전 p2 이전의 요소는 여전히 그 조건을 만족시킨다는 것이다.따라서 이merge 함수의 복잡도는 O(n), 전체 시간 복잡도 O(nlogn), 공간 복잡도 O(n)이다.단일 구간에 주의하는 상황은 이미 포괄되었다.코드는 다음과 같습니다.

class Solution:
    # count numbers of subarray sum in range of [a,b]
    def countSubarraySum(self, nums, a, b):
        if not nums:
            return 0
        n = [0] * len(nums)
        for i in range(len(nums)):
            if i != 0:
                n[i] = nums[i] + n[i - 1]
            else:
                n[i] = nums[i]
        return self.dc(n, a, b, 0, len(n) - 1)

    # count number of prefix sum that x[i] - x[j] in [a, b] and i > j plus itself in [a, b]
    def dc(self, n, a, b, s, e):
        if s > e:
            return 0
        if s == e:
            return a <= n[s] <= b
        m = (s + e) // 2
        ans = self.dc(n, a, b, s, m) + self.dc(n, a, b, m + 1, e)
        p1 = p2 = s
        for q in range(m + 1, e + 1):
            while p1 <= m and n[q] - n[p1] >= a:
                p1 += 1
            while p2 <= m and n[q] - n[p2] > b:
                p2 += 1
            if p2 <= p1:
                ans += p1 - p2
        # merge
        temp = []
        p1, p2 = s, m + 1
        while p1 <= m and p2 <= e:
            if n[p1] <= n[p2]:
                temp.append(n[p1])
                p1 += 1
            else:
                temp.append(n[p2])
                p2 += 1
        while p1 <= m:
            temp.append(n[p1])
            p1 += 1
        while p2 <= m:
            temp.append(n[p2])
            p2 += 1
        for i in range(len(temp)):
            n[i + s] = temp[i]
        return ans