퀵정렬 - [파이썬 알고리즘 인터뷰]

퀵정렬[Lomuto partition]

• Lomuto가 제안한 파티션 교환 정렬(partition-exchange sort) 알고리즘에 대해서만 얘기하겠습니다.

Lomuto가 제안한 퀵정렬은 배열의 가장 끝 값을 pivot으로 정하면 pivot를 기준으로 양 쪽 [left, right] 2부분으로 나누며 pivot 보다 작은 경우 left, 큰 경우 right로 partition하면서 정렬을 한다.

코드를 요약하면 다음과 같다.

• pivot보다 right가 작은 경우 현재의 left, right의 위치를 바꾸는 정렬 함수이다.

# 파이썬 알고리즘 인터뷰에 나와있는 알고리즘
def quicksort(arr, low, high) : 
    def partition(low,high) :
        pivot = arr[high]
        left = low # 값의 시작 범위
        for right in range(low, high) : 
            if arr[right] < pivot :
                arr[left], arr[right] = arr[right], arr[left] 
                left +=1  # 스왑 후 단계를 증가시킨다.
        arr[left], arr[high] = arr[high], arr[left]
        return left
    
    if low < high : 
        pivot = partition(low, high)
        # print("arr : ", arr)
        quicksort(arr, low, pivot-1)
        quicksort(arr, pivot+1, high )
    
    return arr

# 입력 

array = [2,8,7,5,3,1,6,4]
low = 0
high = len(array)-1
res = quicksort(array, low, high)
res
# 결과 : 
# [1, 2, 3, 4, 5, 6, 7, 8]

위의 퀵정렬 알고리즘을 실행을 하는 경우 평균적으로 O(${n\log{n}}$)의 시간 복잡도를 가집니다.

하지만, array = [1, 2, 3, 4, 5, 6, 7, 8]와 같은 경우 파티셔닝이 이루어 지지 않고 n번의 비교를 해야 하므로, O($N^2$)의 시간복잡도를 가집니다.

위의 코드를 실행할 때 print(arr) 부분의 주석을 지우고 코드를 실행하면 맨끝에 있던 pivot인 $4$가 중앙으로 위치한 후 왼쪽과 오른쪽 부분에서 정렬이 이루어지는 것을 확인할 수 있습니다.

• 자신의 위치를 찾아과는 과정

  arr : [2, 3, 1, 4, 8, 7, 6, 5]
  arr : [1, 3, 2, 4, 8, 7, 6, 5]
  arr : [1, 2, 3, 4, 8, 7, 6, 5]
  arr : [1, 2, 3, 4, 5, 7, 6, 8]
  arr : [1, 2, 3, 4, 5, 7, 6, 8]
  arr : [1, 2, 3, 4, 5, 6, 7, 8]

pivot를 기준으로 left, right로 나뉘며 해당 partition에서 다시 pivot를 기준으로 작으면 ,왼쪽 크면 오른쪽으로 쪼개면서 정렬을 진행한다.

위와 같이 pivot를 기준으로 잡고 pivot의 좌, 우를 나누는 특징때문에 퀵정렬을 파티션 교환 정렬(Partition-Exchange Sort)라고도 부릅니다.

---

Reference

• 도서: 파이썬 알고리즘 인터뷰