アルゴリズム体操 (Go)

以前、Java でアルゴリズムの復習としてこんなのを書いた。

kntmr.hatenablog.com

今回はこれを Go でやってみる。

バブルソート

要素の入れ替えのところが Go っぽい。それ以外は Java のコードとほぼ同じ。

func bubbleSort(nums []int) {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] > nums[j] {
                nums[i], nums[j] = nums[j], nums[i]
            }
        }
    }
}

クイックソート

ほぼ Java のコードのままだけど、違うのは Go には while がないくらい？

func quickSort(nums []int, left, right int) {
    index := partition(nums, left, right)
    if left < index-1 {
        quickSort(nums, left, index-1)
    }
    if index < right {
        quickSort(nums, index, right)
    }
}

func partition(nums []int, left, right int) int {
    pivot := nums[(left+right)/2]
    for left <= right {
        for nums[left] < pivot {
            left++
        }
        for nums[right] > pivot {
            right--
        }
        if left <= right {
            nums[left], nums[right] = nums[right], nums[left]
            left++
            right--
        }
    }
    return left
}

(追記: ChatGPT 先生と一緒に改良しました)

func quickSort(nums []int, left, right int) {
    if left >= right {
        return
    }
    pivot := nums[(left+right)/2]
    i, j := left, right
    for i <= j {
        for nums[i] < pivot {
            i++
        }
        for nums[j] > pivot {
            j--
        }
        if i <= j {
            nums[i], nums[j] = nums[j], nums[i]
            i++
            j--
        }
    }
    quickSort(nums, left, j)
    quickSort(nums, i, right)
}

マージソート

ひとまず、Java のコードを Go に書き直しただけ。

func mergeSort(nums, temp []int, left, right int) {
    if left >= right {
        return
    }
    mid := (left + right) / 2
    mergeSort(nums, temp, left, mid)
    mergeSort(nums, temp, mid+1, right)
    merge(nums, temp, left, right, mid)
}

func merge(nums, temp []int, left, right, mid int) {
    for i := left; i <= right; i++ {
        temp[i] = nums[i]
    }
    index, currentLeft, currentRight := left, left, mid+1
    for currentLeft <= mid && currentRight <= right {
        if temp[currentLeft] <= temp[currentRight] {
            nums[index] = temp[currentLeft]
            currentLeft++
        } else {
            nums[index] = temp[currentRight]
            currentRight++
        }
        index++
    }
    for currentLeft <= mid {
        nums[index] = temp[currentLeft]
        index++
        currentLeft++
    }
}

関数に渡す作業配列は次のように初期化する。

temp := make([]int, len(data))
mergeSort(data, temp, 0, len(data)-1)

(追記: ChatGPT 先生と一緒に改良しました)

これは元のスライスを変えないパターン。あと、nums[i:j] みたいな書き方ができる。

func mergeSort(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }
    mid := len(nums) / 2
    left := mergeSort(nums[:mid])
    right := mergeSort(nums[mid:])
    return merge(left, right)
}

func merge(left, right []int) []int {
    ret := make([]int, 0, len(left)+len(right))
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            ret = append(ret, left[i])
            i++
        } else {
            ret = append(ret, right[j])
            j++
        }
    }
    ret = append(ret, left[i:]...)
    ret = append(ret, right[j:]...)
    return ret
}

二分探索

ソート済みのスライスを前提とする。ロジックは Java のコードとほぼ同じだけど、Go らしさを出すために戻り値を (int, bool) にしてインデックスだけでなく要素の存否を返すようにしてみた。

func binarySearch(nums []int, n, left, right int) (index int, ok bool) {
    if left > right {
        return -1, false
    }
    mid := (left + right) / 2
    if nums[mid] > n {
        return binarySearch(nums, n, left, mid-1)
    }
    if nums[mid] < n {
        return binarySearch(nums, n, mid+1, right)
    }
    return mid, true
}

あと、条件分岐のところを無駄に switch で書いてみた。Java と違って Go では case に式が書ける。

func binarySearch(nums []int, n, left, right int) (index int, ok bool) {
    if left > right {
        return -1, false
    }
    mid := (left + right) / 2
    switch {
    case nums[mid] > n:
        return binarySearch(nums, n, left, mid-1)
    case nums[mid] < n:
        return binarySearch(nums, n, mid+1, right)
    default:
        return mid, true
    }
}

(追記: ChatGPT 先生と一緒に改良しました)

これは再帰を使わずにループで書くパターン。

func binarySearch(nums []int, n int) (index int, ok bool) {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := (left + right) / 2
        if nums[mid] == n {
            return mid, true
        }
        if nums[mid] < n {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1, false
}

フィボナッチ数

通常バージョンとメモ化バージョン。

func fib(n int) int {
    if n <= 1 {
        return n
    }
    return fib(n-2) + fib(n-1)
}

func fib(n int, m []int) int {
    if n <= 1 {
        return n
    }
    if m[n] == 0 {
        m[n] = fib(n-2, m) + fib(n-1, m)
    }
    return m[n]
}

メモ化バージョンの方は、関数に渡すキャッシュは次のように初期化する。

m := make([]int, n+1)
fib(n, m)

(追記: ChatGPT 先生と一緒に改良しました)

再帰を使わないパターン。こっちの方がシンプルで Go っぽい...。

func fib(n int) int {
    if n <= 1 {
        return n
    }
    a, b := 0, 1
    for i := 2; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}

素数判定

ロジックは Java のコードとほぼ同じ。math.Sqrt の引数は float64 型の模様。

func primeNumber(n int) bool {
    if n < 2 {
        return false
    }
    sqrt := int(math.Sqrt(float64(n)))
    for i := 2; i <= sqrt; i++ {
        if n%i == 0 {
            return false
        }
    }
    return true
}

(追記: ChatGPT 先生と一緒に改良しました)

2 以外の偶数は先に結果を返して奇数だけチェックするパターン。

func primeNumber(n int) bool {
    if n < 2 {
        return false
    }
    if n == 2 {
        return true
    }
    if n%2 == 0 {
        return false
    }
    sqrt := int(math.Sqrt(float64(n)))
    for i := 3; i <= sqrt; i += 2 {
        if n%i == 0 {
            return false
        }
    }
    return true
}

所感

生成 AI のおかげで学習が捗る。