プログラミング

【まじ簡単?】バブルソートのアルゴリズムをフローチャートで解説

  • このエントリーをはてなブックマークに追加
  • LINEで送る

Hello! プログラミング楽しんでますか?

今回はバブルソートについて解説しますyo!



『バブルソートがよくわからん』

『ソート処理の基礎を学びたい』

『フローチャートでバブルソートの仕組みを知りたい』

こんな疑問に答えます。

バブルソートのアルゴリズムを簡単に解説♪

バブルソートは最もスタンダードで、シンプルな並替え処理としてが有名です。

では、どんな手順(アルゴリズム)でソートされるのでしょうか?

バブルソートを簡単に説明すると…

端から順に隣との大小を比較・交換を繰り返し、ソートする処理です。

バブルソートのアルゴリズム

端から順に隣との大小を比較・交換を繰り返しソートする

たろちゃん
たろちゃん
え!?
何のこっちゃわからん
大きな流れで考えよう!
SEおっさん
SEおっさん

バブルソートの大きな流れは次の感じです。

バブルソートの流れ
  1. 左から順に隣と比較
  2. 右が大きければ交換
  3. ①と②を繰り返す
たろちゃん
たろちゃん
まだ、わからん


大丈夫じゃ♪
簡単な例で解説するぞい
SEおっさん
SEおっさん

バブルソートのアルゴリズムを具定例で解説

バブルソートで5つの数字を昇順に並び替えるアルゴリズムです。

ちなみに、昇順とは小さい順のこと。

次の【例題】を見てください。

【例題】

数字(7 5 3 10 2)をバブルソートで昇順に並べ替えよ

 7 5 3 10 2
  ↓ ↓ ↓ ↓  
  バブルソート
  ↓ ↓ ↓ ↓
 2 3 5 7 10

まずは…

【例題】の5つの数字が、

バブルソートで小さい順に並べ替わる様子

をザクッと頭にイメージしてください。

バブルソートで小さい順に並べ替わるイメージ

SEおっさん
SEおっさん
理解できなくてOK♪
なんとなくイメージじゃ
  • 初期値をセット
    7 5 3 10 2
  • 最大値を確定
    7 5 3 2 10
  • 2番目に大きな数字を確定
    5 3 2  10
  • 3番目に大きな数字を確定
    3 2  7 10
  • 4番目に大きな数字と最小値を確定
    2 3 5 7 10

バブルソートのアルゴリズムをもう一度おさらいしてみましょう。

バブルソートのアルゴリズム

左端から順に隣との大小を比較・交換を繰り返しソート

では、いよいよバブルソートの開始です。

初めてみましょう!

バブルソートで昇順に並び替え

バブルソートは左から順番に隣との大小を比較しながら交換します。

比較しながら交換していく様子を見ていきましょう!

  • 初期値をセット

    5つの箱(A~E)に数字(7 5 3 10 2)をセットします。

  • 最大値を確定

    左右の数字と比較して、左が大きければ交換です。

    イエローのペアを比較して交換する様子をみてください。

    SEおっさん
    SEおっさん
    イエローのペアを比較じゃ



    左端から順にと右隣と比較して交換してますね。
    小さい順なので左のほうが大きければ交換します。
    比較すると1つ右へ移動して再び比較です。

    このように
    右へ移動しながらペアと比較・交換を繰り返します。
    ペアはイエローの部分です。
    ペアが右端まで来ると最大値が確定して終了。

    最大値【10】が1番右に移動してますね。

  • 2番目に大きな数字を確定

    2番目も同じように比較・交換を繰り返します。

    さっきと違う点が1つあるので探してください。


    2番目に大きな数値【7】が隣り合うイエローと比較・交換しながら右に移動してますね。

    これは最大値【10】が確定した時と同じ動きです。
    1つだけ違う大きなポイントは…

    最大値【10】の手前で比較をSTOPすること

    です。

    なぜ手前でSTOPするかわかりますか?

    10は確定済だから!
    たろちゃん
    たろちゃん

    SEおっさん
    SEおっさん
    Yes!

    10と7は比較済のため、10は一番右で決まり。
    決まってるのに、比較するのは無駄。

    もう一度、10と7を比較しても結果は同じですが、
    プログラムは極力”無駄”な処理は省略します。

    なんで省略するの?
    たろちゃん
    たろちゃん

    SEおっさん
    SEおっさん
    処理が遅くなるからじゃ

    速い方が時間を待たなくて良いですよね。
    だから、パフォーマンスは重要ってわけです♪

  • 3番目に大きな数字を確定

    3番目も同じように比較・交換を繰り返します。

    繰り返しをSTOPするポイントは7の手前です。


  • 4番目に大きな数字と最小値を確定

    4番目も同じように比較・交換します。

    ここにも大事なポイントがありますよ!



    数字は5つありますが、
    4つ確定すると最後の5番目も決まりますよね。

    既に3つ【5 7 10】(グレー)は決まってるので、
    4つ目を比較・交換させる終了です。

    比較交換は1組【3 2】(イエロー)だけ。

    つまりポイントは…

    1番最後は交換が不要

    ということです。

    4番目に大きな数字【3】が決まると
    【2】が1番左に残されます。

    一番左は最小値。
    もう比較する必要は無いですね。

    繰り返し処理の省略は、意外にプログラマを悩ますものです。

    プログラミングで

    「アレレ? あと一回比較するんじゃなかったっけ」

    という疑問が湧いた時は思い出してみてください。

    たろちゃん
    たろちゃん
    あ、わかった気がする!

