[알고리즘] 퀵정렬 (분할정복 활용)

특정 리스트를 정렬하는 방법에는 여러 가지가 있다.

그중에서도 대표적으로 분할 정복을 활용하여 리스트를 정렬하는 것이 합병 정렬, 퀵 정렬이다.

 

그 중 퀵정렬에 대해 알아보자

---

퀵 정렬

 

합병 정렬의 combine단계에서는 크기를 비교해가며 새로운 리스트를 생성했다. 즉, 합병 정렬은 combine단계에서 많은 과정을 수행한다. 하지만 퀵 정렬은 이와 다르게 divide에서 많은 과정을 수행한다.

---

퀵 정렬의 과정

 

퀵 정렬은 주로 기준점으로 삼을 임의의 성분을 필요로 한다. 주로 대상 리스트의 제일 마지막 성분을 사용한다. 이를 pivot이라고 부른다. 이 pivot을 기준으로 더 작은 성분은 모두 왼쪽으로, 더 큰 성분은 모두 오른쪽으로 이동한다. (divide) 그리고 왼쪽의 리스트와 오른쪽의 리스트를 각각 또다시 pivot을 기준으로 나눈다. (conquer) 이를 리스트의 길이가 1이 될 때까지 반복한다. (base-case) 그리고 각각의 리스트를 모두 합친다. (combine)

 

합병 정렬은 새로운 리스트를 생성하고 그 리스트에 값을 더해주는 방식으로 combine 했다. 하지만 퀵 정렬은 성분을 기준으로 수행하기 때문에 퀵 정렬의 행심인 divide에서는 그렇게 할 필요가 없다.(오히려 그러지 않는 편이 수월하다.) 

---

퀵 정렬의 divide에 활용되는 partition

 

이 때 활용되는 것이 partition개념이다. 특정 리스트를 인덱스를 활용하여 4가지 부분으로 나눈다. 가장 먼저 제일 뒤의 값은 pivot으로, pivot보다 작은 값들은 small, 더 큰 값들은 big, 아직 검사하지 않은 값들은 unknown으로 나눈다. 이 때 big의 시작점 인덱스을 b로, unknown의 시작점 인덱스를 i로 표기하여 각 값들을 pivot과 비교해나간다. b와 i의 초기값은 0이다.

 

pivot과 비교했을 때 리스트의 i에 해당하는 값이 더 클 경우 그냥 i만 1 늘려준다.

pivot과 비교했을 때 리스트의 i에 해당하는 값이 더 작을 경우 현재의 리스트의 b에 해당하는 값과 현재 i에 해당하는 데이터를 교환하고 b과 i를 1씩 늘려준다.

이를 pivot에 이르기 전까지 수행한다.

최종적으로는 pivot의 값과 b에 대당하는 값의 위치를 교환해준다. (그래야 pivot을 기준으로 왼쪽은 작고 오른쪽은 큰 모양이 되므로)

 

이것이 divide이다. 퀵 정렬의 핵심이자 가장 어려운 부분이다.

---

 난수 열을 대상으로 수행한 퀵 정렬

 

이미지 출처 : 위키백과 ( https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC )

---

퀵 정렬 코드 (by. 파이썬)

 

def quickSort(array):
    if (len(array) <= 1):
        return array
    
    less = []
    pivot = array[0]
    more = []
    for i in range(1,len(array)):
        if array[i] > pivot:
            more.append(array[i])
        else:
            less.append(array[i])
    return quickSort(less) + [pivot] + quickSort(more)

def main():
    line = [int(x) for x in input().split()]

    print(*quickSort(line))

if __name__ == "__main__":
    main()