퀵소트(quick sort)는 데이터를 순서를 구분할 수 있는 두 개의 영역으로 나누는 작업(partition)을 반복하여 정렬하는 알고리즘이다. 퀵소트의 핵심인 partition의 여러 가지 구현 방식 중, 별도의 메모리 할당 없이 partition을 수행하는 것을 소개한다.
데이터의 영역을 1) 보다 작은 값이 모여 있는 영역, 2) 보다 큰 값이 모여 있는 영역, 3) 구분되지 않은 값이 모여 있는 영역으로 나누고, 구분되지 않는 영역의 길이가 0이 될 때까지 아래의 단계를 반복한다 (처음 시작할 때는 보다 작은 값들의 영역과 보다 큰 값들의 영역의 길이는 각각 0, 0이고, partition이 끝난 후에는 구분되지 않은 값들의 영역의 길이가 0이다).
데이터의 영역을 1) 보다 작은 값이 모여 있는 영역, 2) 보다 큰 값이 모여 있는 영역, 3) 구분되지 않은 값이 모여 있는 영역으로 나누고, 구분되지 않는 영역의 길이가 0이 될 때까지 아래의 단계를 반복한다 (처음 시작할 때는 보다 작은 값들의 영역과 보다 큰 값들의 영역의 길이는 각각 0, 0이고, partition이 끝난 후에는 구분되지 않은 값들의 영역의 길이가 0이다).
- 구분되지 않은 영역의 첫번째 값이 기준값보다 크거나 같은 경우, 해당 값을 보다 큰 값의 영역으로 변경
- 구분되지 않은 영역의 첫번째 값이 기준값보다 작은 경우, 보다 큰 값이 모여 있는 영역의 첫번째 값과 구분되지 않는 영역의 첫번째 값을 서로 바꿔, 해당 값을 보다 작은 값의 영역으로 변경
+-----------------------+----------------------+-------------------------------+
| 보다 작은 값들 | 보다 큰 값들 | 구분되지 않은 값들 |
+-----------------------+----------------------+-------------------------------+
기준값을 정하는 것이 정렬 성능에 영향을 주게 되는데, 아래의 구현에서는 데이터의 가장 마지막 값을 기준값으로 사용한다.
======================================================
package main
import "fmt"
func QuickSort(data []int) {
size := len(data)
QuickSortUtil(data, 0, size - 1)
}
func QuickSortUtil(data []int, from int, to int) {
if from >= to {
return
}
pivot := Partition(data, from, to)
QuickSortUtil(data, from, pivot - 1)
QuickSortUtil(data, pivot + 1, to)
}
func Partition(data []int, from int, to int) int {
refVal := data[to]
untouched, lastSmall := from, from - 1
for ; untouched < to; untouched++ {
if data[untouched] < refVal {
lastSmall++;
data[lastSmall], data[untouched] = data[untouched], data[lastSmall]
}
}
lastSmall++
data[lastSmall], data[to] = data[to], data[lastSmall]
return lastSmall
}
func main() {
dataSet := make([][]int, 6)
dataSet[0] = []int{4, 3, 2, 6, 5, 7, 1}
dataSet[1] = []int{1, 2, 3, 4, 5, 6, 7}
dataSet[2] = []int{7, 6, 5, 4, 3, 2, 1}
dataSet[3] = []int{1, 1, 1, 1, 1, 1, 1}
dataSet[4] = []int{1}
dataSet[5] = []int{}
for _, data := range dataSet {
QuickSort(data)
for _, elem := range data {
fmt.Printf("%d ", elem)
}
fmt.Println()
}
}
