週間アルゴリズム

概要

ソート系の中では有名なため、知っている人も多いかと思います。

リストの個数がnとした場合にn(n – 1)/2回のループが行われるためリスト数が多ければ多いほど負荷が高くなります。

ただし、仕組みとしては単純なため処理の記述量も少なくソートするリスト量が決まっているのであれば導入しやすいソートとも言えます。

ソート手順

1. 先頭の要素Aとその隣あう要素Bを比較する
2. AがBより大きいなら、要素AとBの位置を交換する（小さいのであればそのまま）
3. ２の処理をC、D、Eといった形でリストの終端まで要素を比較する（この時点でリストの最後尾には一番大きい値がセットされている）
4. リストの先頭に戻り２→３の様に処理を実行する。ただし、リストの最後尾には一番大きい値がセットされているため、リストサイズ – 1まで行う
5. ４の処理をリストサイズ分だけ繰り返したら処理を終了する

ソースコード

package main

import (
	"fmt"
	"math/rand"
)

func bubbleSort(numbers []int) []int {
	for i, _ := range numbers {
		for j, _ := range numbers[0 : len(numbers)-1-i] {
			if numbers[j] > numbers[j+1] {
				numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
			}
		}
	}
	return numbers
}

func main() {
	// 0~999までのランダムな数値を生成
	nums := rand.Perm(1000)[:10]

	fmt.Println(bubbleSort(nums))
}

実行結果

[35 108 130 178 355 384 689 754 828 877]

数値がソートされてますね！