数字(7 5 3 10 2)をバブルソートで小さい順に並べ替え

という【例題】で解説しました。

いかがだったでしょうか?

少しでもバブルソートの意味がわかってきたらGoodです。

完璧を目指さずにザクっと理解することも大切だ!

バブルソートのアルゴリズムを例題 まとめ

バブルソートを具体的な例で考えると、

仕組みが理解しやすくなります。

仕組みがわかる=アルゴリズムがわかる

ということです。


ポイントを振り返ってみましょう。

小さい順に並び替えるポイント
  • 左端から順に右隣と比較して交換する
    左>右 の場合…交換する
    左≦右の場合…そのまま

  • 比較後は1つ右へ移動して再比較
    右端まで移動と比較を繰り返す
    比較ペアが右端にくると確定
    確定後は左端から再び比較

  • 確定したものは再比較しない

  • 1番最後は比較不要


スポンサーリンク

バブルソートをフローチャートで簡単に解説♪

バブルソートの手順(アルゴリズム)がわかったので、早速プログラミングをしてみましょう。

と言われても…

たろちゃん
たろちゃん
え~っ!!

ってなりますよね。

ご安心ください。ここでフローチャートの出番です。

フローチャートはプログラミングの橋渡し役。

簡単な図で処理の流れがわかるので、プログラミングにとても有効です。

バブルソートのアルゴリズムをプログラミングすることは、難しいように見えますが、フローチャートを使うと意外と簡単にわかっちゃいます。

フローチャート。そう。それは魔法です。

 

【記号は5つ】フローチャートの書き方【初心者向け簡単マニュアル】
【記号は5つ】フローチャートの書き方【初心者向け簡単マニュアル】
フローチャートを覚えたら、プログラムが理解できるようになります。 理解できるとプログラミング楽しくなるので、スキルアップが加速します。 スキルアップすると年収ア.....

 

SEおっさん
SEおっさん
バブルソートを
フローチャートにしてみよう!
バブルソートのフローチャート

たろちゃん
たろちゃん
あ、あかん…
目がクラクラする

フローチャートで目がクラクラする理由は…

英語の変数(Xとかnとかi)がイキナリが出るから。

変数を理解すれば難しくありません。

たろちゃん
たろちゃん
変数ってナニ?
変化する数じゃ♪
SEおっさん
SEおっさん

変数とは変化する数の入れ物です。

つまり、

「数が変化する様子」を追うことが出来れば、変数を理解したも同然。

とはいえ、

プログラムを見ても「数が変化する様子」は解り辛い。

フローチャートは数の変化をわかりやすく表現するツールなのです。

数の変化を追うことで、全ての謎が解けます。じっちゃんの名にかけて。

 

「数が変化する様子」を知る近道は、具体例でフローチャートを追うことです。

【例題】でフローチャートの変数を追っていきましょう。

SEおっさん
SEおっさん
ここが正念場じゃ
ついてこい!
【例題】

数字(7 5 3 10 2)をバブルソートで昇順に並べ替えよ

フローチャートで使用する変数

X…数値が入る箱の枠(配列)
n…箱の数(配列の数)
iとj…箱の位置(配列のインデックス)
Temp…1時的な作業領域(交換で使用)

変数Xは配列といいます。

下記に置き換えて、各々イメージしてください。

X…配列 ⇒⇒⇒⇒ タンス
n…箱の数 ⇒⇒⇒ タンスの数
iとj…箱の位置 ⇒ 引出し
数字 ⇒⇒⇒⇒⇒⇒ 服

nが5なので、タンスの引き出しは次の5つ。

【例題】の初期値を配列に代入すると、こんな感じ。

 ↓こんな感じ
 X[0]=7
 X[1]=5
 X[2]=3
 X[3]=10
 X[4]=2

どうですかね?

