Quick Sort - 퀵 정렬

가장 효율적인 정렬이라고 합니다.

https://en.wikipedia.org/wiki/Quicksort

Quicksort - Wikipedia

배열에서 기준이되는 피벗을 잡고 피벗보다 작은것을 왼쪽에 큰것을 오른쪽에 넣으면서 제귀호출합니다.

제귀호출로 입력되는 배열의 길이가 1보다 같거나 작을때까지 계속됩니다.

 

Go로 구현한 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
package main
import "fmt"
import "math/rand"
func quickSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    median := arr[rand.Intn(len(arr))]
    lowPart := make([]int, 0, len(arr))
    highPart := make([]int, 0, len(arr))
    middlePart := make([]int, 0, len(arr))
    for _, item := range arr {
        switch {
        case item < median:
            lowPart = append(lowPart, item)
        case item == median:
            middlePart = append(middlePart, item)
        case item > median:
            highPart = append(highPart, item)
        }
    }
    lowPart = quickSort(lowPart)
    highPart = quickSort(highPart)
    lowPart = append(lowPart, middlePart...)
    lowPart = append(lowPart, highPart...)
    return lowPart
}
func main() {
    arr := []int{9, 1, 2, 8, 6, 7, 5, 3, 0, 4}
    fmt.Println("Initial array is:", arr)
    fmt.Println("")
    fmt.Println("Sorted array is: ", quickSort(arr))
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

각 코드에 대한 설명을 주석으로 달았습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package main
import "fmt"
import "math/rand"
func quickSort(arr []int) []int {
    // quickSort 함수는 재귀호출 함수이기 때문에 탈출 구분이 필요합니다.
    // 입력값으로 받은 배일의 길이가 1보다 작을때까지 재귀호출 됩니다.
    if len(arr) <= 1 {
        return arr
    }
    // median(중간값)이라는 배열 변수를 만듭니다.
    // 전체 배열의 길이 이내의 정수 랜덤값을 받아옵니다.
    // median은 임의의 피벗값이 됩니다.
    median := arr[rand.Intn(len(arr))]
    // lowPart, middlePart, highPhar라는 빈 정수 배열(slice)을 만듭니다.
    // 각 배열은 arr 배열의 길이만큼 값을 가질 수 있습니다.
    lowPart := make([]int, 0, len(arr))
    highPart := make([]int, 0, len(arr))
    middlePart := make([]int, 0, len(arr))
    // arr 배열을 대상으로 Loop를 돌립니다.
    for _, item := range arr {
        switch {
        // 피벗으로 잡은 기준값을 기준으로 작으면 lowPart slice에 넣습니다.
        case item < median:
            lowPart = append(lowPart, item)
        // 피벗으로 잡은 기준값을 기준으로 같으면 middlePart slice에 넣습니다.
        case item == median:
            middlePart = append(middlePart, item)
        // 피벗으로 잡은 기준값을 기준으로 크면 highPart slice에 넣습니다.
        case item > median:
            highPart = append(highPart, item)
        }
    }
    // 제귀호출을 하면서 quickSort()의 입력값으로 받는 배열의 길이가 1보다 작거나 같을때 까지 수행합니다.
    lowPart = quickSort(lowPart)
    highPart = quickSort(highPart)
    // 제귀호출이 끝나고 lowPart 배열에 순차적으로 추가합니다.
    lowPart = append(lowPart, middlePart...)
    lowPart = append(lowPart, highPart...)
    return lowPart
}
func main() {
    arr := []int{9, 1, 2, 8, 6, 7, 5, 3, 0, 4}
    fmt.Println("Initial array is:", arr)
    fmt.Println("")
    fmt.Println("Sorted array is: ", quickSort(arr))
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

검색해보니 아래와 같은 형태의 Quick Sort도 확인할 수 있습니다.

제귀호출 할 때 make()로 새로운 slice를 만들지 않고 for loop를 돌려 피벗을 기준으로 위치를 변경합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package main
import "fmt"
import "math/rand"
func quickSort(a []int) []int {
    if len(a) < 2 {
        return a
    }
    left, right := 0, len(a)-1
    pivot := rand.Int() % len(a)
    a[pivot], a[right] = a[right], a[pivot]
    for i, _ := range a {
        if a[i] < a[right] {
            a[left], a[i] = a[i], a[left]
            left++
        }
    }
    a[left], a[right] = a[right], a[left]
    quickSort(a[:left])
    quickSort(a[left+1:])
    return a
}
func main() {
    arr := []int{9, 1, 2, 8, 6, 7, 5, 3, 0, 4}
    fmt.Println("Initial array is:", arr)
    fmt.Println("")
    fmt.Println("Sorted array is: ", quickSort(arr))
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX