퀵 정렬 (Quick Sort)

퀵 정렬은 분할 정복 알고리즘의 하나이다. 평균적으로 다른 정렬에 수행 속도가 빠른편이다.

분할정복 알고리즘은 문제를 2개로 분리하고 각각 해결한 후 그 해결 결과값을 모아서 원래의 문제를 해결하는 방식이다.

 

퀵 정렬의 과정은 다음과 같다.

1. 리스트에서 임의의 원소를 고른다. 이 원소를 pivot이라 칭한다.
2. pivot을 기준으로 좌측은 pivot보다 작은 수, 우측은 pivot 보다 큰 수가 오도록 서로 교환한다.
3. 분할된 두 개의 리스트에 대해 재귀적으로 반복한다.

'5,2,4,6,7,1,3' 를 퀵정렬 했을때

 

가장 좌측 5를 pivot으로 설정하고, 2을 left, 3을 right로 설정

left는 => 방향으로 이동하며 pivot보다 큰값 찾기, right는 <= 방향으로 이동하며 pivot보다 작은 값찾기

5(pivot)

2(left)

4

6

7

1

3(right)

pivot보다 큰값 6발견 right값과 교환

5

2

4

3(left)

7

1

6(right)

pivot보다 큰값 7 발견 right 값과 교환

5

2

4

3

6(left)

1

7(right)

pivot 보다 작은값 1 발견 left 값과 교환

5

2

4

3

1(left)

6(right)

7

left right index가 겹칠때 pivot 교환

1(pivot)

2

4

3

5(fix)

6

7

fix 기준으로 좌, 우 다시 나눠서 퀵 정렬 진행 후 완료 값 합치기

1

2

3

4

5

6

7

from random import randint

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

arr = [randint(1,50) for i in range(8)]
print(quick_sort(arr))