配列Xは引出しが5つのタンスみたいでしょ。
5つの引出しに服(数字)を入れてますね。

チョットややこしいのは…
配列は0から始まる風習があるので、0~4の5つとなります。
0~4を配列のインデックス(添字)といいます

また、
配列に直接数字を入れることは出来ません。
服は直接タンスに入れず、引出しに入れますよね。
配列は単なる箱の枠なので、配列Xに数を入れるのはNGです。

SEおっさん
SEおっさん
X=7はOK?NG?

NG!
たろちゃん
たろちゃん

SEおっさん
SEおっさん
X[3]=10はOK?NG?

OK!
たろちゃん
たろちゃん

SEおっさん
SEおっさん
正解じゃ!
おほほのほ♪

配列のインデックス0~4が箱の位置となります。
変数iとjは配列のインデックスです。
繰り返し処理で使用されるのでループ変数とも呼ばれます。

「ループがイマイチ理解できない!」
という方はコチラ↓
フローチャートで簡単にループを抜ける方法!2つの図形と3つの判定

では、改めてフローチャートを見てみましょう。

 

なんとな~くイメージできたかな?

たろちゃん
たろちゃん
ふむふむ
なんとな~く

なんとなく変数が整理できたら、処理と変数を追いかけてみよう♪

ループで使用する変数iとjは箱の位置でしたね。
バブルソートで左右の数を比較する際、ループ変数を箱の位置として使用しますよ。

  • 初期値をセット

    初めにランダムな数値をセットします。
    前回では箱(A~E)でしたが今回は箱X(0~4)となっているのがポイントです。
    箱の名前は変わりましたが、5つの箱であることには変わりありませんヨ。

  • 最大値を確定

    箱に値をセットしたら、バブルソートを開始です。

    どうですか?

    ループAの変数IとループBの変数jの違いがわかるでしょうか?

    ループAの始まりは4
    ループBの始まりは0
    ってのがミソですよ♪

    ループA…繰返し毎に1つ減る

    ループB…繰返し毎に1つ増える
  • 2番目に大きな数字を確定

  • 3番目に大きな数字を確定

  • 4番目に大きな数字と最小値を確定

 

いかがでしょうか。

数の変化を理解できましたか?

ここでもう一度、フローチャートを見てみましょう。

フローチャート

 

たろちゃん
たろちゃん
あ、わかった気がする!

ここまで理解できれば、フローチャートのプログラミング化は簡単です。
さぁ、ガンバってトライしましょう。

バブルソートで降順にソートする方法

小さい順に数値を並べることを「昇順」にソートする
大きい順に数値を並べることを「降順」にソートする

といいます。

【例題】では昇順のソートを学んできました。

たろちゃん
たろちゃん
降順のソートはどうするの?
交換条件が違うだけじゃよ
SEおっさん
SEおっさん

バブルソートで降順にソートする条件

降順ソートは「昇順ソートと交換条件が逆」ただそれだけです。

 

降順は大きい順なので、(左<右)の場合に交換します。

つまり、

小さい順に並んでいる時に交換して大きい順にする

ということです。

例えば、2と4なら交換します。

 

一方で

昇順は小さい順なので、左右を比較して(左>右)の場合に交換します。

大きい順に並んでいる時に交換して小さい順にするということです。

例えば、3と1なら交換します。

 

昇順ソートを理解していれば降順ソートはメチャ簡単ですね。

昇順・降順の交換条件を記したバブルソートのポイントをまとめます。

バブルソートのポイント
  • 左端から順に隣(左と右)の比較・交換を繰り返す

    【右と左を交換する条件】
    昇順…左>右で交換
    降順…左<右で交換

  • 確定したものは再比較しない

  • 1番最後は交換が不要

わからない場合は、先程の具体例を交えて眺めてみてください。

それでも、わからない…

という場合は、

フローチャートを振り返ってみて下さい。

バブルソートのアルゴリズムを理解するには次の順番で進めて行くとGoodです。

  1. 例を用いてアルゴリズムを理解
  2. フローチャートを書く

アルゴリズムを理解してフローチャートを書けたらプログラミング化することも簡単ですよ♪

一緒に学んでいきましょう。



スポンサーリンク

ソートが使用される場面とアルゴリズムの種類

ソートは様々な場面で使用され、バブルソート以外にも様々なアルゴリズムがあります。

ソートが使用される場面

  • Excelの並び替え
    日付の列を選択して、メニューのデータで並び替え
    昇順…↑アイコン
    降順…↓アイコン
    日付の列のセル…バブルソートの箱
  • SQL(データベース操作言語)のSELECT文
    SELCT文ではOrder by句としてソート指定
    例)
    SELECT * FROM 焼き肉屋 ORDER BY 入荷日 DESC
    Order by句の後に並替えたい項目名を指定
    昇順ソート…ASC
    降順ソート…DESC
    入荷日のデータ…バブルソートの箱

