2022.07.30.md

합병 정렬 구현하기

내 코드

def merge(list1, list2):
    i = 0
    j = 0

    # 정렬된 항목들을 담을 리스트
    merged_list = []

    # list1과 list2를 돌면서 merged_list에 항목 정렬
    while i < len(list1) and j < len(list2):
        if list1[i] > list2[j]:
            merged_list.append(list2[j])
            j += 1
        else:
            merged_list.append(list1[i])
            i += 1

    # list2에 남은 항목이 있으면 정렬 리스트에 추가
    if i == len(list1):
        merged_list += list2[j:]

    # list1에 남은 항목이 있으면 정렬 리스트에 추가
    elif j == len(list2):
        merged_list += list1[i:]

    return merged_list

# 합병 정렬
def merge_sort(my_list):
    # 코드를 입력하세요.
    if len(my_list) <= 1:
        return my_list
    else:
        list1 = my_list[:len(my_list)//2]
        list2 = my_list[len(my_list)//2:]
        return merge(merge_sort(list1), merge_sort(list2))

merge 함수 파트는 이전에 사이트에서 제공한 예시 답안을 이용했고, merge_sort 함수 파트는 재귀적으로 구현했다.

퀵 정렬 Quick Sort

합병 정렬에서 combine 단계에 가장 많은 effort가 들어갔던 것과 반대로, 퀵 정렬에서는 divide 단계에 가장 많은 effort가 들어간다.

퀵 정렬은 임의의 pivot 을 하나 설정하고 pivot을 기준으로 더 작은 값들은 왼쪽(오름차순의 경우)으로, 큰 값들은 오른쪽으로 옮긴 뒤(이 과정을 partition 이라고 한다) 왼쪽의 값들을 정렬, 오른쪽의 값들을 정렬하는 과정이 conquer 인데, 그러면 자명하게 combine 단계에서는 할 일이 없다.

퀵 정렬에서 파티션 구현하기

퀵 정렬에서 파티션은 피벗을 기준으로 작은 값과 큰 값을 나누는 일인데, 리스트를

[Small 그룹], [Big 그룹], [Unknown 그룹], [Pivot그룹]

으로 나눠 파티션을 구현할 수 있다. 이를 위해서는 두 개의 포인터가 필요한데, b 와 i 라고 하자.