안녕하세요. 오늘은 퀵정렬에 대해서 살펴보려고 합니다.
퀵 정렬이란 기준점(pivot)을 기준으로 좌우를 나누는 특징을 가지고 있습니다. 이 특징 때문에 파티션 교환 정렬이라고도 불립니다. 개념을 수도코드로 정리하면 다음과 같습니다.
이렇게 정렬할 경우 배열이 n개가 될때까지 반복하고, 한번 반복할 때마다 대상이 반으로 줄어듦으로 O(n log n)의 시간복잡도를 나타냅니다. 피벗이 항상 최소, 최대값일 경우(최악의 경우: 정렬된 배열일때) 시간복잡도는 O(n²)이 되는데 이를 방지하기 위해 피벗을 선택하는 로직을 추가할 수 있습니다.
이것을 코드로 구현하는 방법에는 두가지가 있는데 간단하게 배열을 이용하는 방법과 투포인터 스왑을 이용하여 공간복잡도를 최적화하는 방법을 소개해 드리려 합니다.
먼저 생각하는 수도코드 파이썬과 함께 수도코드를 그대로 코드로 옮겨보겠습니다. 여기서는 피벗을 단순하게 배열의 첫번째 값으로 지정했습니다.
피벗을 기준으로 왼쪽과 오른쪽으로 값을 옮깁니다. 여기서 탈출조건을 주목하면 배열의 길이가 1일때 = 배열이 피벗일 때 = 정렬이 완료된 상황인것을 알 수 있습니다. 마찬가지로 좌/우 배열의 길이가 0일때도 빈배열을 리턴합니다.
하지만 이 코드는 비효율적인 부분이 있습니다. 바로 함수가 호출될때마다 배열을 생산하는 것이죠. 이는 메모리 낭비이기 때문에 별도의 배열을 선언하지 않고 정렬을 구현할수 있습니다. 투 포인터 스왑을 이용해 보겠습니다.
파이썬은 투포인터 스왑을 이용하기에 굉장히 편리한 언어인것 같습니다. 제가 공부하고있는 알고리즘 책에서도 연결 리스트 등 다양한 자료구조를 다룰때 투포인터를 이용하고 있습니다. 투 포인터를 이용한 수도코드를 작성하고 구현해보았습니다.
하지만 이 코드는 에러가 발생합니다! start, end의 인덱스가 범위내에 있는것을 보장할수 없기 때문입니다. 한가지 문제가 더 있습니다. 정확한 기준점의 위치를 보장할수 없습니다. 따라서 기준점의 위치를 확정하면서 배열을 쪼개며 정렬하는 함수를 작성해보겠습니다.
- 총 4개의 포인터를 이용한다. 배열의 시작과 끝을 정하는 start, end, 포인터를 나타내는 left, rigth를 정의한다.
- left는 느린 포인터, right는 빠른 포인터로 활용할 수 있다.
- right가 배열을 순회하면서 피벗보다 작은 값을 left를 기준으로 차곡차곡 쌓고 left와 end를 스왑해서 피벗의 자리를 확정한다.
- 이 정렬이 마치면 피벗 왼쪽에는 피벗보다 작은 값이 들어있게 된다. 따라서 좌측 길이는 달라지지 않고, 피벗의 자리는 확정될수 있는것이다.
- 그리고 확정된 피벗을 제외한 왼쪽 오른쪽 배열을 각각 재귀호출하여 정렬한다.
- 재귀 호출된 배열이 조건을 만족하여 더이상의 정렬이 이루어지지않으면 함수는 종료된다.
이 순서대로 수도코드를 작성해 보겠습니다.
이를 코드로 옮기면 다음과 같습니다.
이와 같이 구현하면 별도의 배열을 선언하지않고 정렬할 수 있습니다. 포인터를 이동시키며 기준점과 비교 후 스왑해 정렬하고 재귀적으로 순환하는 구조를 가지고 있습니다.
