[Algorithm] 퀵 정렬 (Quick Sort)

 

 

 

퀵 정렬 (Quick Sort)

퀵 정렬은 피봇보다 작은 값으로 구성된 배열과 피봇보다 큰 값으로 구성된 배열로 분할해 정렬하는 알고리즘.

 

 

 

작동 방식

• 변수 : low < pivot < high
  • low
    • 배열의 첫 번째 요소에서 시작
    • 피봇보다 작으면 오른쪽으로 한 칸 이동
    • 피봇보다 크면 이동 X
  • high
    • 배열의 마지막 요소에서 시작
    • 피봇보다 크면 왼쪽으로 한 칸 이동
    • 피봇보다 작으면 이동 X
  • low와 high 둘 다 이동하지 않을 때 두 변수가 가리키는 값을 교환

예시

• 배열 [4, 3, 2, 6, 7, 1, 5]가 있을 때 다음과 같은 과정으로 분할한다.
  • 분할은 배열의 크기가 1이하가 될 때까지 반복해서 수행한다.

1.	4	3	2	6	7	1	5
	pivot	low					high
2.	4	3	2	6	7	1	5
	pivot	low					high
3.	4	3	2	6	7	1	5
	pivot		low			high (이동 x)
4.	4	3	2	6	7	1	5
	pivot			low (이동 x)		high
5.	4	3	2	1	7	6	5
	pivot			low		high
6.	4	3	2	1	7	6	5
	pivot			low		high
7.	4	3	2	1	7	6	5
	pivot				low high (엇갈림)
8.	3	2	1	4	7	6	5
				pivot

 

시간 복잡도

• 평균적인 시간 복잡도 : O(nlogn)
• [5,4,3,2,1]일 때, 피봇을 5로 하면 O(n^2)가 될 수도 있다.

 

 

 

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left, right, equal = [], [], []
    for i in arr:
        if i < pivot:
            left.append(i)
        elif i > pivot:
            right.append(i)
        else:
            equal.append(i)
    return quick_sort(left) + equal + quick_sort(right)