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

Caliphです!

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

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


c言語の入門方法を、どんな方でもわかるように、まとめました。 また、具体的に勉強することなどもまとめていますので、読めば誰でも、c言語がかけるようになります。

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

ソートとはどんなもの?

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

ソートとは、数字の列などをならべかえる作業のことを表しています。例えば、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文を書く多重ループという方法を使用しています。

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

バブルソートをPythonで実装

以下に、Pythonで実装したc言語のコードを示します。

少し動作が異なるのでちゃんとした比較にはなりませんが、C言語と比べてとても少ないコードで実装できていますね!

基本的な動きはC言語と同じです。ので説明は省略します。

C言語は、処理がとても早く、速度が必要なプログラムの実装に便利ですが、コードの量が多いので気軽にコーディングしたり、大規模なプログラムには向きません。

こちらは、すでに基礎的なC言語が使用できる人向けに書いた、Pythonの記事です。

この記事を読むとPythonが60分で習得できます!!!

今回Pythonのコードをみて、興味が湧いた人はぜひ習得しましょう。

c言語やc++などのプログラミングをしたことがある人向けに、pythonの使い方をこれでもかというほど省略して説明をしている記事です。

まとめ

ソートの実装はどうでしたか?

少しでも楽しいと感じたなら、競技プログラミングの大会に出場することを勧めます!!atcoderなど、初心者から上級者までが一緒に楽しめる大会がたくさんありますので、参加しましょう。

難しいと思ったり、理解できない人もいると思います。その方は諦めず、コードを自分で書いてみたり、基礎からやり直してみましょう。いつかできます。