[알고리즘 공부] 5. Quick Sort (퀵 정렬)

Quick Sort

 

Quick Sort(퀵 정렬)은 특정 원소를 Pivot으로 잡습니다.

그 후 Pivot을 기준으로 작은 원소는 왼쪽으로 큰 원소는 오른쪽으로 보낸 뒤 Pivot을 이동 시킵니다.

다만 제가 이리저리 검색하면서 공부해본 결과 퀵 정렬의 기본은 딱 여기까지이고

이후 Pivot 설정문제나 이후 정렬 방식 등에 따라 많은 버전이 존재합니다. 

이 말은 곧 Pivot을 어떻게 잡아주느냐에 따라서 알고리즘의 효율이 결정된다는 말이기도 합니다.

일반적으로 퀵 정렬은 시간 복잡도 O(n log n)을 가지고 있으나 최악의 경우 O(n^2)을 가지기도 합니다.

이 글에서는 가장 간단한 퀵 정렬 방식 중 하나인 로무토 파티션 버전을 기준으로 설명 및 코드를 짜겠습니다.

로무토 파티션 방식 예시

위의 방식을 재귀적으로 반복하면 정렬이 되겠죠? 하지만 이미 정렬이 되어있는 수열이라면 Pivot이 항상 오른쪽 끝에

존재할 것이기 때문에 수열을 모두 훑고 지나가는 비효율적인 알고리즘이 되버립니다. 

이러한 문제를 해결하기 위하여 이런저런 방법들이 나와있다고 하는데 일단 지금은 넘어가도록 하겠습니다.

---

input = [14,54,5,2,1,36,324,34,213,6,7,4]

def QuickSort(input):
    
    # 입력된 수열의 길이가 1 초과일 경우
    if len(input) > 1:
        
        # pivot은 항상 수열의 오른쪽 끝 값
        pivot = input[len(input)-1]
        
        # left_pointer는 항상 수열의 왼쪽 첫 값
        left = 0        
        
        # right_pointer는 왼쪽에서 오른쪽으로 한칸씩 이동
        for right in range(len(input)):
        	
            #right_pointer < pivot 일 경우 데이터 스왑
            if input[right] < pivot:
                input[right], input[left] = input[left], input[right]
                left += 1
        
        # 마지막으로 left_pointer와 pivot 데이터 스왑
        input[len(input)-1], input[left] = input[left], input[len(input)-1]
        
        # 이동한 pivot의 위치를 기준으로 left_side, right_side 나누어 재귀
        left_side = QuickSort(input[:left])
        right_side = QuickSort(input[left:])
    
    # 길이가 1 이하 일 경우 그대로 return
    else:
        return input
    
    # 받아온 정렬된 데이터들을 통합
    return left_side+right_side

print(QuickSort(input))