[Python] 퀵 정렬을 위한 partition 함수 구현하기

[ 퀵 정렬을 위한 파티션 함수 구현 ] 

 

퀵 정렬(Quick Sort)은 분할 정복(Divide and Conquer) 알고리즘의 하나로, 리스트를 빠르게 정렬하는 데 사용됩니다. 

이를 위해 파티션 함수는 리스트를 기준값(pivot)을 중심으로 두 개의 부분 리스트로 분할합니다.

 

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

 

 

partition 함수가 퀵 정렬 알고리즘의 핵심 부분이며, 정렬하는 데이터의 분할을 담당하기 때문에

partition 함수의 시간 복잡도는 중요합니다.

 

 

 

▷partition 함수의 시간 복잡도

: 파티션 함수의 시간 복잡도는 주로 데이터를 분할하는 과정에서 결정됩니다.

일반적으로 리스트를 순회하면서 기준값보다 작은 값을 왼쪽으로, 큰 값을 오른쪽으로 이동시키는 과정을 반복합니다.

이때 한 번의 순회에 대해 선형 시간이 소요되므로, 파티션 함수의 시간 복잡도는 O(n)입니다.

 

 

▷평균적인 경우와 최악의 경우의 시간 복잡도 비교

• 평균적인 경우 : 퀵 정렬은 평균적으로 O(n log n)의 시간 복잡도를 갖습니다. 이때 파티션 함수의 시간 복잡도가 O(n)이므로, 파티션 함수의 호출은 전체 퀵 정렬 과정에서 O(n log n)번 발생하게 됩니다.

•  최악의 경우 : 퀵 정렬의 최악의 경우 시간 복잡도는 O(n^2)입니다. 이는 파티션 함수가 항상 한쪽으로만 데이터를 분할하는 경우에 발생합니다. 이 경우에도 파티션 함수의 호출은 O(n)번 발생하지만, 이것이 전체 퀵 정렬의 시간 복잡도를 결정합니다.

 

 

▷파티션 함수가 빠른 정렬 알고리즘 중 하나인 이유

 : 파티션 함수는 퀵 정렬 알고리즘의 분할 단계를 담당하는 핵심 요소입니다.

퀵 정렬은 분할 정복 알고리즘의 한 예로, 리스트를 빠르게 정렬하기 위해 입력을 작은 부분 리스트로 분할하고,

각 부분 리스트를 독립적으로 정렬한 후 결합합니다. 파티션 함수는 리스트를 빠르게 분할하는 데 기여하므로 퀵 정렬 알고리즘의 빠른 속도를 실현하는 데 중요한 역할을 합니다.