アルゴリズム ビジュアル大辞典のアルゴリズムをPython, Goで実装する [スワップソート、合計、最小・最大値の値とインデックス取得]

何をやるか

先日販売されたこちらの書籍より、基礎的なアルゴリズムを実装してみたいと思い立ったので、Python, Goで実装にトライしてみます。

アルゴリズム ビジュアル大事典

スワップソート

概要

データの入れ替え(スワップ)を繰り返しながらデータの順序を変えるアルゴリズム。
変数の中身を交換するスワップを行うためには、入れ替え対象となる2つの変数のほかに、どちらかの値を退避させるための箱(変数)も必要となる。

実装例

A = 8
B = 5
C = 2

def swap(x, y):
    t = x
    x = y
    y = t
    return x, y

if __name__ == '__main__':
    if A > B:
        A, B = swap(A, B)
    if B > C:
        B, C = swap(B, C)
    if A > B:
        A, B = swap(A, B)
    print(A, B, C) # 2, 5, 8

package main

import (
	"fmt"
)

var (
	A int = 8
	B int = 5
	C int = 2
)

func swap(x, y *int) {
	t := *x
	*x = *y
	*y = t
}

func main() {
	if A > B {
		swap(&A, &B)
	}
	if B > C {
		swap(&B, &C)
	}
	if A > B {
		swap(&A, &B)
	}
	fmt.Println(A, B, C) // 2, 5, 8
}

メモ

Goの場合、ポインタで操作しながら変数の実体を入れ替えられるが、Pythonの場合、原則参照渡しであるものの、イミュータブルな型については値渡しのような振る舞いになるため、関数内にてSwapした値を返すことにした。

参考

Pythonの変数はイミュータブルなのでポインタみたくはできない - Qiita
Pythonにおける値渡しと参照渡し - sushi.py
pythonの参照について - Qiita

合計(サム)

概要

配列などの複数のデータに対して、全ての値を参照して足し合わせた合計値を得るアルゴリズム。

実装例

A = [1,2,3,4,5,6,7]
sum = 0

if __name__ == '__main__':
    for i in A:
        sum += i
    print(sum) # 28

package main

import (
	"fmt"
)

func main() {
	A := []int{1, 2, 3, 4, 5, 6, 7}
	total := 0

	for i := 0; i < len(A); i++ {
		total = total + A[i]
	}
	fmt.Println(total) // 28

最小(最大)要素の値

概要

配列など複数のデータやデータの集合に対して、全ての値を参照して最小の値(または最大の値)を得るアルゴリズム。
以下の例は最小値を得るもので、配列から1つずつ値を取り出して、初期値との大小関係を比較しながら最小値を格納する変数を更新していく。

実装例

A = [10,23,24,23,21,6,17]
minv = A[0]

if __name__ == '__main__':
    print(minv)
    for i in A:
        if i < minv:
            minv = i
    print(minv) # 6

package main

import (
	"fmt"
)

func main() {
	A := []int{10, 23, 24, 23, 21, 6, 17}
	minV := A[0]

	for i := 0; i < len(A); i++ {
		if A[i] < minV {
			minV = A[i]
		}
	}
	fmt.Println(minV) // 6
}

メモ

初期値は何でもいいが、INFを設定したり、対象となる集合値のうち最初の値を設定しておけばいい。

最小値のインデックス取得

概要

今度は値そのものではなく最小(最大)値のインデックス取得をするアルゴリズム。
言語によって書き方は様々だと思うが、関数化して書いてみた。

実装例

def minimum(array):
    mini = 0
    for i in range(len(array)):
        if array[mini] > array[i]:
            mini = i
    return mini, array[mini]

A = [9,3,5,7,11,20,12,8]
print("index:{} value: {}".format(minimum(A)[0], minimum(A)[1])) # index: 1 value: 3

package main

import (
	"fmt"
)

func minimum(array []int) (idx int, value int) {
	mini := 0
	for i := 0; i < len(array); i++ {
		if array[mini] > array[i] {
			mini = i
		}
	}
	return mini, array[mini]
}

func main() {
	A := []int{9, 3, 5, 7, 11, 20, 12, 8}
	idx, val := minimum(A)
	fmt.Printf("index: %d value: %d", idx, val) // index: 1 value: 3
}