모두의 알고리즘 문제 11. 퀵 정렬

퀵 정렬은 '피벗(pivot)'이라는 기준을 하나 선정하고 피벗보다 큰 리스트, 피벗보다 작은 리스트로 리스트를 나누어 정렬하고 다시 합하는 정렬 방식이다.

 

쉽게 설명한 퀵 정렬 알고리즘은 아래와 같다

 

def quick_sort(a):
    n = len(a)
    if n <= 1:
        return a

    pivot = a[-1]
    g1=[]
    g2=[]

    for i in range(0, n-1):
        if a[i] < pivot:
            g1.append(a[i])
        else:
            g2.append(a[i])
            
    return quick_sort(g1) + [pivot] + quick_sort(g2)

d= [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
print(quick_sort(d))

결과: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

 

위 코드의 ' return quick_sort(g1) + [pivot] + quick_sort(g2)' 부분을 보면 리스트끼리 이어붙일 수 있다는 걸 알 수 있다.

[pivot]이 리스트 취급되고 양옆의 리스트들과 이어졌다.

 

예를 들면, [1, 2] + [3] + [4, 5] ->> [1, 2, 3, 4, 5] 가 된다.

 

그리고 이번 정렬에서도 재귀함수가 쓰였는데 동작 방식은 다음과 같다.

 

 

 

1. 리스트a = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]일 때 피벗은 리스트의 마지막 원소로 정한다고 가정한다.

 

2. 리스트 a는 피벗=5를 기준으로 피벗보다 크고 작은 리스트 두개로 나뉜다. [3, 1, 2, 4], 5, [6, 8, 9, 10, 7]

 

3. [3, 1, 2, 4]는 마지막 원소를 피벗으로 삼는다. 피벗 4를 기준으로 리스트는 [3, 1, 2], 4, [ ] 로 나뉜다.

 

4. [3, 1, 2]는 피벗=2를 기준으로 나뉜다. [1], 2, [3]. 리스트 길이가 1이므로 값은 그대로 리턴된다.

 

5. 리스트[3, 1, 2]는 [1, 2, 3]을 리턴하고, [3, 1, 2, 4]는 리턴 받은 [1, 2, 3]과 피벗=4를 이어붙여 [1, 2, 3, 4]를 리턴한다.

 

6. 리스트[6, 8, 9, 10, 7]도 위와 같은 방식으로 진행되고 마지막에 남는 두개의 리스트와 피벗이 이어져 하나의 정렬된 리스트가 된다.

 

 

 

일반적인 퀵 정렬 알고리즘은 아래와 같다

 

def quick_sort_sub(a, start, end): #입력 리스트a의 어디부터 어디까지가 정렬 대상인지.
    if end-start <=0: #정렬 대상이 없으면 정렬할 필요 없음
        return

    #기준값을 정하고 기준값에 맞춰 리스트 안에서 각 자료의 위치를 맞춤
    #[기준값보다 작은 값들, 기준값, 기준값보다 큰 값들]
    pivot = a[end] #편의상 리스트의 마지막 값을 피벗으로 정함
    i = start

    for j in range(start, end): #피벗을 기준으로 정렬. end-1까지.
        if a[j] <= pivot:  #피벗이 마지막값이라 정렬 가능한 반복문
            a[i], a[j] = a[j], a[i]
            i+=1
	#위의 for문에서 피벗 제외하고 정렬
    #피벗을 가운데로 옮기는 코드
    a[i], a[end] = a[end], a[i] 
   
    #재귀호출
    quick_sort_sub(a, start, i-1) #기준값보다 작은 그룹을 재귀호출로 다시 정렬
    quick_sort_sub(a, i+1, end) #기준값보다 큰 그룹을 재귀호출로 정렬


def quick_sort(a): 
    quick_sort_sub(a, 0, len(a)-1)


