Sorting - (7)

버블 소트(백준 1517번, 시간 제한: 1초)

문제
N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.

버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.

입력
첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다.

출력
첫째 줄에 Swap 횟수를 출력한다.

입력 예시
3
3 2 1

출력 예시
3

코드 예시

import sys
input = sys.stdin.readline

def merge_sort(start,end):
    if(start<end):
        middle=(start+end)//2
        merge_sort(start,middle)
        merge_sort(middle+1,end)
        merge(start,middle,end)

def merge(start,middle,end):
    global result
    i=start
    k=start
    j=middle+1
    while i<=middle and j<=end :
        if list[i]<=list[j]:
            sorted[k]=list[i]
            k+=1
            i+=1
        else:
            sorted[k]=list[j]
            result=result+middle-i+1
            j+=1
            k+=1
    while i<=middle:
        sorted[k]=list[i]
        k+=1
        i+=1
    while j<=end:
        sorted[k]=list[j]
        k+=1
        j+=1
    for s in range(start,end+1):
        list[s]=sorted[s]

N=int(input())
list=list(map(int,input().split()))
sorted=[0]*int(N)
result = 0
merge_sort(0,N-1)
print(result)

이 문제는 이름과는 달리, 버블 소트를 하게되면 시간초과가 뜬다. N=500,000 이기 때문이다.

머지 소트는 정렬 시에, 투 포인터를 비교하며 정렬이 되는데, 이때 왼쪽으로 몇 칸이 이동하는지 세는 것과 같다.
이때, 배열 2개를 L(i 포인터), R(j 포인터) 이라고 할때, L 쪽의 현재 포인터가 더 크다면 (middle+1-i) 를 더해주면 된다.

=> 이정도 swap 이 되어야 함.