[알고리즘] Divide and Conquer : 퀵 정렬 구현하기

실습설명

Divide and Conquer 방식으로 quicksort 함수를 써보세요. 

quicksort 는 파라미터로 리스트 하나와 리스트 내에서 정렬시킬 범위를 나타내는 인덱스 start와 인덱스 end를 받습니다.

 

merge_sort 함수와 달리 quicksort 함수는 정렬된 새로운 리스트를 리턴하는게 아니라, 파라미터로받는리스트 자체를 정렬시키는 것입니다.

 

swap_elements와 partition 함수는 이전과제에서 작성한 그대로 사용하면 됩니다.

 

힌트1

Divide and Conquer로 문제를 풀기 위해서는 문제를 더 작은 부분 문제로 나누고, 재귀적으로 부분 문제들을 해결해야 하는데요. 재귀적으로 문제를 풀 때에는 늘 base case와 recursive case가 있어야 하죠?

 

그럼 문제를 제대로 파고들기 전에 가장 쉬운 base case부터 봅시다. Base case는 문제가 충분히 작아서 바로 풀 수 있는 경우를 의미해요.

 

힌트2

이전에 작성했던 merge_sort 함수는 재귀적으로 호출되면서 파라미터를 my_list의 길이가 점점 작아집니다. 따라서 my_list의 길이가 0 또는 1인 경우를 base case라고 했었죠.

 

하지만 quicksort 함수는 재귀적으로 호출되면서 파라미터 start와 end만 바뀔 뿐, my_list는 바뀌지 않습니다.

 

그렇다면 quicksort의 base case는 어떻게 표현할 수 있을까요?

 

힌트3

quicksort 함수에서 우리가 정렬하려는 부분의 길이는 end-start입니다. end-start가 0인 경우를 base case라고 할 수 있겠네요.

 

힌트4

# 퀵 정렬
def quicksort(my_list, start, end):
    # base case
    if end - start < 1:
        return # return None과 같은 효과

merge_sort 와 달리 quicksort 함수는 새로운 리스트를 리턴하지 않습니다.

 

 

힌트5

이제 Divide and Conquer를 해야합니다.

1. Divide : partition 과정을 통해, pivot을 기준으로 리스트를 나눈다.

2. Conquer : pivot 왼쪽부분과 pivot 오른쪽 부분을 각각 quicksort 함수로 정렬한다.

3. Combine : 따로할게 없다.

 

 

답안

# 두 요소의 위치를 바꿔주는 helper function
def swap_elements(my_list, index1, index2):
    temp = my_list[index1]
    my_list[index1] = my_list[index2]
    my_list[index2] = temp

# 퀵 정렬에서 사용되는 partition 함수
def partition(my_list, start, end):
    # 리스트 값 확인과 기준점 이하 값들의 위치 확인을 위한 변수 정의
    i = start
    b = start
    p = end

    # 범위안의 모든 값들을 볼 때까지 반복문을 돌린다
    while i < p:
        # i 인덱스의 값이 기준점보다 작으면 i와 b 인덱스에 있는 값들을 교환하고 b를 1 증가 시킨다
        if my_list[i] <= my_list[p]:
            swap_elements(my_list, i, b)
            b += 1
        i += 1

    # b와 기준점인 p 인덱스에 있는 값들을 바꿔준다
    swap_elements(my_list, b, p)
    p = b

    # pivot의 최종 인덱스를 리턴해 준다
    return p

# 퀵 정렬
def quicksort(my_list, start, end):
    # base case
    if end - start < 1:
        return

    # my_list를 두 부분으로 나누어주고,
    # partition 이후 pivot의 인덱스를 리턴받는다
    pivot = partition(my_list, start, end)

    # pivot의 왼쪽 부분 정렬
    quicksort(my_list, start, pivot - 1)

    # pivot의 오른쪽 부분 정렬
    quicksort(my_list, pivot + 1, end)


# 테스트 코드 1
list1 = [1, 3, 5, 7, 9, 11, 13, 11]
quicksort(list1, 0, len(list1) - 1)
print(list1)

# 테스트 코드 2
list2 = [28, 13, 9, 30, 1, 48, 5, 7, 15]
quicksort(list2, 0, len(list2) - 1)
print(list2)

# 테스트 코드 3
list3 = [2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4]
quicksort(list3, 0, len(list3) - 1)
print(list3)