【C言語とPython】バブルソートの実装をわかりやすく解説してみた

Caliphです！

今回は、プログラミングの中でアルゴリズムを学ぶのに重要だと言われているソートについて、実装と説明をわかりやすくしていきます。

初心者の方は、すこし大変かもしれませんが頑張ってみましょう。

始めたばかりで、あまりよくわからないという方は、上の記事でプログラミングの基礎を勉強しましょう。

ソートとはどんなもの？

初めにソートの説明をします。

ソートとは、数字の列などをならべかえる作業のことを表しています。例えば、4,9,7,3,8,5,1という数字列があったとします。これを昇順に並び替えてみましょう。

4 9 1 7 3 8 5　

↓

1 3 4 5 7 8 9

このように、並び替えることができました。

並び替え方には、色々な方法がありますが、あなたはどのように並び替えましたか？

コンピュータで行うソートには色々な種類があります。今回はその中で1番わかりやすいバブルソートを説明していきます。

なぜソートを学ぶのか

ソートを実際に実装する前に、どうしてソートを学ぶのかを説明します。

プログラミンでは、実装するときに様々なアルゴリズムを使用するんです。（アルゴリズムとは、問題の解法や解く手法）今回の並べ替えもアルゴリズムですし、家計簿の計算も、消費税の計算も、時間の計算もアルゴリズムです。

そして、ソートは様々なアルゴリズムの基礎となっております。理解すると他のアルゴリズムにも応用することができるんです。これが、ソートの勉強を勧める1番の理由です。

先ほど紹介した数列の並び替えは、人間でも簡単にできましたよね？、むしろプログラミングをする方が時間がかかって非効率です。

しかし　、データベースの並び替えや様々なデータ解析を行うときに使用するデータの数は、数千から、数万になります。大規模なものだともっと多いかもしれません。このようなときに、人間が自分の頭を使って並び替えると、とんでもない作業時間になります。しかし、コンピュータを使用すると、このソートが一瞬で終了します。

バブルソートとは

有名なソートの種類

ソートには、以下のように様々な種類があります。

バブルソート
選択ソート
シェルソート
マージソート
クイックソート

この中でデータ数が多いときに、1番効率がよく並び替えることができるのはクイックソートです。しかし、バブルソートの方が、アルゴリズムを理解しやすく、プログラミング初心者には優しいので、今回はこちらの実装と解説を行います。

バブルソートの動き

それでは、実際のバブルソートの動きを以下に示します。また、数列は4 9 1 7 5を使用します。

[1回目] 4 9 1 7 5

[2回目] 4 9 1 5 7

[3回目] 4 1 9 5 7

[4回目] 1 4 9 5 7

[5回目] 1 4 5 9 7

[6回目] 1 4 5 7 9

このように、バブルソートでは、数列の後ろから、1つ左隣の数と比較を行い、左の数字の方が大きい場合に、入れ替えを行います。

1回目から3回目までの入れ替えが、数列を比較する作業の1周目です。しかし、まだ完全に入れ替えが成功していないので、2周目の入れ替えを数列の後ろから行います。

5回目の入れ替えで数列が昇順になった事が確認できたので終了です。

この要素数の数列だと、バブルソートがとても大変ですねw。

文字で説明しても、わかりづらいので、わかりやすい動画を以下に貼っておきます。

バブルソートをC言語で実装

以下に、C言語で実装したバブルソートのソースコードを示します。

このコードには関数が2つあります。1つはメイン関数、2つ目はshowdata関数です。これはプログラムの実行途中をわかりやすく表示するために私が書いたものなので、書いても書かなくてもどちらでも大丈夫です。

初めてソートのプログラムをみた人は、何がなんだか全くわかりませんよね？（笑）

そういうものなので安心してください！普通、このソートを見た瞬間に理解できる人なんかいません。そこで、渡しが用意したshowdata関数の出番です。以下の実行結果を見てみましょう。

0周目　6個目の入れ替え　　4 9 1 7 3 5 8 
0周目　4個目の入れ替え　　4 9 1 3 7 5 8 
0周目　2個目の入れ替え　　4 1 9 3 7 5 8 
0周目　1個目の入れ替え　　1 4 9 3 7 5 8 

1周目　5個目の入れ替え　　1 4 9 3 5 7 8 
1周目　3個目の入れ替え　　1 4 3 9 5 7 8 
1周目　2個目の入れ替え　　1 3 4 9 5 7 8 

2周目　4個目の入れ替え　　1 3 4 5 9 7 8 

3周目　5個目の入れ替え　　1 3 4 5 7 9 8 

4周目　6個目の入れ替え　　1 3 4 5 7 8 9

バブルソートの動きで説明した通り、一通り数列の入れ替えをした後に、何周も同じ作業を繰り返しています。この動きは、for文の中にfor文を書く多重ループという方法を使用しています。

出力結果には表示されていませんが、バブルソートではたくさんのループを行なっているので実は効率のあまりよくないソートなんです。