こんにちは、ナナです。
「ソート」とはデータを昇順や降順に並べ替えることを示します。
データを並べ替えるためのアルゴリズムはいくつもありますが、本記事では「バブルソート」と呼ばれる最も基本的なソート方法を紹介します。
本記事では次の疑問点を解消する内容となっています。
では、「バブルソート」について学んでいきましょう。
「ソート」とは何か？
プログラムにまだ慣れていない方は「ソート」という用語自体が聞きなれない単語かもしれません。
まずは、「ソート」とは何なのかを説明しましょう。
ソートとは情報を規則的に並べ替えること
とある規則に従って情報を並べ替えることを「ソート」と呼びます。
コンピュータの世界は「数」というもので全てを表現します。私たちの目には文字や画像で映るものであろうと、コンピュータの中では数で管理されているのです。
次のように「数」が書かれたカードが５枚あるとします。
「数」というものに着目した際の並べ替えで、最も代表例な規則は「昇順」と「降順」です。
このように「数」を順に並べ替えることを「ソート」と呼びます。
「ソート」を行うためのアルゴリズムはいろいろありますが、本記事では最も基本的な「バブルソート」を紹介します。
バブルソートのサンプルプログラムを紹介
C言語において「バブルソート」によるプログラムは、標準ライブラリ関数では提供されていません。
つまり、バブルソートによる並び替えをしたければ、皆さん自身でプログラムを作成することになります。
とはいっても、バブルソートは最も基本的なソートアルゴリズムですから、それほどプログラムすること自体は難しくありません。
プログラム初心者の勉強のための課題として、解かせることも多いプログラムです。
バブルソートの「昇順」「降順」プログラムの紹介
それでは、次のようにint型配列として並ぶ「数」を、バブルソートのプログラムで並び替えてみましょう。
int num[5] = {7, 1, 3, 8, 5};「昇順」と「降順」で一部異なる部分がありますが、次のプログラムで並び替えることができます。
昇順ソートのプログラム
#include <stdio.h>
int main(void)
{
int i, j;
int num[5] = {7, 1, 3, 8, 5};
int tmp;
// 昇順ソートのプログラム
for (i = 0; i < 5; i++)
{
for (j = i + 1; j < 5; j++)
{
if (num[i] > num[j])
{
tmp = num[i];
num[i] = num[j];
num[j] = tmp;
}
}
}
// 並べ替え結果の表示
for (i=0 ; i < 5 ; i++)
{
printf("%d ", num[i]);
}
return 0;
}1 3 5 7 8降順ソートのプログラム
#include <stdio.h>
int main(void)
{
int i, j;
int num[5] = {7, 1, 3, 8, 5};
int tmp;
// 降順ソートのプログラム
for (i = 0; i < 5; i++)
{
for (j = i + 1; j < 5; j++)
{
if (num[i] < num[j])
{
tmp = num[i];
num[i] = num[j];
num[j] = tmp;
}
}
}
// 並べ替え結果の表示
for (i=0 ; i < 5 ; i++)
{
printf("%d ", num[i]);
}
return 0;
}8 7 5 3 1実際に主となる並べ替え部分は２つのループ処理でできており、６行程度のプログラムであることがわかりますね。
これくらい簡単に並べ替えることができるのが「バブルソート」のプログラムなのです。
「昇順」と「降順」の違いは、大小関係を比較する向きが異なるだけであることがわかりますね。
バブルソートの並べ替え方法：考え方と工程を解説
それでは「バブルソート」のプログラムとはどのような工程で動いているのかを解説していきましょう。
ここで皆さんに学んで頂きたいことは、プログラムとはどのように考えて作り上げていくかのプロセス（工程）です。
並べ替えのプログラムに限らず、様々なプログラムを作り出すうえでどのような考え方で進めればよいのかを学んでいきましょう。
「数」を並べ替え変える作業の工程とは？
プログラミング初心者の方に「並べ替えを行うプログラムを作ってみましょう！」と課題を与えると、案外苦戦する方が多いです。
並べ替えのプログラムってどうしたらいいの？何から手を付けていいのか全然わからないわ・・・。何をどうしたら順に並ぶのかしら。
こんな時は落ち着いてほしいのです。
もし皆さんの目の前にトランプのカードがあって「昇順に並べ替えてみてください」といったら、できない方はいませんよね。
この時に「どのように考えて並べ替えたのですか？」と聞くと、多くの人がなかなか答えられないのです。
理由を答えられずとも、人間の持つ「脳」というスーパーコンピュータは、無意識でも並び替えを行ってしまうのです。
しかし、無意識でもできるということは、本来皆さんは「並べ替えの原理を知っている」ということです。
プログラミングとは、この無意識に並び替えた作業を明確な手順として認識することで可能になります。
トランプは並べ替えることはできるけど、プログラムになったとたん何をしたらいいのかわからなくなるのよね。なんでできないのかしら・・・。
皆さんはいったい何をどのように考えてトランプを昇順に並べ替えたのでしょうか？それをじっくりと考えてみるとよいですよ。
それが並び替えのアルゴリズムなのです。
無意識の作業を明確な手順として認識してみよう！
トランプのカードを元の配置に戻してみましょう。「昇順に並び替えなさい」となったときに皆さんは最初に何を考えたのでしょうか？
人によっては異なる可能性もありますが、多くの方はまず「全てのカードの中から最も小さな数字を探す」という作業を頭の中で行ったのではないでしょうか。
このように無意識に行った作業を手順として明確化し、工程を分解していきます。
さぁ、次に行う作業は見つけた「１」を左端に並べることですね。
これで一番左端の「数」は並べ替えが完了しました。次は残りの４枚に対して同じ作業を繰り返せばよいですね。
これで２番目の小さなカードが確定しました。これを残りのカードに順に繰り返していけば並べ替えが完了です。
どうでしたか？これが無意識に行っていた並べ替え作業を、明確な手順で表現するということなのです。
バブルソートのプログラムを解説
並べ替えの工程がわかったところで、プログラムでどのように実現しているかを考察してみましょう！
あらためて、並び替えを行っているプログラム部分を抜粋してみます。
int num[5] = {7, 1, 3, 8, 5};
for (i = 0; i < 5; i++)
{
for (j = i + 1; j < 5; j++)
{
if (num[i] > num[j])
{
tmp = num[i];
num[i] = num[j];
num[j] = tmp;
}
}
}このプログラムを次のように３つの部品に分けて解説します。
部品①：カードの確定場所を示すためのループ
部品①はループ処理となっています。このループは、その時点におけるカードを確定する場所を管理している部品です。
このループが１度回るとカードが１枚確定することになります。
左端から順に確定していくため、確定するたびにループカウンターは「０」から終端の「４」まで順にずれていきます。
このループが回りきることで、全てのカードが確定したことになりますね。
部品②：カードの中から最小の数を見つけ出す部品
部品②は小さなカードを見つけるための部品です。[i]が示す場所にあるカードを基準とし、残りのカードと順に大小関係を比較していきます。
ループカウンタの「j」の初期値が「i + 1」であるのは、基準カードの次のカードが残りのカードの始まり位置となるからです。
もしも大小比較の結果、基準カードより小さいカードが見つかった場合は、そのカードと基準場所のカードを入れ替えます。
これを残りのカード全てに実施することで基準カードが最も小さなカードになります。
部品③：２枚のカードを入れ替える部品
部品③は部品②の作業で、２枚のカードを入れ替える必要が出た場合に動作する部品です。
２枚のカード（変数）を入れ替える際に、次のようにプログラミングしてしまう方がいます。しかし、この方法はうまく動きません。
#include <stdio.h>
int main(void)
{
int num[2] = {10, 20};
// [0]と[1]を入れ替え
num[0] = num[1];
num[1] = num[0];
printf("num[0]:%d num[1]:%d", num[0], num[1]);
return 0;
}num[0]:20 num[1]:20num[0]とnum[1]が両方とも「20」になってしまいました。
何が起きているかを図示化してみましょう。
このようにプログラムの代入とはコピーとなるため、num[0]の「10」の数が代入時に消失してしまうのです。
この状態を回避するためには、消失前に別の変数へ数を退避させておくことです。tmp変数は退避用のデータを一時保管するための変数なのです。
このように入れ替えを行うためには、３つの変数を利用してコピー作業をローリングするようなイメージで入れ替えを行います。
バブルソートのプログラムとは
バブルソートの「バブル」とは「泡」のことです。
小さなデータが端から順に並んでいく姿は、まさしく「泡」のように順にデータが決まっていくことを表現しているのです。
これでバブルソートの仕組みがわかりましたね。
クイックソートによる並び替え方法
バブルソート以外に便利な標準ライブラリ関数として用意された「クイックソート」について知りたい人は『qsort関数の使い方【構造体データも並べ替えができる】』を参照しましょう。