Quick Sort 알고리즘이란?

안녕하세요 이번 포스트에서는 Quick Sort 알고리즘의 정의를 알아보고 Quick Sort를 Python으로 구현한 코드까지 같이 살펴보도록 하겠습니다.

Quick Sort 알고리즘은 divide and conquer 방식으로 배열을 나누어 가면서 정렬하는 방식으로 다음과 같이 계산됩니다.

1) 배열에서 pivot(중심점)을 선택합니다.

2) 두 번째로, 선택된 pivot보다 작은 값들은 왼쪽으로 큰 값들은 오른쪽으로 움직입니다.

3) 이 과정은 위의 pivot보다 작은 값들로 이루어진 sub array에서도 반복되고 pivot보다 큰 값들로 이루어진 sub array에서도 반복되어서 배열 전체 값이 정렬될때까지 재귀적으로 이루어집니다. 그렇게해서 결과적으로 순서대로 배열이 정렬되게 됩니다.

자세한 설명은 아래 유투브 영상에서 시각적으로 보여주고 있어서 참고 링크를 첨부드립니다.

이 영상에서는 pivot을 선택하고 그 pivot을 기준으로 맨 왼쪽부터 체크해서 pivot보다 큰 값을 itemFromLeft로 정하고 맨 오른쪽부터 체크해서 pivot보다 작은 값을 itemFromRight로 정합니다.

그렇게 해서 itemFromLeft의 순서가 itemFromRight보다 Left 즉 왼쪽에 위치하면 두 값을 서로 교체하고 반대로 itemFromLeft의 순서가 itemFromRight보다 Right 즉 오른쪽에 위치하면 itemFromLeft 값을 pivot과 교체합니다. index로 표현하면 index(itemFromLeft) < index(itemFromRight) 이면 두 값을 교체하지만 index(itemFromLeft) > index(itemFromRight) 이면 이제itemFromLeft를 pivot과 교체합니다.

그러면 pivot 기준 좌측에 있는 값들은 pivot보다 전부 작고 우측에 있는 값들은 pivot보다 전부 크게 됩니다.

이후 pivot 기준 좌측 sub array와 우측 sub array에서 위와 같은 과정을 반복하면 결과적으로 순서가 sorting이 됩니다.

관련해서 Python 코드를 보겠습니다. Python 코드는 아래 유투브 영상의 댓글에서 Mr. UncleChu 라는 분이 굉장히 깔끔한 코드를 써놓아서 이 코드를 가져왔고 제가 마지막 리턴하는 부분만 수정하였습니다. 원본 코드는 리턴하는 값이 sum([lesser, [a_array[0]], bigger], []) 인데, sum 함수 안에 숫자가 아닌 것을 넣을 경우 성능이 좋지 않기 때문에 그 한 줄만 바꾸었습니다.

from functools import reduce 

def quick_sort(a_array):
    if len(a_array) < 2: return a_array
    lesser = quick_sort([x for x in a_array[1:] if x <= a_array[0]])
    bigger = quick_sort([x for x in a_array[1:] if x >  a_array[0]])
    return reduce(lambda x, y: x+y, [lesser, [a_array[0]], bigger])

보시면 quick_sort 라는 재귀함수로 구성되어 있고 처음에 [6,2,3,5,9,0,1,7,8,10,4] 라는 배열이 있다고 하면, 이 코드에서 a_array[0] 즉 6은 최초의 pivot이 됩니다.

여기에서는 pivot을 선택할 때 전체 배열의 맨 처음, 중간, 끝 중에서 중앙값을 선택하는 방식으로 하지 않고 단순히 배열의 0번을 pivot으로 지정합니다.

재귀함수가 lesser 계산하면서도 있고 bigger 계산하면서도 있기 때문에 순서를 따라가는 것이 복잡하지만 위에 공유드린 코드에서 하나하나 값들을 print로 출력해서 보시면 이 순서를 따라가실 수 있을 것입니다. 하나하나 print 하는 코드는 다음과 같습니다.

from functools import reduce 

