본 QuickSort 알고리즘은 오름차순 정렬을 기본으로 합니다.

구조 파악하기

quicksort

quicksort(low : 왼쪽 끝 인덱스, high : 오른쪽 끝 인덱스):
	if low < high (정상적인 경우):
    
    	# 첫번째 인덱스를 기준으로 작은 건 왼쪽, 큰 건 오른쪽으로 이동시키는 함수
    	partition(low, high, pivotpoint)
        
        # 작은 쪽 배열과
        quicksort(low, pivotpoint  - 1)
        
        # 큰 쪽 배열에 대해 재귀적으로 quicksort 진행
        quicksort(pivotpoint + 1, high)

이번에는 partition 함수에 대해서도 파악해 보자

partition : 배열을 작은 것과 큰 것으로 구분하자

def partition(배열 S, low, high, pivotpoint):
	pivotitem = S[low] # 배열의 가장 왼쪽 아이템 
    i =  S[low]
    
    ''' i의 역할
    작은 원소를 왼쪽으로 보내기 위한 보조 인덱스의 역할을 한다. 조금 더 자세하게는, 현재 pivotitem보다 작은 원소들이 저장된 부분의 가장 오른쪽 인덱스, 즉, 여기까지 작은 애들이에요~ 를 알려주는 역할이다.
    '''

    # i 한 칸 뒤부터 마지막까지 진행하며, pivotitem보다 작은 원소를 찾는다.
    for smaller_finder in low+1 부터 high까지: 
    	if S[smaller_finder] < 기준아이템: # 작은 원소를 찾았다! 그러면
        	j를 한 칸 전진하고,
            다음 원소와 small_finder의 원소를 바꾼다.
            # 위의 과정을 통해 새로 발견된 작은 원소가 왼쪽으로 이동되었다.
    
    pivotpoint를 j로 옮기고,
    기존의 pivotitem 값을 옮겨진 pivotpoint에 넣는다 (기준값이 중앙으로 오게 하기 위함)

위의 partition함수를 통해, 주어진 배열은 pivotitem을 기준으로 작은 값이 왼쪽, 큰 값이 우측으로 오게 된다. 그림으로 다시 한 번 보자.

각각의 부분 배열마다 quicksort 함수를 통해 배열을 작은 쪽과 큰 쪽으로 구분하고, 각각에 대해 다시 quicksort를 재귀호출하여 또다시 작은 쪽과 큰 쪽으로 구분하고... 이러한 과정을 반복하며 전체적으로 배열의 정렬이 완료된다.
이때 위에서 QuickSort 함수를 작은 쪽 (왼쪽)부터 재귀호출하였으므로, 전체적으로 배열의 정렬은 가장 왼쪽 부분부터 완료된다.