퀵 정렬

퀵 정렬

: 주어진 배열을 두 개로 분할하고, 각각을 정렬한다

 

 

병합 정렬과의 차이점

1. 퀵 정렬은 분할 시에 pivot item을 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킨다.

2. 각 부분 정렬이 끝난 후, 병합 정렬은 병합하는 과정이 필요하나 퀵 정렬은 후처리가 필요하지 않다.

 

 

 

아이디어

- pivot보다 큰 값은 오른쪽, 작은 값들은 왼쪽 집합에 위치하도록 한다.

- 피봇을 두 집합의 가운데에 위치시킨다.

 

 

 

구현

def partition(l, r):
    
    # 피봇을 A[l]로 설정
    pivot = A[l]
    i, j = l, r
    
    # i, j가 교차하면 i, j는 피봇을 기준으로 작은 값과 큰 값들의 경계에 위치
    while i <= j:
        
        # 피봇보다 큰 값을 발견할때 까지 i+1
        while i <= j and A[i] <= pivot:
            i += 1
        
        # 맨 오른쪽 원소부터 피봇보다 작은 값을 발견할때까지 j-1
        while i <= j and A[j] >= pivot:
            j -= 1  
        
        # 두 원소가 떨어져 있다면 두 원소 swap
        if i < j:
            A[i], A[j] = A[j], A[i]

    # 작은 값과 큰 값의 경계가 되는 위치로 피봇 보내기
    A[l], A[j] = A[j], A[l]
    
    return j



def qsort(l, r):
    if l < r:
        s = partition(l, r)
        qsort(l, s-1)
        qsort(s+1, r)
        
        

A = [7, 2, 5, 3, 4, 5]
N = len(A)
qsort(0, N-1)
print(A)


'''
[2, 3, 4, 5, 5, 7]
'''