def quick_sort(a_array):
    print("start: ", a_array, len(a_array))
    if len(a_array) < 2: return a_array
    print("pivot 1: ", a_array[0], a_array)
    print("total 1: ",a_array[1:], "quick sort 1: ", [x for x in a_array[1:] if x <= a_array[0]])
    lesser = quick_sort([x for x in a_array[1:] if x <= a_array[0]])
    print("lesser: ", lesser)

    print("pivot 2: ", a_array[0], a_array)
    print("total 2", a_array[1:], "quick sort 2", [x for x in a_array[1:] if x >  a_array[0]])
    bigger = quick_sort([x for x in a_array[1:] if x >  a_array[0]])
    print("bigger: ", bigger)
    print(lesser, a_array[0], bigger)
    print("answer: ", reduce(lambda x, y: x+y, [lesser, [a_array[0]], bigger]))
    return reduce(lambda x, y: x+y, [lesser, [a_array[0]], bigger])
 
test_array = [6,2,3,5,9,0,1,7,8,10,4]
quick_sort(test_array)

구두로 풀어서 설명드리면,

전체 배열 [6,2,3,5,9,0,1,7,8,10,4] 에서 0번 index 값인 6을 pivot으로 결정하면 pivot을 제외한 배열 a_array[1:]인 [2,3,5,9,0,1,7,8,10,4] 중에서 6보다 작은 값들을 선택해서 sub array를 만듭니다. 그러면 [2, 3, 5, 0, 1, 4] 가 되는데 여기서 quick_sort 함수가 호출이 됩니다. 그러면 [2, 3, 5, 0, 1, 4] 에 대해서 다시 pivot을 계산합니다. 이번에는 2가 pivot이 되고 2를 제외한 나머지 sub array [3, 5, 0, 1, 4] 에서 2보다 작은 값들로 배열을 만들면 [0, 1] 이 되는데 여기서 또 quick_sort 함수가 호출이 됩니다. 그러면 이번에는 pivot이 0이 되고 0보다 작은 값은 없기 때문에 그 배열은 []이 됩니다. 그러면 []를 가지고 다시 quick_sort가 호출이 되는데 이번에는 배열의 length가 2보다 작기 때문에 배열이 if 절에서 바로 리턴되고 더이상 lesser에서 quick_sort가 호출될 수 없으므로 0이 pivot일 때 lesser가 계산이 되어서 lesser는 [] 가 됩니다. 그러고 나서 pivot이 0인 상태에서 이제 bigger가 계산이 되는데 그 값은 [1]로 여기서 다시 quick_sort가 호출되는데 length가 2보다 작기 때문에 배열이 if 절에서 바로 리턴되고 마저 pivot이 0일 때의 bigger가 [1]로 계산됩니다. 그러면 lesser []. pivot 0, bigger [1] 해서 answer가 [0, 1]이 되고 이제 pivot 0일 때 해야하는 것은 다 끝났기 때문에 마저 pivot 2일 때 lesser를 계산하던 로직으로 가서 lesser가 [0, 1]이 되고 pivot 2일 때 bigger를 계산하는 로직으로 넘어갑니다.이번에는 2보다 큰 값들이 [3, 5, 4] 되면서 이제 이 값을 기준으로 다시 quick_sort가 호출됩니다. 그러면서 꼬리에 꼬리를 물고 계속 더 이상 호출될 quick_sort가 없을 때까지 재귀적으로 진행된다고 보시면 됩니다.

크게 로직을 이해해보면 오히려 더 이해가 쉬워지는데요 pivot 하나를 정해서 (코드 상에서는 array의 0번째 값) 이 pivot보다 작은 값들로 이루어진 배열을 lesser, 큰 값들로 이루어진 배열을 bigger라고 하고 그 안에서도 재귀적으로 새로운 pivot을 기준으로 lesser와 bigger을 계산해주는 것입니다. 이렇게 재귀적으로 반복하다보면 최종적으로 한 pivot을 기준으로 lesser와 bigger가 나눠지는데 lesser 안에서도 순서대로 되어 있고 bigger 안에서도 순서대로 되어있어서 최종적으로 lesser, pivot, bigger 를 보면 전체 배열이 sorting이 되어있습니다.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s