BubbleSortについて調べた

動機

就活をする中で、最終面接の課題になるという話だったので。

バブルソートとは

リストに於いて、隣り合う２つの要素を比較して条件に応じた交換を行う整列アルゴリズムのこと。
このソートを行うことで、値の小さい（大きい）ものが浮かび上がってくる様が、泡が浮かんでくる様を想起させるため「バブルソート」という。
最も基本的な交換法であるため、「基本交換法」「隣接交換法」、あるいは単に「交換法」と呼ばれることもある。

アルゴリズム

「算法」と訳されることもある。
問題を解く手順を定式化した形で表したもののこと。

ここでは、リストを「昇順」に整列させる手順を扱う。
①先頭の要素”A"と隣り合う次の要素"B"を比較する
②要素”A"が”B”よりも大きいなら、”A”と”B”の値を交換する
③先頭の要素を”B"に移し、隣り合う”C"の値を比較/交換する
④上記をリストの終端まで繰り返す
⑤最も大きい値を持つ要素がリストの終端に浮かび上がる
⑥終端の値はリスト内での最大値のため、要素数をひとつ減らして①〜⑥を繰り返す。
https://www.codereading.com/algo_and_ds/algo/bubble_sort.htmlを参考

値が移動していくのではなく、比較の基点が移動していくイメージ。

Javaでバブルソートを書く

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        int[] array = {1,45,22,90,22};
        
        for(int i = 0; i < array.length; i++){
            System.out.print(array[i] + " ");
        }
        System.out.println("sort前");
        
        //bubble sortの処理
        for(int i = 0; i < array.length -1; i ++){
            for(int j = array.length -1; j > i; j--){
                if(array[j - 1] > array[j]){
                    int tmp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = tmp;
                }
            }
        }
        
        //sort後を出力
        for(int i = 0; i < array.length; i++){
            System.out.print(array[i] + " ");
        }
    }
}

1 45 22 90 22 sort前
1 22 22 45 90

コードは以下を参考にしました。
https://techacademy.jp/magazine/19444
自分で考えて近いところまでは行ったけど、うまくいかなかった。
webフレームワークばかり勉強していて、言語のことを全然理解できてなかったのが原因かも。反省。
いや、普通に数学的思考回路が弱すぎるのが原因だ・・・単に頭が悪い。
とりあえず考え方としては、
ループの回数：常に隣の値と比較して交換していくため、length-1回となる。
終端の値を除外する処理：forの中にforを入れて、１ループごとにj--する。

バブルソートの特徴

計算回数はn(n-1)/2回
n回目のスキャンでn番目に軽い（重い）値を浮かび上がらせる計算量オーダーはO(n²)
ひとつずつ比較していくため処理は遅い。
一方で並列処理との親和性が高く、コード次第で計算回数を減らすことができたり、単純な比較のため直感的に扱えるという利点もある。

計算量オーダー

実際にアルゴリズムを実装する前に計算時間を大まかに測ることのできる「ものさし」のようなもの。
簡単なものだと、O(n)、O(n²)などがある。
これは簡単に調べることができる。

【例】

//これはO(n)
for(int i = 0; i < n; i++){
...
}

//これはO(n^2)
for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j ++){
...
    }
}

アルゴリズムとは本質的に「繰り返し処理」であるため、単純にfor文の数で計算量を求めることができるらしい（？）

ちなみに計算量オーダーは正しい計算量を示している訳ではない。
「ランダウのO記法」を用いて表記している。

ランダウのO記法

3n² + 5n + 100回の計算をするアルゴリズムがあるとする。
最高次数の項以外を落とす⇨3n²
⇨係数を落とす⇨n²
数学に明るくないので詳しい説明はできないが、nの値が大きくなればなるほど、他の数値は誤差になるということらしい。
アルゴリズムに関してはこの方の記事がとっても面白いです。（文系脳の私でも楽しく読めます）
https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0

まとめ

アルゴリズム面白い
明日はバブルソートを用いたプログラムをいくつか書いてみたい

体重133キロからのプログラミング

体重はちょっと減って今１２５キロです。

動機