티스토리 뷰
퀵정렬(Quick Sort)는 평균적으로 좋은 성능을 가져 현장에서 가장 많이 쓰이는 정렬 알고리즘이다. 최악의 경우(Worst-Case) Θ(n^2)의 시간복잡도를 가져 Θ(nlogn)의 시간복잡도를 가지는 병합정렬, 힙정렬보다 성능이 안좋아보일 수 있으나 평균적인 성능은 어떤 정렬에도 뒤떨어지지 않는다.
퀵정렬(Quick Sort)는 배열의 한 원소를 기준(피봇, pivot)으로 삼아 피봇보다 작은 수들은 피봇의 앞으로, 피봇보다 큰 수들은 피봇의 뒤로 보낸다. 정렬되지 않은 피봇의 좌우는 재귀적으로 문제를 해결하여 배열 전체가 정렬이 되도록 한다. 예를 들어 설명하면 다음과 같다.
이 예는 배열의 젤 뒷원소를 피봇으로 삼아 퀵정렬(Quick Sort)를 수행하는 경우이다. 피봇인 15보다 작은 수들은 앞으로 보내고 15보다 큰 수들은 뒤로 보낸다(a). 이렇게 한번 수행이되면 피봇의 좌우는 다시 재귀적으로 진행이 되는데 배열의 원소가 2개일 경우부터 정렬이 시작되어 자신을 호출한 함수로 올라가면서 하나씩 정렬이 되어가 모든 배열의 정렬이 완료된다(b).
퀵정렬(Quick Sort)의 슈도코드는 다음과 같다.
quickSort() 함수 내의 partition() 함수에서 배열의 끝인 A[r]을 피봇으로 삼아 양쪽으로 재배치하고 A[r]이 자리한 위치를 return 한다. 그리고 return 한 위치를 기준으로 좌우로 재귀함수를 호출한다.
기준원소를 중심으로 분할하는 방법에는 여러가지가 있다. 예의 그림처럼 배열의 젤 뒷원소를 피봇으로 삼을 수도 있고, 배열의 가운데를 피봇으로 삼을 수 있다. 특별히 비효율적이지만 않으면 원하는 대로 작성해도 상관이 없다.
다음은 partition() 함수를 좀더 구체적으로 기술한 슈도코드이다.
Partition() 의 코드를 살펴보면 배열의 끝을 x(피봇)에 저장하고 배열의 시작부분인 p에서 -1하여 i 에 저장한다. i는 피봇보다 작거나 같은 원소들의 제일 끝을 나타내기 위한 변수이다. j는 p부터 시작하여 피봇 앞인 r-1까지 이동하는데 피봇보다 작은지 큰지 확인을 안한 원소들의 시작점을 나타내게 된다. 이를 그림으로 나타내면 다음과 같다.
partition() 의 코드 일부분은 살펴보면
j 가 처음부터 피봇전까지 탐색하면서 A[j]가 피봇보다 큰 경우 그냥 아무런 작업을 하지않고 다음 원소로 옮겨간다. A[j]가 피봇보다 작은 경우 피봇보다 작은 원소들의 끝을 나타내는 i을 한칸 뒤로 옮기고 A[i]와 A[j]의 위치를 바꾸어준다. 이렇게 되면 i가 가르키는 원소들 앞에는 피봇보다 작은 원소들이 그 뒤에는 피봇보다 큰 수들이 위치하게 된다.
다음은 partition() 함수의 예를 구체적으로 나타낸다.
퀵정렬(Quick Sort)의 최악의 경우(Worst Case)는 항상 한쪽은 0개, 다른 쪽은 n-1개로 분할되는 경우이다. 이는 잘 일어나지 않을 것 같지만 현장에서 다른 서버의 데이터베이스에 있던 데이터들을 받아 사용하는 경우가 많은데 그 데이터들이 이미 그 서버에 의해 정렬이 완료된 경우가 대부분이다. 퀵정렬의 최악의 경우를 살펴보면 다음과 같다.
최선의 경우는 항상 절반으로 분할되는 경우인데 그 경우에는
T(n) = 2T(n/2) + θ(n) = θ(nlogn)
의 시간복잡도를 가진다.
퀵정렬의 평균시간복잡도는 다음과 같다.