様々なソートアルゴリズム

バブルソート以外にもソートアルゴリズムはあります。

種類は豊富ですよ。

ソートアルゴリズムの種類
  • バブルソート
  • クイックソート
  • マージソート
  • 選択ソート
  • 挿入ソート
  • ヒープソート

たろちゃん
たろちゃん
え!
そんなにあるの?

手段が違うだけで
目的は同じじゃよ
SEおっさん
SEおっさん


バブルソートが一番スタンダードでわかりやすいため、解説いたしました。

ぜひ他のソートアルゴリズムも学んでみてください。

機会があれば詳しく紹介したいと思っています。

それまでは「マージソート」とかでググってね♪

バブルソートのアルゴリズムをフローチャートで解説 まとめ

バブルソートのアルゴリズムをフローチャートで解説いたしました。

いかがでしたでしょうか?

 

バブルソートのアルゴリズムがわかり、自分の手でフローチャートを描ければ、プログラミングは簡単です。

ほぼ全ての言語でバブルソートをプログラミング化できるでしょう。

そして、バブルソートにはプログラミングに必要な基本が含まれています。

つまり…

バブルソートをプログラミング化できれば、

プログラマーの素質アリ

ということです。

バブルソートを侮るなかれ
SEおっさん
SEおっさん

バブルソートはシンプルな処理なので、初心者がプログラミングの流れを理解するのに適した素材。

しかし、その一方…

シンプルな処理とはいえ、そこはプログラミング。

条件分岐や2重ループというボス達が待ち構えていています。

 

初心者がバブルソートのアルゴリズムを簡単に理解するのも困難なことも確か。

そこで登場する強力な武器が「フローチャート」

 

フローチャートを駆使して、バブルソートを倒しちゃいましょう。

 

では、ポイントを振り返ってみていきましょう。

バブルソートとは

最もスタンダードで、シンプルな並替え処理

バブルソートのアルゴリズム

端から順に隣との大小を比較・交換を繰り返しソートする

バブルソートの流れ
  1. 左から順に隣と比較
  2. 右が大きければ交換
  3. ①と②を繰り返す
バブルソートのポイント
  • 左端から順に隣(左と右)の比較・交換を繰り返す

    【右と左を交換する条件】
    昇順…左>右で交換
    降順…左<右で交換

  • 確定したものは再比較しない

  • 1番最後は交換が不要

バブルソートを正しく理解して、

プログラミングの勇者への道を歩んでください。

「ゆっくりと、でも確実に」

このブログがその手助けになれば幸いです。

SEおっさん
SEおっさん
ここまで読んでくれてありがとう!

「記事を読んでもわからないトコがある」「内容が変だよ」
という時は、お気軽にコメントください♪

「もっとSEおっさんに詳しく聞きたい。何かお願いしたい!」
という時は、ココナラまで。メッセージもお気軽に♪


LINEでのお問合わせも受付中!
LINE公式アカウント

メッセージをお待ちしています!



スポンサーリンク
  • このエントリーをはてなブックマークに追加
  • LINEで送る

コメント

  1. cyber96jp より:

    はじめまして。今度、ITパスポートなるものを受ける予定の50代のオッサンです。フローチャートなるものを四苦八苦しながら勉強しておりまして、こちらに辿り着きました。
    ひとつ、分からないのが、j = i -1 の分岐のところです。何度もトレースしてみたのですが、どうしても最後の比較に行かずにループBを抜けてしまいます。j = i ではダメなのでしょうか?これだとうまく行くのです。
    もしかしたら、別のところに問題があるかもしれませんが、、、お時間ありましたら教えてくださいませ。失礼致します。

    1. SEおっさん より:

      はじめまして。
      返信が大変遅くなってしまい申し訳ございませんm(__)m
      3カ月も空いてしまいました。

      ご質問に回答しますね。
      (既に解決されている場合はご容赦を)

      ■ご質問
      条件分岐<j = i -1> は<j = i >ではダメ?

      ■回答
      ダメではないですが、処理が遅くなります。

      <j = i >でもソートされます。
      しかし、
      最後の箱は確定しているので比較する必要がないのです。
      このため、
      <j = i -1>
      とした方が無駄な比較しないので処理が早い
      となります。

      回答になっていますでしょうか?
      ITパスポートの合格をお祈りしております。

      ココナラでもサポートしておりますので、もしよければお立ち寄りくださいませ。
      初心者向けプログラミングの基本を教えます

コメントを残す

*