【2021年最新】コード有バブル・選択ソートのアルゴリズム徹底解説

たくさんのソートアルゴリズムの中でも、一番理解しやすいのが、バブルソートです。

ソートアルゴリズムとは、たくさんのデータを小さい順や大きい順に並び替える事をソートといいます。（sort:整列）

並び替えはよく使うかと言われれば、実務ではあまり使わない気がしますが、アルゴリズムを理解していることで日々の業務にも応用を利かせることができたりしますので、じっくり学びましょう。

アルゴリズムとは

アルゴリズムとは、計算の手順・方法や考え方を指します。

プロセスや一連の流れなどと解釈してもいいかもしれませんね。

つまり、アルゴリズムとはその答えを導くための考え方です。

アルゴリズム体操

みなさんアルゴリズム体操は聞いたことありますか？

1歩進んで前ならえ、1歩進んで偉い人、ひっくり返ってぺこりんこ・・・・

アルゴリズム体操

ってやつですね！

知らない人は無視して結構です。余談なので・・・

で、このアルゴリズム体操はなんのアルゴリズムかわかりませんが、体操かな？

1つずつ動作をしていくというプロセスや、流れを１つずつ説明しています。

これがアルゴリズムなのですねー

奥が深いようで適当なようなネタです：）

重要性

アルゴリズムをしっかり理解する事は、プログラミングやシステム開発においてパフォーマンスを向上させます。

あるシステムを開発する際、いろんな方法がありますが、アルゴリズムを理解する事で最適な方法を解とします。

最適な方法でシステム構築することで処理量が減りますのでパフォーマンスが向上します。

WEB制作なんかにおいても、ページを読み込むスピードが変わるなどといった効果があります

ソートアルゴリズム

ではまず、ソートアルゴリズムですが、ソートというのは整列（英語でsort）です。

何かを整列させたいとき、数字を小さい順や大きい順に並び変えるときには、いろんな方法があります。

バブルソート・クイックソート・マージソートなど種類がありますが、今回はバブルソートを説明します。

バブルソート

バブルソートは隣の要素と比較して入れ替える手法です。

隣と比較して昇順（降順）になっていないなら、入れ替える。を、繰り返していきます。

一般的な実装ではこの処理を列の一方の端から反対の端まで順番に行うことが多く、繰り返しの度に未整列の要素の中で最も大きな（あるいは小さな）要素が列の端に移動していく様子を泡（バブル）が浮き上がっていく様に例えてこのような名称となりました。

https://e-words.jp/w/%E3%83%90%E3%83%96%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88.html – IT用語辞典e-Word

特徴

・アルゴリズムの理解が簡単。

・コード記述が少なく実装簡単

・実務上あまり使われないが、学習によく取り上げられる。

・最短の計算時間はＯ（n）であるが、最長でＯ（n＾２）である。

・平均して高速で最良な手法ではない。

要素の比較や交換を順不同で並列化しやすいため処理装置を分散することで高速化することもできます。

肉球ふにふに

今は計算時間とかどれが最良化など気にする必要はないと思います！が、手法によって計算時間が違うことだけ知っておきましょう。

バブルソート徹底解説①

手順1 a:b

aとbを比較します。

2と4の比較なので入れ替えません。

手順2 b:c

bとcを比較します。

４と３なので入れ替えます。

bの箱に３を入れ、cのは箱に４を入れます

”い”ぬのて

※箱の中身だけ入れ替える感覚だよ。

手順3 c:d

cとdを比較します。4と１なので入れ替えます。

”い”

注意：先ほどは４と３を入れ替えたので次は３と１の比較？４と1の比較？って迷うかもしれません。

しかし、箱同士の比較・場所同士の比較なので３番目と4番目・cとｄ・４と１の比較です。

ここで1クール目が終了です。これを「要素の数-１」クール行います。

また、2クール目は入れ替えは「要素数-クール数」回でおｋです。

ではこれを繰り返します。

手順2－1 a:b

またaとｂの比較を行います。

２と３なので入れ替えません。

手順2-2 b:c

ｂとｃの比較。

３と１なので入れ替えます。

手順2-3は行わなくてもＯＫです。理由は後程説明します。

手順3-1 a:b

aとｂの比較です。

２と１なので入れ替えます。

ということで完成です。‼‼‼‼‼

あれ？もう終わり？そう思いましたね（圧）

