[Algorithm] 퀵 정렬 (Quick Sort) 알고리즘

퀵 정렬 (Quick Sort)

기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다.

기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미친다.

• 분할 정복(Divide and Conquer)와 재귀 알고리즘을 이용한 정렬 알고리즘이다.
• 파이썬의 list.sort()함수처럼 기본으로 지원되는 내장 정렬 함수는 퀵 정렬을 기본으로 한다.
• 시간 복잡도: O(nlog(n))

 

퀵 정렬 과정

1. 데이터를 분할하는 pivot을 설정한다. (그림의 경우 가장 오른쪽 끝을 pivot으로 설정).

2. pivot을 기준으로 다음 a~e과정을 거쳐 데이터를 2개의 집합으로 분리한다.

    2-a. start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동한다. 

    2-b. end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end를 왼쪽으로 1칸 이동한다.

    2-c. start가 가리키는 데이터가 pivot이 가리키는 데이터보다 크고,end가 가리키는 데이터가 pivot이 가리키는 데이터보            다 작으면 start,end가 가리키는 데이터를 swap하고 start는 오른쪽, end는 왼쪽으로 1칸씩 이동한다

    2-d. start와 end가 만날 때까지 2-a~ 2-c를 반복한다.

    2-e. start와 end가 만나면 만난 지점에서 가리키는 데이터와 pivot이 가리키는 데이터를 비교하여 pivot이 가리키는 데

           이터가 크면 만난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot이 가리키는 데이터를 삽입한다.

3. 분리 집합에서 각각 다시 pivot을 선정한다.

4. 분리 집합이 1개 이하가 될 때까지 과정 1~3을 반복한다.

 

 

그림으로 이해하기

 

퀵정렬  구현 (python)

리스트의 가운데 값을 pivot으로 선택하고, pivot보다 작은 값(lesser_arr), 동일한 값(equal_arr), 큰 값을 담아둘 리스트(greater_arr) 3개의 리스트를 생성한다.

그리고 반복문을 통해 각 값을 pivot과 비교 후에 해당하는 리스트에 추가시킨다.

그 다음 작은 값과 큰 값을 담고 있는 배열을 대상으로 퀵 정렬 함수를 재귀적으로 호출한다.

마지막으로 재귀 호출의 결과를 다시 크기 순으로 합치면 정렬된 리스트를 얻을 수 있다.

def quick_sort(arr):
	if len(arr) <=1:
    	return arr
    pivot = arr[len(arr) // 2]
    lesser_arr,equal_arr, greater_arr = [],[],[]
    for num in arr:
    	if num < pivot:
        	lesser_arr.append(num)
        elif num > pivot:
        	greater_arr.append(num)
        else:
        	equal_arr.append(num)
    return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)

 

최적화한 수도코드 (python)

메인 함수인 quick_sort()는 크게 sort()와 partition() 2개의 내부 함수로 나뉘어진다.

sort() 함수는 재귀 함수이며 정렬 범위를 시작 인덱스와 끝 인덱스로 인자를 받는다.

partition() 함수는 정렬 범위를 인자로 받으며 다음 로직을 따라서 좌우측의 값들을 정렬하고 분할 기준점의 인덱스를 리턴한다. 이 분할 기준점(mid)는 sort()를 재귀적으로 호출할 때 우측 리스트의 시작 인덱스로 사용된다.

 

def quick_sort(arr):
    def sort(low, high):
        if high <= low:
            return

        mid = partition(low, high)
        sort(low, mid - 1)
        sort(mid, high)

    def partition(low, high):
        pivot = arr[(low + high) // 2]
        while low <= high:
            while arr[low] < pivot:
                low += 1
            while arr[high] > pivot:
                high -= 1
            if low <= high:
                arr[low], arr[high] = arr[high], arr[low]
                low, high = low + 1, high - 1
        return low

    return sort(0, len(arr) - 1)

 

 

• 참고자료

https://www.inflearn.com/course/lecture?courseSlug=%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC&unitId=148379 

학습 페이지

 

https://www.daleseo.com/sort-quick/