d= [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
quick_sort(d)
print(d)

위에서 재귀호출이 어떻게 동작하는지 설명했는데 그것과 똑같이 움직인다.

 

1. 피벗을 기준으로 정렬 후 피벗을 가운데로 둔다.

2. 피벗 좌우의 리스트 각각 정렬시킨다.

3. 좌우의 리스트는 또 각각 리스트를 좌우로 분리시켜 정렬시킨다.

 

이때 이론상 피벗을 기준으로 원소들이 이론과는 다른 순서로 배열되어 나뉘길래 고민해봤는데 딱히 순서는 필요없을 것 같다.

 

예를 들어서 [6, 8, 9, 10, 7] 리스트에서 피벗은 마지막값인 7로 정한다면 리스트는 이론적으로 [6], 7, [8, 9, 10]으로 나뉘어야 하는데 위의 코드를 분석해보면 리스트가 [6], 7, [9, 10, 8]로 나뉘게 된다.

 

처음엔 내가 코드를 잘못읽은줄 알고 계속 반복해서 코드를 분석하고 틀린점을 찾았는데 못찾고 머리만 사매고 있었다. 그런데 생각해보니 굳이 이론과 동일하게 나뉘지 않는다고 결과에서 정렬이 안된게 아니라는걸 생각했다. 

 

어차피 피벗 기준으로 나뉘어서, 원소의 순서가 어찌됐든 결과적으로 전부 정렬되어서 나올텐데 굳이 사소한 순서에 집착해서 머리 싸맬 필요는 없던 것 같다. 

 

그리고 이 책은 초보자를 대상으로 쓰여서 기존의 퀵 정렬과는 차이가 있으니 이번 공부 시간엔 퀵 정렬에 대해 공부하는 걸로 만족하기로 했다. 더 자세히 공부하고 싶으면 다른 교재를 알아봐야지.

 

 

반성할 점이 있다면 아래 코드의

 

-----------------------------------

  for j in range(start, end): #피벗을 기준으로 정렬. end-1까지.
        if a[j] <= pivot:  #피벗이 마지막값이라 정렬 가능한 반복문
            a[i], a[j] = a[j], a[i]
            i+=1
#위의 for문에서 피벗 제외하고 정렬
#피벗을 가운데로 옮기는 코드
    a[i], a[end] = a[end], a[i] 

-----------------------------------

 

'a[i], a[end] = a[end], a[i] ' 이부분이 굳이 필요한가? for문의 range의 end를 end+1로 바꾸면 되는거 아닌가?하고 필요없어 보이는 부분을 지우고 for문을 바꿔봤는데 바로 에러가났다. 자세히 살펴보니 내가 지운 부분은 for문으로 리스트가 정렬된 후 피벗을 리스트 중앙으로, 자신보다 작은 값의 바로 오른쪽으로 옮기는 코드라서 이게 없으면 정렬이 되지 못햇다.

 

 

 

그리고 퀵 정렬에서는 기준값이 몹시 중요하다. 만약 선정된 기준이 가장 큰 값이라면 기준보다 작은 그룹에 모든 자료들이 모여있어서 그룹을 둘로 나눈 의미가 없이 퀵정렬의 효율이 낮아질 것이다. 따라서 퀵 정렬에서는 좋은 기준을 정하는 것이 곧 정렬의 효율성을 가늠하는 것이므로 매우 중요하다.

 

이 책에선 좋은 기준을 정하는 방법은 범위를 넘어서는(책의 대상독자들의 수준을 넘어서는) 어려운 내용이라 담지 않았다고 한다. 그래서 위의 예제 프로그램은 리스트 가장 마지막 값을 기준으로 정했다.

 

 

 

퀵 정렬의 시간복잡도는 최악의 경우, 즉 위에서 말한 것처럼 기준 선정이 잘못된 경우에 삽입 정렬과 같은 O(n^2)이지만, 평균적일 때는 병합 정렬과 같은 O(n*logn)이다.

 

다행히도 좋은 기준 값을 정하는 알고리즘에 관해서는 연구가 많이 되어 있기 때문에 퀵 정렬은 대부분의 경우 O(n^logn)으로 정렬을 마칠 수 있다.