[알고리즘] 퀵정렬 : partition 함수 구현하기

파티션 : 퀵정렬에서 리스트를 나누는 것

피벗 : 기준점

피벗을 기준으로 값을 새롭게 정렬한다.

ex 피벗보다 작은값들을 왼쪽으로, 큰값을 오른쪽으로

 

1,Divede : 피벗을 설정한다.

2.Conquer : 피벗을 기준으로 정렬한다.

3.Combine : ..(할것 없음)

 

실습설명

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 함수가 제대로 작동하는지 확인하고 나서 partiotion함수를 작성하세요.

 

힌트1

partition 함수는 일단 생각하지말고, swap_elements 함수에대해서만 생각하자.

my_list에서 index1의 값과 index2의 값의 위치를 바꿔줘야하는데, 선택 정렬을 할 때에도 이렇게 자리바꾸는 코드를 작성한 적이 있다.

 

힌트2

temp라는 임시 변수를 이용하면 값들의 위치를 바꿀수 있다.

# 리스트내에 두 인덱스의 항목들을 바꿔주는 함수
def swap_elements(my_list, index1, index2):
    temp = my_list[index1]
    my_list[index1] = my_list[index2]
    my_list[index2] = temp

이제 partition 함수에서 swap_elements 함수를 사용할 수 있다.

 

힌트3

영상에서 봤던 네 그룹(Small, Big, Unknown, Pivot)과 사용되는 변수들 (start, b, i,p)

을 생각하면서 코드를 작성해보자.

힌트4

my_list가 [4,3,6,2,7,1,5] 처럼 주어졌다고 하자.

p는 end와 같으니 이경우에 my_list[p]는 마지막 원소인 5이다.

Step   i        b  my_list[i]                                                     동작                                                                       my_list

1	0	0	4	- 인덱스 i의 값이 인덱스 p의 값보다 작기 때문에 i와 b 인덱스에 있는 값들을 교환 - i += 1 - b += 1	[4, 3, 6, 2, 7, 1, 5]
2	1	1	3	- 인덱스 i의 값이 인덱스 p의 값보다 작기 때문에 i와 b 인덱스에 있는 값들을 교환 - i += 1 - b += 1	[4, 3, 6, 2, 7, 1, 5]
3	2	2	6	- 인덱스 i의 값이 인덱스 p의 값보다 크다. - i += 1	[4, 3, 6, 2, 7, 1, 5]
4	3	2	2	- 인덱스 i의 값이 인덱스 p의 값보다 작기 때문에 i와 b 인덱스에 있는 값들을 교환 - i += 1 - b += 1	[4, 3, 2, 6, 7, 1, 5]
5	4	3	7	- 인덱스 i의 값이 인덱스 p의 값보다 크다. - i += 1	[4, 3, 2, 6, 7, 1, 5]
6	5	3	1	- 인덱스 i의 값이 인덱스 p의 값보다 작기 때문에 i와 b 인덱스에 있는 값들을 교환 - i += 1 - b += 1	[4, 3, 2, 1, 7, 6, 5]
7	6	4	5	- 반복문 종료 - b에 있는 값과 p에 있는 값 바꾸기	[4, 3, 2, 1, 5, 6, 7]

 

 

답안

# 두 요소의 위치를 바꿔주는 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


# 테스트 코드 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)