Cocktail Sort - 칵테일 정렬

칵테일 쉐이커 정렬 또는 양방향 버블 정렬이라고도 합니다.

버블 정렬에서는 오름차순일 경우 큰값을 찾아 오늘쪽 자리부터 채워나가게 됩니다.

이걸 양쪽으로 오가며 큰 값과 작은 값을 배열의 끝에서부터 채워오는 정렬입니다.

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

Cocktail shaker sort - Wikipedia

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
package main
import "fmt"
func main() {
    arr := [10]int{9, 1, 2, 8, 6, 7, 5, 3, 0, 4}
    fmt.Println("Initial array is:", arr)
    fmt.Println("")
    for i := 0; i < len(arr)/2; i++ {
        left := 0
        right := len(arr) - 1
        for left <= right {
            if arr[left] > arr[left+1] {
                arr[left], arr[left+1] = arr[left+1], arr[left]
            }
            left++
            if arr[right-1] > arr[right] {
                arr[right-1], arr[right] = arr[right], arr[right-1]
            }
            right--
        }
    }
    fmt.Println("Sorted array is: ", 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
package main
import "fmt"
func main() {
    arr := [10]int{9, 1, 2, 8, 6, 7, 5, 3, 0, 4}
    fmt.Println("Initial array is:", arr)
    fmt.Println("")
    // 양방향으로 큰 값과 작은 값을 비교하므로 배열 자릿수의 절반만 Loop를 돕니다.
    for i := 0; i < len(arr)/2; i++ {
        // left는 배열 왼쪽 첫번째 자리입니다.
        left := 0
        // right는 배열의 오른쪽 첫번째 자리입니다.
        right := len(arr) - 1
        // 검색할 범위를 줄이면서 Loop를 돌립니다.
        for left <= right {
            // 배열의 왼쪽 자리를 비교합니다.
            // "left > left + 1"일 경우 왼쪽부터 작은수를 왼쪽으로 자리를 이동시키면서 정렬해 나갑니다.
            if arr[left] > arr[left+1] {
                // 왼쪽 자리의 값이 그 오른쪽보다 클 경우 자리를 변경합니다.
                arr[left], arr[left+1] = arr[left+1], arr[left]
            }
            // 배열의 왼쪽 끝에서부터 하나씩 올라갑니다.
            left++
            // 배열의 오른쪽 자리를 비교합니다.
            // "right-1 > right"일 경우 오른쪽부터 큰수를 오르쪽으로 자리를 이동시키면서 정렬해 나갑니다.
            if arr[right-1] > arr[right] {
                // 오른쪽 자리의 값이 그 왼쪽보타 클 경우 자리를 변경합니다.
                arr[right-1], arr[right] = arr[right], arr[right-1]
            }
            // 배열의 오른쪽 끝애서부터 하나씩 내려갑니다.
            right--
        }
    }
    fmt.Println("Sorted array is: ", arr)
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

위 코드는 배열을 반으로 나누고 왼쪽은 오름차순 버블 정렬인데 왼쪽부터 맞추고, 오른쪽은 내림차순 버블 정렬인데 오른쪽에서부터 맞춰옵니다. 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
package main
 
import "fmt"
 
func main() {
    list := []int{91,28,73,46,55,64,37,82,19}
    fmt.Println("before:", list)
    cocktailSort(list)
    fmt.Println("after: ", list)
}
 
func cocktailSort(list []int) {
    last := len(list) - 1
    for {
        swapped := false
        for i := 0; i < last; i++ {
            if list[i] > list[i+1] {
                list[i], list[i+1] = list[i+1], list[i]
                swapped = true
            }
        }
        if !swapped {
            return
        }
        swapped = false
        for i := last - 1; i >= 0; i-- {
            if list[i] > list[i+1] {
                list[i], list[i+1] = list[i+1], list[i]
                swapped = true
            }
        }
        if !swapped {
            return
        }
    }
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

아무래도 반으로 나눠서 하는것이 더 효율적일 것 같습니다.