[Divide and Conquer] 퀵 정렬 구현하기

실습 설명

Divide and Conquer 방식으로 quicksort 함수를 써 보세요. quicksort는 파라미터로 리스트 하나와 리스트 내에서 정렬시킬 범위를 나타내는 인덱스 start와 인덱스 end를 받습니다.

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

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

 

quick_sort.py

# 두 요소의 위치를 바꿔주는 helper function
def swap_elements(my_list, index1, index2):
    # 지난 실습의 코드를 여기에 붙여 넣으세요
    my_list[index1], my_list[index2] = my_list[index2], my_list[index1]
    
    return my_list

    
# 퀵 정렬에서 사용되는 partition 함수
def partition(my_list, start, end):
    # 지난 실습의 코드를 여기에 붙여 넣으세요
    b = 0
    p = end
    for i in range(end): # 범위를 pivot 앞까지 봐야해서 range(end)로 구현
        if my_list[i] <= my_list[p]:
            swap_elements(my_list, i, b)
            b += 1
    
    swap_elements(my_list, p, b)
    p = b
    
    return p

    
# 퀵 정렬
def quicksort(my_list, start, end):
    # 여기에 코드를 작성하세요
    # base case
    if end - start < 1:
        return # return None과 같은 효과
    
    p = partition(my_list, start, end)
    
    # pivot의 왼쪽 부분 정렬
    quicksort(my_list, start, p-1)
    
    # pivot의 오른쪽 부분 정렬
    quicksort(my_list, p+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)

해결과정

#basecase my_list의 길이가 0 또는 1 인 경우

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

#recursivecase

Divide and Conquer

1. Divide: partition 과정을 통해, pivot을 기준으로 리스트를 나눈다.
2. Conquer: pivot 왼쪽 부분과 pivot 오른쪽 부분을 각각 quicksort 함수로 정렬한다.
3. Combine: 따로 할 게 없다!