犬の手も借りたいあなたに最適な記事を届けます

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

スポンサーリンク

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

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

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

アルゴリズムとは

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

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

例題:三角形の面積を求める場合、底辺*高さ/2です。

これは正三角形で考えた場合です。

頂点から垂直に底辺までおろした場合、底辺のちょうど中点に位置します。

底辺を軸に三角形が収まるように正四角形を書いた場合、正三角形の頂点と他の点が正四角形の半分の対角点に位置することがわかります。

ので、三角形の面積の公式は「底辺*高さ/2」で表すことができます。

これはいわゆる公式と証明ですね。この公式とその考え方がアルゴリズムです。

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

使用例:試験上位100名を合格にする場合、テストの点数準順に並べて上位100名を表示する際に使います。

バブルソートとは、上記の並び替えのソート。の中でもどのように並び替えていくか、様々な方法があります。

アルゴリズム体操

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

1歩進んで前ならえ、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

特徴

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

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

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

・最短の計算時間はO(n)であるが、最長でO(n^2)である。

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

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

肉球ふにふに
肉球ふにふに

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

バブルソート徹底解説①

問題定義:

a,b,c,dという4つの箱があり、その中に2,4,3,1と数値が入っています。

これを昇順(小さい順)並び替えましょう。

※aに2、bに4、cに3、dに1とします。

手順1 a:b

aとbを比較します。

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

結果1 : 2431

手順2 b:c

bとcを比較します。

4と3なので入れ替えます。

bの箱に3を入れ、cのは箱に4を入れます

”い”ぬのて
”い”ぬのて

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

結果2 : 2341 (箱の並びはabcdそのまま)

手順3 c:d

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

”い”
”い”

注意:先ほどは4と3を入れ替えたので次は3と1の比較?4と1の比較?って迷うかもしれません。

しかし、箱同士の比較・場所同士の比較なので3番目と4番目・cとd・4と1の比較です。

結果3 : 2314

箱の並びはabcd(永遠に箱の並びは変わりません。)

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

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

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

48395 を並び替える場合、5桁なので4クール入れ替えが必要です。

1クール目は4回の入れ替え判断

2クール目は3回の入れ替え判断

ということですね。

手順2-1 a:b

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

2と3なので入れ替えません。

結果 : 2314

手順2-2 b:c

bとcの比較。

3と1なので入れ替えます。

結果2-2 : 2134

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

手順3-1 a:b

aとbの比較です。

2と1なので入れ替えます。

結果3-1 : 1234

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

あれ?もう終わり?そう思いましたね(圧)

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

バブルソート徹底解説②

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

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

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

絶対に・・・!!

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

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

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

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

ということです。

コード

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

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

コードは2種類!

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

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

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

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
      }
    }
  }
}
解説

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

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

内側の繰り返しの中身はjが要素数-1なので今回の例では3です。

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

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

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

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

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

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

選択ソートはソートアルゴリズムの1つでバブルソートに並んで処理の遅いソートアルゴリズムです。しかし、これもまた、理解することで、知識や考え方を生かすことができます。だからこそこうやってアルゴリズムやプログラミングの入門で学習として取り扱われます。選択ソートは要素たちの中で最小値または、最大値を見つけ出し、一番先頭に持ってくる考え方です。考え方は簡単ですね。ではそうやって一番小さい値を見つけ出せばいいのか・・・ここの理解が少し難しいと思いますので、丁寧に説明いたします。53241と要素が並んでいるとします。インデックスは01234ですので、まずは仮に最小値をインデックス0の5と仮定します。次に、インデックス0とインデクス1を比較します。5と3を比較すると、3の方が小さいですね。その場合、分岐を使ってインデックス0>インデックス1の場合最小値をインデックス1に上書きしてあげます。これを要素の数ー1回繰り返すと、インデックス番号4の1が最小値デアあることがわかりました。では、インデックス番号0と最小値であるインデックス番号4の中身を交換してあげましょう。するとインデックス番号0に1が入りました。ということです。これを繰り返します。2週目は先頭に持ってきたインデックス番号0、1を除いた残りで最小値を見つけ出していきます。日本語だけでの説明では変数の設定など、わかりにくいかもしれませんので、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}}

スポンサーリンク

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です