ソートを勉強してみる 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
}

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