C言語プログラミング2(挿入ソート)
ソート(sort)という単語をご存知でしょうか？
「整列」つまりばらばらの順番に並んだデータを並べ替えることを指します(コンピュータ系の世界だけかしら？)。
たとえば「３５１２９８７４６」というデータを「１２３４５６７８９」と変えることです。
このソートには様々なやり方(アルゴリズム)が考えられています。
今、ちょっとした機会がございまして、ソートのうちの定番と呼ばれるものを勉強しています。
せっかく勉強しているのでこちらにて紹介しようかと思いました。
役に立つかはわからないですが「もしかしたら知りたい人がいるかも」という理由でC言語にて書いたコードも掲載します。
知りたい人が0人だったらごめんなさい。
今回紹介するのは挿入ソートです。データが「３５１２４」のときの数値の変化例を()内に書きます。
・まず1番目と2番目を順番に並べる。「３５」
・3番目のデータをさきほどのデータの正しい位置に挿入する。「１３５」
・4番目のデータをさきほどのデータの正しい位置に挿入する。「１２３５」
・5番目のデータをさきほどのデータの正しい位置に挿入する。「１２３４５」
つまりだんだんと範囲を広げながら、データを正しい位置に「挿入」していく手法です。
挿入についてはどう行うかというと、「１２４５」に「３」を挿入する場合を以下に書いてみます。
・まず、「１２４５」の最後尾である「５」と「３」を比べる。
・「３」は「５」より小さいので「５」の左に「３」を入れる。
「１２４３５」となる。
・続いて「３」を左の「４」と比べる。
・「３」は「４」より小さいので「４」の左に「３」を入れる。
「１２３４５」となる。
・続いて「３」を左の「２」と比べる。
・「３」は「２」より小さくないので、挿入完了となる。
では、以下にC言語で書いた挿入ソートのプログラムを掲載します。
ソートを行う関数部分のみです。
/* 挿入ソート関数ここから */
/* data[]:データ格納配列 num:配列要素数 */
void sort(int data[],int num){
int i,j,temp;
for(i=1;i<num;i++){
temp=data[i];
/*temp以下の値が出るまで配列を右にずらす*/
for(j=i; j>0 && temp<data[j-1] ; j--)data[j]=data[j-1];
data[j]=temp;
}
}
/* 挿入ソート関数ここまで */
挿入ソートは単純でわかりやすいですが、基本的に計算時間が多くかかります。
ただし、「整列済みのデータが本当に整列されているか」を確認したいときは高速です。
(最初から整列されているときには、データが先頭の次から順番に「自分より一つ前」を見るだけで済むため)
Wikipedia ソート
Wikipedia 挿入ソート
Wikipedia C言語