ソートを勉強してみる by Go ①

　普段は IT インフラ運用をやっているのですが、ちょっとアルゴリズムを勉強してみることにしました。アプリにもなっている「アルゴリズム図鑑」と、VisuAlgo というページを活用して、コードを実装していきます。

きっかけとしては、昨日 Paiza というプログラミングテストをやってみたときに、A ランクまでは難なく取れたのですが、S ランクでは実行結果のタイムアウトにより、なかなか取得できなかったためです。これは根本的にアルゴリズムの知識不足なのでは？と思い、勉強してみることにしました。

今回は初回ということで、まずソートをやってみました。対象は以下の 4 つです。ザザーッとコードを書いていきます。次回はマージソートとクイックソートをやってみます。

バブルソート

package main

import (
	"fmt"
	"math/rand"
)

func main() {
	// make array of random int
	var list [100]int
	for i := 0; i < len(list); i++ {
		list[i] = (rand.Int() >> 56)
	}

	// bubble sort
	var stack int
	for i := len(list) - 1; i > 0; i-- {
		for j := 0; j < i; j++ {
			if list[j] > list[j+1] {
				stack = list[j]
				list[j] = list[j+1]
				list[j+1] = stack
			}
		}
	}

	for _, v := range list {
		fmt.Println(v)
	}
}

選択ソート

package main

import (
	"fmt"
	"math/rand"
)

func main() {
	// make array of random int
	var list [100]int
	for i := 0; i < len(list); i++ {
		list[i] = (rand.Int() >> 56)
	}

	// select sort
	var stack int
	for i := 0; i < len(list); i++ {
		min := list[i]
		for j := i + 1; j < len(list); j++ {
			if min > list[j] {
				stack = min
				min = list[j]
				list[j] = stack
			}
		}
		if min < list[i] {
			list[i] = min
		}
	}

	for _, v := range list {
		fmt.Println(v)
	}
}

挿入ソート

package main

import (
	"fmt"
	"math/rand"
)

func main() {
	// make array of random int
	var list [100]int
	for i := 0; i < len(list); i++ {
		list[i] = (rand.Int() >> 56)
	}

	// insert sort
	var stack int
	for i := 1; i < len(list); i++ {
		target := list[i]
		for j := i - 1; j >= 0; j-- {
			if target < list[j] {
				stack = list[j]
				list[j] = list[j+1]
				list[j+1] = stack
			}
		}
	}

	for _, v := range list {
		fmt.Println(v)
	}
}

ヒープソート

すいません。コード汚いですね。

package main

import (
	"fmt"
	"math/rand"
)

func main() {
	// ランダムな値をセットした int 配列を作成します。
	length := 20
	list := make([]int, length)
	for i := 0; i < len(list); i++ {
		list[i] = (rand.Int() >> 56) // 値が大きいと見にくいので、56 bit シフト。64 bit 環境です。
	}

	// ヒープ木を作ります。
	var stack int // スタックを作っておきます。
	heap := make([]int, length)
	for i := 0; i < length; i++ {
		heap[i] = list[i]
		if i == 0 {
			continue
		}

		oyaIndex := getOyaIndex(i)
		koIndex := i

		// 挿入時にヒープ木を作り始めます。
		for {
			if heap[oyaIndex] >= heap[koIndex] {
				break
			}

			stack = heap[oyaIndex]
			heap[oyaIndex] = heap[koIndex]
			heap[koIndex] = stack

			if oyaIndex == 0 {
				break
			}

			koIndex = oyaIndex
			oyaIndex = getOyaIndex(koIndex)
		}
	}

	// "list" に、ソート結果を代入します。つまり、再利用します。
	for i := 0; i < length; i++ {
		nowIndex := length - 1 - i
		list[nowIndex] = heap[0] // ヒープの最上位ノードをソート結果用の "list" に代入します。

		// ヒープの値を最上位ノード位置に持っていきます。
		// ノードを最上位ノード位置に持っていく ＝ ノードを 0 にする と考えます。
		heap[0] = heap[nowIndex]
		heap[nowIndex] = 0

		// ヒープを再構築します。
		var oyaIndex int
		for {
			koIndex := getKoIndex(oyaIndex, heap)
			if koIndex == -1 {
				break
			}
			if heap[oyaIndex] >= heap[koIndex] {
				break
			}
			stack = heap[koIndex]
			heap[koIndex] = heap[oyaIndex]
			heap[oyaIndex] = stack
			oyaIndex = koIndex
		}
	}

	for _, v := range list {
		fmt.Println(v)
	}
}

// 子ノードのインデックスから親ノードのインデックスを取得します。
func getOyaIndex(index int) int {
	return ((index + 1) >> 1) - 1
}

// 親ノードのインデックスから子ノードのインデックスを取得します。
// ただし、2つの子の値を比較して、大きい方のインデックスを返します。
func getKoIndex(index int, list []int) int {
	koIndex1 := ((index + 1) << 1) - 1
	koIndex2 := (index + 1) << 1

	if koIndex1 > len(list)-1 {
		return -1
	}

	if koIndex2 > len(list)-1 {
		return koIndex1
	}

	if list[koIndex1] > list[koIndex2] {
		return koIndex1
	}
	return koIndex2
}

以上です。何かの役に立てれば、、
ヒープソートはちょっと汚いので、もう少し工夫できるか考えようと思います。