BOJ1517 버블 소트

문제

BOJ1517 버블 소트
골드I | 백준 1517 | Python3 파이썬 풀이

알고리즘

Merge Sort 아이디어를 사용했다.
1. 리스트를 절반으로 분할
2. 리스트의 사이즈가 1이라면 반환, 이때 반환된 두 리스트를 정렬한다.
3. 두 포인터를 이용해 두 배열의 첫 자리 원소 중 작은 값을 넣는 방식으로 정렬한다.

Bubble Sort에서

특정 수가 swap 되는 수 : 자기 기준 왼쪽에 큰 수의 개수만큼 swap이 일어난다.

예) 초기 배열에서의 10의 경우 자신의 왼쪽에 큰 수가 12, 20 두 개이므로 swap이 2번 일어난다. 나머지 수는 자신의 왼쪽 편에 자신보다 큰 수가 0개이므로 총 swap은 2 + 0 + 0 + 0으로 2번 일어난다.

Merge Sort에서 swap 횟수를 구해본다.

예를 들어, 10이 선택되었을 때 10은 4칸 배열 2번 인덱스에서 0번으로 이동하며 swap이 2번 일어난다고 계산할 수 있다. 즉, 10 기준 좌측 배열에 자신보다 큰 값의 수가 swap 횟수이다. 즉, 우측 배열의 값이 insert 되는 경우에 좌측 배열에 자신보다 큰 수의 개수가 swap 횟수이다.

좌측 배열에서 insert 되는 경우에는 swap이 일어나지 않는다고 볼 수 있다.

예를 들어 20이 insert 되는 경우에 20은 자신보다 왼쪽으로 이동하지 않고 insert 된다. 즉, 10이 이동할 때 한 칸 뒤로 이동한 것이므로 10이 이동할 때만 swap이 발생하는 것이다.

즉, 위 예시에서 12가 insert 될 때 좌측 배열에 더 큰 값 수가 2이므로 +2, 21이 insert 될 때 남은 수가 0개이므로 +0이다.

코드

import sys
sys.setrecursionlimit(10**4)

input = sys.stdin.readline

def MergeSort(start, end):
    global swap, arr
		
    SIZE = end - start
    mid = (start + end) // 2
    if SIZE <= 1:
        return
 
    # divide
    MergeSort(start, mid)
    MergeSort(mid, end)
 
    # merge
    new_arr = []
    idx1, idx2 = start, mid
    
    count = 0
    
    while idx1 < mid and idx2 < end:
		# left is bigger
        if arr[idx1] > arr[idx2]:
            new_arr.append(arr[idx2])
            idx2 += 1
            count += 1

		# right is bigger
        # arr[idx1] < arr[idx2]
        else: 
            new_arr.append(arr[idx1])
            idx1 += 1
            # 오른쪽 배열에서 merge 될 때 왼쪽 배열에 큰 값의 수를 합쳐 줌
            swap += count
    
	# 남은 원소 처리
    while idx1 < mid:
        new_arr.append(arr[idx1])
        idx1 += 1
        swap += count
    while idx2 < mid:
        new_arr.append(arr[idx2])
        idx2 += 1
    
    # 반영
    for t in range(len(new_arr)):
        arr[start + t] = new_arr[t]
 

N = int(input())
# array 생성
arr = list(map(int, input().split()))
swap = 0

MergeSort(0, N)

print(swap)

결과