Cocktail Sort - 칵테일 정렬

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

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

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

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

Cocktail shaker sort - Wikipedia

Go로 구현한 코드입니다.

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)
}

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

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)
}

위 코드는 배열을 반으로 나누고 왼쪽은 오름차순 버블 정렬인데 왼쪽부터 맞추고, 오른쪽은 내림차순 버블 정렬인데 오른쪽에서부터 맞춰옵니다. Loop 한 번 돌때마다 양쪽을 맞춰 옵니다.

아래 코드는 배열 전체를 대상으로 한번은 오른차순, 한번은 내림차순으로 진행합니다.

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
        }
    }
}

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