🗽 1517번: 버블 소트

👉🏻 1517번: 버블 소트

☀️ 오늘의 문제

def merge_sort(arr, temp, left, right):
    # 병합 정렬의 종료 조건을 나타내는 코드, 배열의 크기가 1이하인 경우
    if ____:
        return 0

    mid = (left + right) // 2
    inv_count = 0

    # 왼쪽과 오른쪽을 나누어 정렬하고 swap 횟수를 계산
    inv_count += merge_sort(arr, temp, left, mid)
    inv_count += merge_sort(arr, temp, mid + 1, right)

    # 병합 과정에서 swap 횟수를 계산
    inv_count += merge(arr, temp, left, mid, right)

    return inv_count

def merge(arr, temp, left, mid, right):
    i = left
    j = mid + 1
    k = left
    inv_count = 0

    # 병합 과정에서 swap 횟수 계산
    while i <= mid and j <= right:
        #  왼쪽 배열과 오른쪽 배열의 요소를 비교하여 작은 값을 temp 배열에 삽입하기 위한 조건
        if ____:
            temp[k] = arr[i]
            i += 1
        else:
            temp[k] = arr[j]
            j += 1
            inv_count += ____  # 남아있는 왼쪽 배열 요소 개수만큼 swap 발생
        k += 1

    # 남아있는 요소들을 병합
    while i <= mid:
        temp[k] = arr[i]
        i += 1
        k += 1

    while j <= right:
        temp[k] = arr[j]
        j += 1
        k += 1

    # temp의 내용을 원래 배열로 복사
    for i in range(left, right + 1):
        arr[i] = temp[i]

    return inv_count

 

---

🤔 어떻게 풀었을까?

💭 빈칸 1

• 병합 정렬은 '분할 정복' 알고리즘입니다. 재귀적으로 배열을 반으로 나누다가 주석처럼 하나의 원소만 남거나 혹은 아무 원소도 없을 때 정렬할 필요가 없는 상태가 됩니다.
• 조건이 left >= right로 설정되어야, '배열의 길이가 1 이하인 경우'라는 의미가 쓰일 수 있습니다.
  • left == right이면 원소가 1개 남고, left > right이면 말이 안 되게 되죠.
• 책장을 정리할 때 생각해보면, 책 한 권만 있으면 추가로 정리할 필요가 없듯이,
• 한 개의 원소로는 순서를 바꿀 일이 없어서 이미 정렬 완료! 라고 보시면 됩니다.

# 병합 정렬의 종료 조건을 나타내는 코드, 배열의 크기가 1이하인 경우
if left >= right:
    return 0

 

💭 빈칸 2

• 사실 저는 처음에 arr[i] < arr[j]가 정답이 아닐까? 생각해서 틀린 문제입니다.
• 근데 해당 설명을 살펴보니 두 요소가 같게 되는 경우에 원래의 순서가 밀릴 수도 있는 것 같습니다.
• '안정 정렬을 보장하기 위함'이라고 나와있는데, 동일한 값의 요소들이 정렬 후에도 원래 배열에서의 순서를 유지하는 특성을 가지게 하기 위해 < 대신 <=를 사용한다고 합니다.

# 병합 과정에서 swap 횟수 계산
while i <= mid and j <= right:
    # 왼쪽 배열과 오른쪽 배열의 요소를 비교하여 작은 값을 temp 배열에 삽입하기 위한 조건
    if arr[i] <= arr[j]:
        temp[k] = arr[i]
        i += 1

 

💭 빈칸 3

• 왼쪽 배열은 이미 정렬이 되어 있습니다. 만약 현재 인덱스가 i라면, arr[i]부터 arr[mid]까지의 원소들은 모두 오름차순으로 정렬되어 있습니다.
• 이 else 구문에 들어왔다는 것은 병합하는 도중에 '오른쪽 배열의 원소 arr[j]가 왼쪽 배열의 현재 원소 arr[i]보다 작다'라는 뜻인데,
  • 이건 단순히 arr[i]와 arr[j]만의 문제가 아니라,
  • 왼쪽 배열에 남아 있는 모든 원소들(그러니까 i번째 원소 arr[i]부터 arr[i+1], ..., arr[mid])이 죄다 arr[j]보다 큰 상황입니다.
• 그래서 이때 남은 왼쪽 배열의 원소 개수를 (mid - i + 1)로 계산하는 것입니다.
• 그 다음 오른쪽 배열의 원소 arr[j]가 남은 (mid - i + 1)개 만큼의 왼쪽 원소와 모두 역전 관계에 있기 때문에, swap 횟수를 그만큼 증가시켜야 되는 것이죠!

else:
    temp[k] = arr[j]
    j += 1
    inv_count += (mid - i + 1)  # 남아있는 왼쪽 배열 요소 개수만큼 swap 발생
k += 1