では、なぜ、手順2－3や手順３－２が不要かを解説します。

バブルソート徹底解説②

バブルソートではクール度にその要素達の中で一番大きいものを一番後ろ（右に）持って行きます。

なので、一番右に持って行った数字は確定で動くことがありません。

ので、一番最後と一番最後から2番目の比較はする必要がありません。

絶対に・・・！！

同様に2クール目で確定した一番後ろの数字を除く「要素数-1」個の要素の中で、

一番大きいものを一番後ろに（一番後ろのひとつ前）に持って行きますので、

2クール目では一番後ろ２つが確定しています。

同様に3クール目では後ろ2つが確定しているため、今回の例では残った2つを比較するだけで入れ替えが完了します。

ということです。

コード

javaをメインにコードで書いてみました。

ifとかforとかプログラミング言語の基本をまだ学んでいない人はこちらへ！

コードは２種類！

２種類のコードがあります。

どちらでも計算時間や回数は同じなため、理解しやすい方をお使いください。

コード① : 大きいものを後ろに

1つ目は大きい数字を一番後ろにするやり方で、今回の例と同じです。

”の”

（自身で考えたコードなので、うまく実行できなかった場合、ご連絡ください。

※自身で考えたコードというのはこの大きいものを後ろにするやり方がネットや参考書に見当たらなかったという意味です。）

コード汎用性を高めるため、中身の記述だけします。

for(i=0;i<a.length;i++){
  for(j=0);j>a.length-i-1;j++{
    if(a[j]>a[j+1]){
      keep=a[j]a[j]=a[j+1]a[j+1]=keep
      }
    }
  }
}

コード② : 小さいものを先頭に

2つ目は様々なサイトに載っているやり方で、先にコードの紹介をします。

解説は後程

for(i=0;i<a.length;i++){
  for(j=a.length-1);j>i;j--{
    if(a[j-1]>a[j]){
      keep=a[j]a[j]=a[j-1]a[j-1]=keep
      }
    }
  }
}

解説

基本的には先ほどのやり方と同じで、大きいのを後ろにするか、小さいのを前にするかの違いだけです。

外側の繰り返しは同じなので割愛します。

内側の繰り返しの中身はｊが要素数-１なので今回の例では３です。

例ではわかりやすいようにabcdという箱で説明しましたが、実勢は０１２３という箱番号が割り振られています。

これは言語ほぼ共通ですので覚えておきましょう。

なので、ｊの値というのは３、つまり最後の箱です。

そして、jがiより大きいうちは処理を続けます。

普段はi<3とかでiが数値を追い抜いて終了がおおいですが、今回はｊがiを下回って終わるようにj—と記述します。

あとは、通常通りですね。

選択ソートはソートアルゴリズムの１つでバブルソートに並んで処理の遅いソートアルゴリズムです。しかし、これもまた、理解することで、知識や考え方を生かすことができます。だからこそこうやってアルゴリズムやプログラミングの入門で学習として取り扱われます。選択ソートは要素たちの中で最小値または、最大値を見つけ出し、一番先頭に持ってくる考え方です。考え方は簡単ですね。ではそうやって一番小さい値を見つけ出せばいいのか・・・ここの理解が少し難しいと思いますので、丁寧に説明いたします。５３２４１と要素が並んでいるとします。インデックスは０１２３４ですので、まずは仮に最小値をインデックス０の５と仮定します。次に、インデックス０とインデクス１を比較します。５と３を比較すると、３の方が小さいですね。その場合、分岐を使ってインデックス０＞インデックス１の場合最小値をインデックス１に上書きしてあげます。これを要素の数ー１回繰り返すと、インデックス番号４の１が最小値デアあることがわかりました。では、インデックス番号０と最小値であるインデックス番号４の中身を交換してあげましょう。するとインデックス番号０に１が入りました。ということです。これを繰り返します。２週目は先頭に持ってきたインデックス番号０、１を除いた残りで最小値を見つけ出していきます。日本語だけでの説明では変数の設定など、わかりにくいかもしれませんので、Javaコードを掲載します。若ありやすいようにメソッドの中身だけ記述しました。for(I=0;i<a.length;i++){min=I;for(j=i+1;j<a.length;j++)if(a[min]<a[j]){min=j}keep=a[i];a[i]=a[min];a[min]=keep}}