Zenn
📊

Go言語で学ぶアルゴリズム：バブルソート

2024/07/07に公開
Go
入門
アルゴリズム
tech

はじめに

業務でアルゴリズムを利用することは少ないと思います。
私自身も業務の中でアルゴリズムが必要になったことは殆どありませんし知らなくてもなんとかなっています。
ただ、エンジニアとして基本的なアルゴリズムぐらいはわかっておいたほうがいいなという思い立ったので学習記録も兼ねて記事にしたいと思います。

バブルソート

まずはアルゴリズムの基本であるバブルソートについて学んでいきます。
数あるソートアルゴリズムの中でも処理が単純なため理解しやすいアルゴリズムだと思います。

アルゴリズム

以下のような配列があるとします。
[3, 6, 4, 1, 7, 8, 2, 5, 9]

右端から数字を比較していきます。
[3, 6, 4, 1, 7, 8, 2, 5, 9]
          ↑ ↑
ここでは右の数字のほうが小さいので入れ替えずに次に進みます。
[3, 6, 4, 1, 7, 8, 2, 5, 9]
        ↑ ↑
ここでも右の数字のほうが小さいので入れ替えずに次に進みます。
[3, 6, 4, 1, 7, 8, 2, 5, 9]
       ↑ ↑
ここでは右の数字のほうが大きいので入れ替えます。
[3, 6, 4, 1, 7, 2, 8, 5, 9]
       ↑ ↑
入れ替えが完了しました。次に進みます。
[3, 6, 4, 1, 7, 2, 8, 5, 9]
      ↑ ↑
ここでも右の数字のほうが大きいので入れ替えます。
[3, 6, 4, 1, 2, 7, 8, 5, 9]
      ↑ ↑
このような処理を配列の左端まで移動しながら行います。１度目の並び替えが終わった配列は以下のようになります。
[1, 3, 6, 4, 2, 7, 8, 5, 9]

この時点で左端には配列中の最小の数字が移動してきていることになります。
このような処理を配列の個数分繰り返します。すると配列は以下のようにソートされていきます。

  • 1回目：[1, 3, 6, 4, 2, 7, 8, 5, 9]
  • 2回目：[1, 2, 3, 6, 4, 5, 7, 8, 9]
  • 3回目：[1, 2, 3, 4, 6, 5, 7, 8, 9]
  • 4回目：[1, 2, 3, 4, 5, 6, 7, 8, 9]
  • 5回目：[1, 2, 3, 4, 5, 6, 7, 8, 9]
  • 6回目：[1, 2, 3, 4, 5, 6, 7, 8, 9]
  • 7回目：[1, 2, 3, 4, 5, 6, 7, 8, 9]
  • 8回目：[1, 2, 3, 4, 5, 6, 7, 8, 9]
  • 9回目：[1, 2, 3, 4, 5, 6, 7, 8, 9]

以上でバブルソートは完了です。
今回の配列では４回目のソート時点でソートが完了していますがもし配列が大きい順に並んでいた場合は配列の個数分処理を繰り返さないとソートが完了しないことになります。

計算量

バブルソートの計算量はどうなっているでしょうか。
1回のソートで数値を比較する回数を考えます。1回目のソートでは端から端まで比較を行う必要があるので比較回数は8回になります。
2回目のソートでは左端には最小の数値が来ているのでその前まで比較を行えばよいことになります。比較回数は7回です。
このように回数を繰り返すごとに比較回数は8→7→6→5→・・・→1と減っていきます。
ソートする配列の長さをnとすると比較回数は以下の式で表されます。

(n - 1) + (n - 2) + (n - 3) + ・・・+ 1 = \displaystyle\sum_{k=1}^nk = \cfrac{n(n - 1)}{2}

よって最悪の場合計算回数は\cfrac{n^2 - n}{2}回になるので計算量はO(n^2)となります。

実装

では実際にバブルソートを実装してみます。
ソースコードは以下のようになります。

main.go
package main

import "fmt"

func main() {
  array := []int{3, 6, 4, 1, 7, 8, 2, 5, 9}
  for i := 0; i < len(array); i++ {
    for j := len(array) - 1; j > i; j-- {
      if array[j] < array[j-1] {
        array[j], array[j-1] = array[j-1], array[j]
      }
    }
  }
  fmt.Println(array)
}

実行するとソートされた結果が表示されます。

$ go run main.go 
[1 2 3 4 5 6 7 8 9]

正しくソートされています。

1つ目のfor文は配列の長さ分処理を繰り返します。この処理が1回終了するごとに比較した数字の中で最小の値が左から順番にソートされていきます。
2つ目のfor分の中で隣り合う数字の比較を行います。左側の数字が右側の数字より大きい場合要素の入れ替えを行います。ここでの繰り返し回数は外側のfor文が進むたびに比較を行う範囲が狭まっていくのでj > iとしています。

ランダムな数値を生成して試してみます。
コードは以下のとおりです。

main.go
package main

import (
	"fmt"
	"math/rand"
)

func randomArray(arr []int) []int {
	lenNumbers := len(arr)
	for i := 0; i < lenNumbers; i++ {
		arr[i] = rand.Intn(1000)
	}
	return arr
}

func bubbleSort() {
	array := make([]int, 10)
	randomArray(array)
	lenArray := len(array)
	for i := 0; i < lenArray; i++ {
		for j := len_array - 1; j > i; j-- {
			if array[j] < array[j-1] {
				array[j], array[j-1] = array[j-1], array[j]
			}
		}
	}
	fmt.Println(array)
}

func main() {
	for i := 0; i < 10; i++ {
		bubbleSort()
	}
}

実行すると以下の結果が得られました。正しくソートされています。

$ go run main.go 
[94 122 412 433 452 643 645 715 758 976]
[56 103 130 360 363 523 682 826 852 882]
[86 102 135 338 391 407 423 435 502 578]
[47 95 294 407 417 469 579 708 802 893]
[18 58 343 398 444 446 626 787 866 884]
[1 161 297 478 529 578 605 696 837 875]
[53 60 239 287 438 472 515 592 769 899]
[44 45 193 252 255 378 436 473 598 612]
[122 183 284 475 704 756 844 861 982 988]
[14 54 59 490 602 694 897 913 959 993]

まとめ

今回はバブルソートについて学習しました。
次回は選択ソートについて取り扱う予定です。

Discussion