バルブソート

サンプルコード

main.go

package main

import (
	"fmt"
)

func sort(nums []int) []int {
	for i := 0; i < len(nums); i++ {
		isSwapped := false
		for j, value := range nums[:len(nums)-i-1] {
			if value > nums[j+1] {
				nums[j] = nums[j+1]
				nums[j+1] = value
				isSwapped = true
			}
			fmt.Println(nums)
		}

		if !isSwapped {
			break
		}
		fmt.Println("-----")
	}
	return nums
}

func main() {

	nums := []int{5, 9, 3, 1, 2, 8, 4, 7, 6}
	fmt.Println(nums)
	fmt.Println("-----BEGIN-----")

	result := sort(nums)

	fmt.Println("----- END -----")
	fmt.Println(result)
}

出力結果

[5 9 3 1 2 8 4 7 6]
-----BEGIN-----
[5 9 3 1 2 8 4 7 6]
[5 3 9 1 2 8 4 7 6]
[5 3 1 9 2 8 4 7 6]
[5 3 1 2 9 8 4 7 6]
[5 3 1 2 8 9 4 7 6]
[5 3 1 2 8 4 9 7 6]
[5 3 1 2 8 4 7 9 6]
[5 3 1 2 8 4 7 6 9]
-----
[3 5 1 2 8 4 7 6 9]
[3 1 5 2 8 4 7 6 9]
[3 1 2 5 8 4 7 6 9]
[3 1 2 5 8 4 7 6 9]
[3 1 2 5 4 8 7 6 9]
[3 1 2 5 4 7 8 6 9]
[3 1 2 5 4 7 6 8 9]
-----
[1 3 2 5 4 7 6 8 9]
[1 2 3 5 4 7 6 8 9]
[1 2 3 5 4 7 6 8 9]
[1 2 3 4 5 7 6 8 9]
[1 2 3 4 5 7 6 8 9]
[1 2 3 4 5 6 7 8 9]
-----
[1 2 3 4 5 6 7 8 9]
[1 2 3 4 5 6 7 8 9]
[1 2 3 4 5 6 7 8 9]
[1 2 3 4 5 6 7 8 9]
[1 2 3 4 5 6 7 8 9]
----- END -----
[1 2 3 4 5 6 7 8 9]

選択ソート

サンプルコード

main.go

package main

import (
	"fmt"
)

func sort(nums []int) []int {
	for i, v1 := range nums {
		minValueIndex := i
		minValue := v1

		for j, v2 := range nums[i:] {
			if minValue > v2 {
				minValueIndex = i + j
				minValue = v2
			}
		}

		nums[i] = minValue
		nums[minValueIndex] = v1

		fmt.Println(nums)
	}

	return nums
}

func main() {

	nums := []int{5, 9, 3, 1, 2, 8, 4, 7, 6}
	fmt.Println(nums)
	fmt.Println("-----BEGIN-----")

	result := sort(nums)

	fmt.Println("----- END -----")
	fmt.Println(result)
}

出力結果

[5 9 3 1 2 8 4 7 6]
-----BEGIN-----
[1 9 3 5 2 8 4 7 6]
[1 2 3 5 9 8 4 7 6]
[1 2 3 5 9 8 4 7 6]
[1 2 3 4 9 8 5 7 6]
[1 2 3 4 5 8 9 7 6]
[1 2 3 4 5 6 9 7 8]
[1 2 3 4 5 6 7 9 8]
[1 2 3 4 5 6 7 8 9]
[1 2 3 4 5 6 7 8 9]
----- END -----
[1 2 3 4 5 6 7 8 9]

挿入ソート

サンプルコード

main.go

package main

import (
	"fmt"
)

func sort(nums []int) []int {
	result := nums[0:1]
	fmt.Println(result, nums[1:])

	for i, value := range nums[1:] {
		for j, sortedValue := range result {
			if value < sortedValue {
				result = append(result[:j], append([]int{value}, result[j:]...)...)
				break
			}

			if j == len(result)-1 {
				result = append(result, value)
				break
			}
		}
		fmt.Println(result, nums[i+2:])
	}

	return result
}

func main() {

	nums := []int{5, 9, 3, 1, 2, 8, 4, 7, 6}
	fmt.Println(nums)
	fmt.Println("-----BEGIN-----")

	result := sort(nums)

	fmt.Println("----- END -----")
	fmt.Println(result)
}

出力結果

[5 9 3 1 2 8 4 7 6]
-----BEGIN-----
[5] [9 3 1 2 8 4 7 6]
[5 9] [3 1 2 8 4 7 6]
[3 5 9] [1 2 8 4 7 6]
[1 3 5 9] [2 8 4 7 6]
[1 2 3 5 9] [8 4 7 6]
[1 2 3 5 8 9] [4 7 6]
[1 2 3 4 5 8 9] [7 6]
[1 2 3 4 5 7 8 9] [6]
[1 2 3 4 5 6 7 8 9] []
----- END -----
[1 2 3 4 5 6 7 8 9]

