알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - 버블 정렬 프로그램 2

021 버블 정렬 프로그램 2 (백준 1517번)

1517번: 버블 소트

처음에는 버블 정렬 구현했던 코드에서 실제 swap 이루어지는 부분을 카운트 해주기만 하면 된다고 생각했는데 입력 데이터의 크기가 50만이었기 때문에 n²의 시간복잡도로는 풀 수 없다는 것을 알게되었다. 버블 정렬의 시간복잡도 자체가 n²이기 때문에 버블 정렬이 아닌 병합 정렬을 사용해야함..

 

 

swap 횟수 = 정렬한 값 앞의 데이터 개수

 

코드

import sys
input = sys.stdin.readline
result = 0

def merge_sort(s,e):
    global result
    if e-s < 1: return
    m = int(s+(e-s) / 2)
    merge_sort(s,m)
    merge_sort(m+1,e)
    for i in range(s, e+1):
        tmp[i] = A[i] # tmp에 값 복사
    
    k = s
    index1 = s
    index2 = m+1
    while index1 <= m and index2 <= e:
        if tmp[index1] > tmp[index2]:
            A[k] = tmp[index2]
            result = result + index2 - k # swap 값 카운트
            k += 1
            index2 += 1
        else:
            A[k] = tmp[index1]
            k += 1
            index1 += 1
    while index1 <= m:
        A[k] = tmp[index1]
        k += 1
        index1 += 1
    while index2 <= e:
        A[k] = tmp[index2]
        k += 1
        index2 += 1
        
    
N = int(input())
A = list(map(int, input().split()))
A.insert(0,0) # 0번째 값을 채워주는 용도
tmp = [0] * int(N+1) 
merge_sort(1,N)
print(result)