[Divide and Conquer] partition 함수 구현하기

실습 설명

partition 함수를 작성하세요.

partition 함수는 리스트 my_list, 그리고 partition할 범위를 나타내는 인덱스 start와 인덱스 end를 파라미터로 받습니다. my_list의 값들을 pivot 기준으로 재배치한 후, pivot의 최종 위치 인덱스를 리턴해야 합니다.

예시 1

Pivot(기준점)은 마지막 인덱스에 있는 5.

list1 = [4, 3, 6, 2, 7, 1, 5]
pivot_index1 = partition(list1, 0, len(list1) - 1)
print(list1)
print(pivot_index1)

 

[4, 3, 2, 1, 5, 6, 7]
4

5보다 작은 값들은 왼쪽에, 5보다 큰 값들은 오른쪽에 배치됩니다.

예시 2

Pivot(기준점)은 마지막 인덱스에 있는 4.

list2 = [6, 1, 2, 6, 3, 5, 4]
pivot_index2 = partition(list2, 0, len(list2) - 1)
print(list2)
print(pivot_index2)

[1, 2, 3, 4, 6, 5, 6]
3

4보다 작은 값들은 왼쪽에, 4보다 큰 값들은 오른쪽에 배치됩니다.

팁

partition 함수를 작성하다 보면 코드가 꽤나 지저분해질 수 있습니다. 특히 리스트에서 값들의 위치를 바꿔주는 경우가 많은데요. 코드가 지저분해지는 걸 방지하기 위해서 swap_elements라는 함수를 먼저 작성하는게 좋습니다.

list1 = [1, 2, 3, 4, 5, 6]
swap_elements(list1, 2, 5)  # 2번 인덱스 값과 5번 인덱스 값 위치 바꿈
print(list1)                # => [1, 2, 6, 4, 5, 3]

swap_elements 함수가 제대로 작동하는지 확인하고 나서 partition 함수를 작성해 주세요.

partition.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
    


# 테스트 코드 1
list1 = [4, 3, 6, 2, 7, 1, 5]
pivot_index1 = partition(list1, 0, len(list1) - 1)
print(list1)
print(pivot_index1)

# 테스트 코드 2
list2 = [6, 1, 2, 6, 3, 5, 4]
pivot_index2 = partition(list2, 0, len(list2) - 1)
print(list2)
print(pivot_index2)

해결과정

i(Unknown: 아직모름), p(pivot : 기준점), b(big : pivot보다 큼)를 적절히 설정해서 로직을 구현했지만, 

처음에는 for i in range(len(my_list)): 라고 범위를 설정해줬는데, 이렇게 범위를 잡아주면 len(my_list)-1까지 i가 리스트를 돌게된다. 그래서 end까지 보는것이 아닌 end보다 한번 더 for문이 실행된다는 시행착오를 겪었다.  범위는 my_list index end 까지 봐야하기 때문에 for i in range(end): 로 설정해준다면 i는 end - 1까지 돌게 될 것이다.