ヒープソート

ヒープを実装する元気はなかったので、既存のパッケージを使いました。
heap - The Go Programming Language

サンプルコード

main.go

package main

import (
    "container/heap"
	"fmt"
)

// An IntHeap is a min-heap of ints.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func sort(nums []int) []int {
	h := &IntHeap{}
	heap.Init(h)

	for	i:=0; i <len(nums); i++ {
		heap.Push(h, nums[i])
	}

	var result []int
	for h.Len() > 0 {

		value := heap.Pop(h)

		result = append(result, value.(int))
		fmt.Println(result, *h)
	}
	return result
}

func main() {

	nums := []int{5, 9, 3, 1, 2, 8, 4, 7, 6}
	fmt.Println(nums)
	fmt.Println("-----BEGIN-----")

	result := sort(nums)

	fmt.Println("----- END -----")
	fmt.Println(result)
}

出力結果

[5 9 3 1 2 8 4 7 6]
-----BEGIN-----
[1] [2 3 4 6 7 8 5 9]
[1 2] [3 6 4 9 7 8 5]
[1 2 3] [4 6 5 9 7 8]
[1 2 3 4] [5 6 8 9 7]
[1 2 3 4 5] [6 7 8 9]
[1 2 3 4 5 6] [7 9 8]
[1 2 3 4 5 6 7] [8 9]
[1 2 3 4 5 6 7 8] [9]
[1 2 3 4 5 6 7 8 9] []
----- END -----
[1 2 3 4 5 6 7 8 9]

マージソート

サンプルコード

main.go

package main

import (
	"fmt"
)

func sort(nums []int) []int {
	if len(nums) == 1 {
		return nums
	}
	halfIndex := len(nums) / 2
	leftNums := sortMerge(nums[:halfIndex])
	rightNums := sortMerge(nums[halfIndex:])
	leftIndex := 0
	rightIndex := 0
	var result []int
	for i := 0; i < len(leftNums)+len(rightNums); i++ {
		if len(rightNums) <= rightIndex || (len(leftNums) > leftIndex && leftNums[leftIndex] <= rightNums[rightIndex]) {
			result = append(result, leftNums[leftIndex])
			leftIndex++
		} else {
			result = append(result, rightNums[rightIndex])
			rightIndex++
		}
	}
	fmt.Println(leftNums, rightNums)
	fmt.Println(result)
	fmt.Println("-----")
	return result
}

func main() {

	nums := []int{5, 9, 3, 1, 2, 8, 4, 7, 6}
	fmt.Println(nums)
	fmt.Println("-----BEGIN-----")

	result := sort(nums)

	fmt.Println("----- END -----")
	fmt.Println(result)
}

出力結果

[5 9 3 1 2 8 4 7 6]
-----BEGIN-----
[5] [9]
[5 9]
-----
[3] [1]
[1 3]
-----
[5 9] [1 3]
[1 3 5 9]
-----
[2] [8]
[2 8]
-----
[7] [6]
[6 7]
-----
[4] [6 7]
[4 6 7]
-----
[2 8] [4 6 7]

クイックソート

サンプルコード

main.go

package main

import (
	"fmt"
	"math/rand"
	"time"
)

func sort(nums []int) []int {

	if len(nums) == 1 {
		return nums
	}

	rand.Seed(time.Now().Unix())
	index := rand.Intn(len(nums))

	var smallerNums []int
	var largerNums []int

	baseValue := nums[index]

	for i := 0; i < len(nums); i++ {
		if i == index {
			continue
		}

		value := nums[i]
		if baseValue <= value {
			largerNums = append(largerNums, value)
		} else {
			smallerNums = append(smallerNums, value)
		}
	}

	var result []int

	if len(smallerNums) > 0 {
		result = sortQuick(smallerNums)
	}
	result = append(result, baseValue)
	if len(largerNums) > 0 {
		result = append(result, sortQuick(largerNums)...)
	}

	fmt.Println(smallerNums, baseValue, largerNums)

	return result
}

func main() {

	nums := []int{5, 9, 3, 1, 2, 8, 4, 7, 6}
	fmt.Println(nums)
	fmt.Println("-----BEGIN-----")

	result := sort(nums)

	fmt.Println("----- END -----")
	fmt.Println(result)
}

出力結果

[5 9 3 1 2 8 4 7 6]
-----BEGIN-----
[1] 2 [3]
[3 1 2] 4 [5]
[] 8 [9]
[] 7 [9 8]
[5 3 1 2 4] 6 [9 8 7]
----- END -----
[1 2 3 4 5 6 7 8 9]