퀵 정렬이란, 이름에서 알 수 있듯이 정렬이 빠른 알고리즘이다.
특징
- 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘
- 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속함
- 원소들 중에 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있어 불안정 정렬에 속함
알고리즘
과정
퀵 정렬은 분할 정복 알고리즘 방법을 통하여 리스트를 정렬
- 리스트 목록 중에서 하나의 원소를 고르는데, 이때 고른 원소를
피벗(pivot)이라고 부름- 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오게됨
- 이후 피벗을 기준으로 리스트를 둘로 나누는데, 이때 리스트를 둘로 나누는 것을 분할이라고 하며 분할을 마친 뒤에 피벗은 더 이상 움직이지 않음
- 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복
- 재귀 호출이 한 번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지기 때문에 반드시 끝나는 것을 보장
설명
퀵 정렬에서 쓰이는 용어는 피벗, left, right, low, high가 있다.
left : 정렬 대상의 가장 왼쪽 지점을 가리키는 이름
right : 정렬 대상의 가장 오른쪽 지점을 가리키는 이름
pivot : 피벗이라 발음하고 중심점, 중심축의 의미를 담고 있다.
low : 피벗을 제외한 가장 왼쪽에 위치한 지점을 가리키는 이름
high : 피벗을 제외한 가장 오른쪽에 위치한 지점을 가리키는 이름
배열에 5 - 3 - 8 - 4 - 9 - 1 - 6 - 2 - 7 순서로 저장되어 있다고 가정
위 배열에서 low는 5, high는 7이 됨
그 다음 피봇을 지정해야 하는데 피벗은 배열에서 가장 왼쪽 값이 될 수 있고 가장 오른쪽 값이 될 수도 있고, 중간 값이 될 수도 있음
만일 5를 피벗으로 지정했다면 pivot은 5, left는 3, right는 7이 됨
만일 7을 피벗으로 지정했다면 pivot은 7, left는 5, right는 2가 됨
다음 설명을 위해서 pivot은 p, low는 i, high는 j로 가정
Pivot을 가장 왼쪽 값으로 지정했을 때의 과정
1단계 : 초기화
처음에 p을 5로 지정을 한 경우
5 - 3 - 8 - 4 - 9 - 1 - 6 - 2 - 7
p i j2단계 : low와 high 이동
그 다음 과정에서 서로 교환할 값을 찾기 위해 i가 움직인 후 그 다음 j가 움직이게 됨
i는 피벗보다 작은 값을 만날 때까지 오른쪽으로 이동
j는 피벗보다 큰 값을 만날 때까지 왼쪽으로 이동
먼저 i가 이동을 하여 p보다 큰 값인 8에서 멈춤
5 - 3 - 8 - 4 - 9 - 1 - 6 - 2 - 7
p i j이후 j가 이동을 하여 p보다 작은 값인 2에서 멈춤
5 - 3 - 8 - 4 - 9 - 1 - 6 - 2 - 7
p i j 3단계 : low와 high의 교환
i와 j가 둘 다 조건에 맞는 값을 찾아 멈추게 되어 i의 값과 j의 값을 교환
5 - 3 - 2 - 4 - 9 - 1 - 6 - 8 - 7
p i j 2~3 단계를 반복하다 보면 i와 j가 교차되는 경우가 발생
5 - 3 - 2 - 4 - 1 - 9 - 6 - 8 - 7
p j i i와 j가 교차되면 교환 종료
4단계 : 피벗의 이동
i와 j가 교차되면, p와 j의 값을 교환
1 - 3 - 2 - 4 - 5 - 9 - 6 - 8 - 7
j i 5단계 : 분할(partition)
p와 j의 값을 교환했다면 j를 기준으로 j보다 값이 작은 영역, j보다 값이 큰 영역 두 영역으로 나뉘게 됨
여기서는 5를 기준으로 하여 왼쪽 영역, 오른쪽 영역 각각에 다시 p와 left, right 등이 지정됨
1 - 3 - 2 - 4 5 9 - 6 - 8 - 7
p i j p i j왼쪽 영역에서는 1이 p이자 left, 4가 right가 되며, i는 3, j는 4로 지정됨
오른쪽 영역에서는 9가 p이자 left, 7이 right가 되며, i는 6, j는 7로 지정됨
Pivot을 가장 오른쪽 값으로 지정했을 때의 과정
1단계 : 초기화
처음에 p을 7로 지정을 한 경우
5 - 3 - 8 - 4 - 9 - 1 - 6 - 2 - 7
i j p2단계 : low와 high 이동
그 다음 과정에서 서로 교환할 값을 찾기 위해 i가 움직인 후 그 다음 j가 움직이게 됨
i는 피벗보다 큰 값을 만날 때까지 오른쪽으로 이동
j는 피벗보다 작은 값을 만날 때까지 왼쪽으로 이동
먼저 i가 이동을 하여 p보다 큰 값인 8에서 멈춤
5 - 3 - 8 - 4 - 9 - 1 - 6 - 2 - 7
i j p이후 j가 이동을 하여 p보다 작은 값인 2에서 멈춤
5 - 3 - 8 - 4 - 9 - 1 - 6 - 2 - 7
i j p3단계 : low와 high의 교환
i와 j가 둘 다 조건에 맞는 값을 찾아 멈추게 되어 i의 값과 j의 값을 교환
5 - 3 - 2 - 4 - 9 - 1 - 6 - 8 - 7
i j p2~3 단계를 반복하다 보면 i와 j가 교차되는 경우가 발생
5 - 3 - 2 - 4 - 1 - 9 - 6 - 8 - 7
j i pi와 j가 교차되면 교환 종료
4단계 : 피벗의 이동
i와 j가 교차되면, p와 i의 값을 교환
5 - 3 - 2 - 4 - 1 - 7 - 6 - 8 - 9
j i 5단계 : 분할(partition)
p와 i의 값을 교환했다면 i를 기준으로 i보다 값이 작은 영역, i보다 값이 큰 영역 두 영역으로 나뉘게 됨
여기서는 7를 기준으로 하여 왼쪽 영역, 오른쪽 영역 각각에 다시 p와 left, right 등이 지정됨
5 - 3 - 2 - 4 - 1 7 6 - 8 - 9
i j p i j p왼쪽 영역에서는 5가 p이자 left, 1이 right가 되며, i는 3, j는 1로 지정됨
오른쪽 영역에서는 6이 p이자 left, 9이 right가 되며, i는 8, j는 9로 지정됨
Pivot을 중간 값으로 지정했을 때의 과정
1단계 : 초기화
처음에 p을 9로 지정을 한 경우
5 - 3 - 8 - 4 - 9 - 1 - 6 - 2 - 7
i p j2단계 : low와 high 이동
그 다음 과정에서 서로 교환할 값을 찾기 위해 i가 움직인 후 그 다음 j가 움직이게 됨
i는 피벗보다 크거나 같은 값을 만날 때까지 오른쪽으로 이동
j는 피벗보다 작거나 같은 값을 만날 때까지 왼쪽으로 이동
먼저 i가 이동을 하여 p보다 크거나 같은 9에서 멈춤
5 - 3 - 8 - 4 - 9 - 1 - 6 - 2 - 7
p
i j이후 j가 이동을 하여 p보다 작거나 같은 7에서 멈춤
5 - 3 - 8 - 4 - 9 - 1 - 6 - 2 - 7
p
i j3단계 : low와 high의 교환
i와 j가 둘 다 조건에 맞는 값을 찾아 멈추게 되어 i의 값과 j의 값을 교환
5 - 3 - 8 - 4 - 7 - 1 - 6 - 2 - 9
p
i j2~3 단계를 반복하다 보면 i와 j가 교차되는 경우가 발생
5 - 3 - 8 - 4 - 7 - 1 - 6 - 2 - 9
p
j ii와 j가 교차되면 교환 종료
4단계 : 분할(partition)
i와 j가 교차되면, j를 기준으로 왼쪽과 오른쪽으로 나뉘게 됨
여기서는 4를 기준으로 하여 왼쪽 영역, 오른쪽 영역 각각에 다시 p와 left, right 등이 지정됨
5 - 3 - 8 - 4 - 7 - 1 - 6 - 2 9
p
i j 왼쪽 영역은 4가 p가 되고 left와 i는 5, right와 j는 2가 됨
오른쪽 영역은 9 하나만 존재하므로 9의 위치 고정
왼쪽, 오른쪽, 중간으로 나누어 진행을 하여 두 영역으로 나뉘었다면 그 과정을 계속 반복하면서 끝까지 수행하게 됨
장단점
장점
- 속도가 빠름단점
- 정렬된 리스트에 대해서는 오히려 더 수행시간이 많이 걸림
복잡도
시간복잡도
- 두 그룹으로 분할하는데 n의 시간이 걸리고 분할된 단계가 long(n) 개 존재하므로 평균 정렬 속도는 O(nlog2n)
- 분할한 결과가 한쪽으로 몰리는 최악의 경우에는 O(n2)공간복잡도
- O(n)
예제코드
pivot을 왼쪽으로 설정한 경우
import java.util.*
fun quickSort(arr: IntArray, left: Int = 0, right: Int = arr.size - 1) {
if(left >= right) return
val pivot = partition(arr, left, right)
quickSort(arr, left, pivot - 1)
quickSort(arr, pivot + 1, right)
}
fun partition(arr: IntArray, left: Int, right: Int): Int {
var low = left + 1
var high = right
val pivot = arr[left]
while (low <= high) {
while (arr[low] <= pivot && low < high) low++
while (arr[high] > pivot && low <= high) high--
if(low < high)
swap(arr, low, high)
else
break
}
swap(arr, left, high)
return high
}
fun swap(arr: IntArray, i: Int, j: Int) {
var temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
fun main() {
var arr = intArrayOf(5, 3, 8, 4, 9, 1, 6, 2, 7)
quickSort(arr)
print(Arrays.toString(arr))
}pivot을 오른쪽으로 설정한 경우
import java.util.*
fun quickSort(arr: IntArray, left: Int = 0, right: Int = arr.size - 1) {
if(left >= right) return
val pivot = partition(arr, left, right)
quickSort(arr, left, pivot - 1)
quickSort(arr, pivot + 1, right)
}
fun partition(arr: IntArray, left: Int, right: Int): Int {
var low = left
var high = right - 1
val pivot = arr[right]
while (low <= high) {
while (arr[low] < pivot && low <= high) low++
while (arr[high] >= pivot && low < high) high--
if(low < high)
swap(arr, low, high)
else
break
}
swap(arr, low, right)
return low
}
fun swap(arr: IntArray, i: Int, j: Int) {
var temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
fun main() {
var arr = intArrayOf(5, 3, 8, 4, 9, 1, 6, 2, 7)
quickSort(arr)
print(Arrays.toString(arr))
}pivot을 중간으로 설정한 경우
import java.util.*
fun quickSort(arr: IntArray, left: Int = 0, right: Int = arr.size - 1) {
if(left >= right) return
val pivot = partition(arr, left, right)
quickSort(arr, left, pivot - 1)
quickSort(arr, pivot + 1, right)
}
fun partition(arr: IntArray, left: Int, right: Int): Int {
var low = left
var high = right
val pivot = arr[(left + right) / 2]
while (low <= high) {
while (arr[low] < pivot && low < high) low++
while (arr[high] > pivot && low < high) high--
if(low < high)
swap(arr, low, high)
else
break
}
return high
}
fun swap(arr: IntArray, i: Int, j: Int) {
var temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
fun main() {
var arr = intArrayOf(5, 3, 8, 4, 9, 1, 6, 2, 7)
quickSort(arr)
print(Arrays.toString(arr))
}Reference
