 |
| 図．１ 最も単純なソートアルゴリズム |
|---|
いきなりアホな題ですみません。まぁ、そういうわけで今回からはソートをやってみたいと思います。ソートというのは、データを順番に並べ替えることです。いろいろなところで使うことがあるでしょう。
では、今回の要点をどうぞ。
では、いってみましょう。
データを順番通りに並び替えることをソートといい、いろいろなところで使われます。先ず今回は難しいことを考えず、心の赴くままにソートしてみます。
次のようなデータがあるとします。
| プログラム１ |
|---|
// SortData.cpp
#include "MainDefs.h"
// ソートするデータ
int g_anData[] = {
117, 169, 99, 168, 48, 128, 1, 155, 39, 101,
54, 150, 173, 174, 9, 76, 55, 77, 186, 213,
16, 175, 14, 173, 78, 228, 231, 254, 4, 255,
23, 34, 185, 192, 118, 99, 25, 112, 51, 6,
235, 13, 103, 137, 67, 167, 240, 40, 249, 10,
124, 166, 89, 157, 228, 73, 28, 138, 188, 39,
152, 31, 40, 160, 51, 117, 240, 44, 29, 79,
215, 87, 63, 68, 41, 9, 110, 33, 148, 11,
229, 137, 56, 199, 242, 222, 1, 79, 239, 101,
53, 161, 116, 164, 73, 42, 203, 15, 249, 136,
};
// ソートするデータの数
int g_nNumOf = numof(g_anData); |
| プログラム２ |
// SortData.h #ifndef __SORTDATA_H__INCLUDED__ #define __SORTDATA_H__INCLUDED__ extern int g_anData[]; // ソートするデータ extern int g_nNumOf; // ソートするデータの数 #endif |
| プログラム３ |
// MainDefs.h #ifndef __MAINDEFS_H__INCLUDED__ #define __MAINDEFS_H__INCLUDED__ // 配列の要素数を取得 #define numof(array) (sizeof (array) / sizeof *(array)) #endif |
このデータ g_anData を小さい方から大きい方へとなるように並べ替えてみましょう。インデックスが増えるに連れて値が大きくなっていくので、このような順番を昇順と呼びます。その逆は降順です。
簡単に考えると、データを全部見て一番大きいのを最後に持っていき、次にそれを除いてデータを全部見てその中で一番大きいのを最後から２番目に置く、というような作業を（データの個数−１）回すればいいですね。最後はデータが１個になるので、データの個数回まではする必要はありません。
一番大きいものを探し最後に置くという操作は、次のようにすることができます。先ず、頭の方から隣同士のデータを比較していきます。そして右の方（インデックスの大きい方）が大きいときはそのまま放っておき、左の方（インデックスの小さい方）が大きいときはデータを交換します。これを続けていくと、一番大きいデータが一番右にやってきますね。
次は範囲を１つ狭めて、また頭から比較していきます。同じようにやっていくと、今度は次に大きいデータが右から２番目にやってきますね。これを続けていくとデータをソートすることができます。
これを図にすると、下図のようになります。
|
| 図．１ 最も単純なソートアルゴリズム |
|---|
一番大きいデータが泡が昇っていくかのように浮き出てくるので、このソート方法をバブルソートと呼びます。
ということでプログラムを組んでみましょう。
| プログラム１ |
|---|
// SortSub.h
#ifndef __SORTSUB_H__INCLUDED__
#define __SORTSUB_H__INCLUDED__
// 値の入れ替え
// temp 変数を仲介に、temp ← a ← b ← temp と
// データを移せば入れ替え完了です
inline void Swap(int& a, int& b)
{
int temp;
temp = a;
a = b;
b = temp;
}
// 配列の表示
void DispArray(const int* pnData, int nNumOf);
#endif |
| プログラム２ |
// SortSub.cpp
#include <stdio.h>
void DispArray(const int* pnData, int nNumOf)
{
const int PER_LINE = 10; // １行に表示する数
int i;
for(i = 0; i < nNumOf; i++)
{
// %3d の 3 は、最低３文字表示するという意味です
// １のときは " 1" というように、左に空白が入ります
printf("%3d, ", pnData[i]);
if(i % PER_LINE == PER_LINE - 1)
putchar('\n');
}
} |
| プログラム３ |
// Sort1.cpp
#include "SortData.h"
#include "SortSub.h"
// バブルソート
void BubbleSort(int* pnData, int nNumOf)
{
int iLoop; // （データの個数−１）回回すための変数
int iComp; // 比較するときのループ変数
// （データの個数−１）回回します
// 上の図を見れば、この回数も納得がいくでしょう
for(iLoop = 0; iLoop < nNumOf - 1; iLoop++)
{
// 比較を行い、大きい方のデータを左に持っていきます
// 初めは（データの個数−１）回で、一週毎に回数が減っていきます
for(iComp = 0; iComp < nNumOf - 1 - iLoop; iComp++)
{
// 比較して、左の方が大きければ交換
if(pnData[iComp] > pnData[iComp + 1])
Swap(pnData[iComp], pnData[iComp + 1]);
}
}
}
int main()
{
BubbleSort(g_anData, g_nNumOf);
DispArray(g_anData, g_nNumOf);
return 0;
} |
| 実行結果 |
1, 1, 4, 6, 9, 9, 10, 11, 13, 14, 15, 16, 23, 25, 28, 29, 31, 33, 34, 39, 39, 40, 40, 41, 42, 44, 48, 51, 51, 53, 54, 55, 56, 63, 67, 68, 73, 73, 76, 77, 78, 79, 79, 87, 89, 99, 99, 101, 101, 103, 110, 112, 116, 117, 117, 118, 124, 128, 136, 137, 137, 138, 148, 150, 152, 155, 157, 160, 161, 164, 166, 167, 168, 169, 173, 173, 174, 175, 185, 186, 188, 192, 199, 203, 213, 215, 222, 228, 228, 229, 231, 235, 239, 240, 240, 242, 249, 249, 254, 255, |
はい、ソートできました。
このソート方法は最も単純なものです。そして、最も遅い方法です。
しかし、データ数が少ないときは充分実用できます。ソート関数を自作して使いたいときは、簡単に作れる（＝バグの出にくい）バブルソートを使ってもいいでしょう。
他にも色々なソート方法が開発されています。それについては...次回以降にお話ししたいと思います。
では、今回の要点です。
それでは、次回まで。
第２３章 call itself ３ | 第２５章 たのしいソート２
Last update was done on 2000.9.13
この講座の著作権はロベールが保有しています