C言語: 2006年12月アーカイブ
「C言語プログラミング2(挿入ソート)」に続きまして、またソート(つまりばらばらの順番に並んだデータを並べ替えること)のお話です。
今回ご紹介するのはシェルソート(改良挿入ソート)と言いまして、前回の挿入ソートの改良版です。
挿入ソートには「用意されているデータがある程度整列されているときは高速である」という長所がある代わりに「用意されているデータが整列状態と遠いほど低速となる」という欠点があります。
シェルソートはその欠点を改善するため、いきなり全体に挿入ソートをするのではなく、部分毎に挿入ソートを行います。
そして、その部分を徐々に広げていき、最終的にある程度整列された状態で挿入ソートをするというものです。
データが「８５４２６３７１」のときの数値の変化例を以下に書いてみます。
まず、データとデータの間隔を4として挿入ソートを行う。
・1番目の数値と5番目の数値で挿入ソート。「(６)５４２(８)３７１」
・2番目の数値と6番目の数値で挿入ソート。「６(３)４２８(５)７１」
・3番目の数値と7番目の数値を挿入ソート。「６３(４)２８５(７)１」
・4番目の数値と8番目の数値を挿入ソート。「６３４(１)８５７(２)」
次に、データとデータの間隔を2として挿入ソートを行う。
・1番目から3番目と5番目と7番目の数値で挿入ソート。「(４)３(６)１(７)５(８)２」
・2番目から4番目と6番目と8番目の数値で挿入ソート。「４(１)６(２)７(３)８(５)」
次に、データ間隔1として挿入ソートを行う。
・全データでの挿入ソート。「１２３４５６７８」
以下、C言語で書いたシェルソートのプログラムを掲載します。
ソートを行う関数部分のみです。
/* シェルソート関数ここから */
/* data[]:データ格納配列 num:配列要素数 */
void sort(int data[],int num){
int i,j,n,temp;
for(n=num/2;n>0;n=n/2){/*間隔を徐々に狭めていく 最終的には1*/
for(i=n;i<num;i++){/*nで決まっている間隔で一つずつ挿入ソート*/
temp=data[i];
/*temp以下の値が出るまで配列を右にずらす*/
for(j=i;j>n-1;j=j-n){
if(temp>data[j-n])break;
data[j]=data[j-n];
}
data[j]=temp;
}
}
}
ソート(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;
}
}
/* 挿入ソート関数ここまで */
挿入ソートは単純でわかりやすいですが、基本的に計算時間が多くかかります。
ただし、「整列済みのデータが本当に整列されているか」を確認したいときは高速です。
(最初から整列されているときには、データが先頭の次から順番に「自分より一つ前」を見るだけで済むため)
今年も残りあとわずか、いかがお過ごしでしょうか？
わたしはまたまた風邪をひいていたりします。困るぐらいに声が出ない日が続きました。
あまり声を出さないようにしてクールを装いながら、クールと無口は違うんだなと実感する日々だったりします。
そんなわたしの最近のマイブームが「綺麗なC言語プログラム」です。
C言語という単語、知らない人もけっこういらっしゃいますでしょうか。
多々あるプログラム言語の中でもかなりメジャーな一つなので、知っている方の方が多いかなと勝手に推測しています。
約三十年前に生み出され、現在も第一線で使われているプログラム言語です（C++やJavaとの関連も含め、第一線と表現させていただきました）。
言語としては長い歴史を持っているため、もちろんかなり研究されています。
プログラミングのコンテスト等もありますので。
そんなC言語において、単純な処理を少しでも綺麗に書きたいというのが最近のマイブームなんです。
間違いなくすでに誰かが考えついていることなので、それほど生産性がある行為だとは思っていません。
パズルを解くのと同じような感覚の趣味です。
ただ、ここに書くことでどこかの誰かの役に立ったら良いなぐらいは思います。
ちなみに、綺麗なプログラミングの定義は特にないですが
「提供されている標準ライブラリをあまり用いずできるだけ少ない手順で処理を完了する」
みたいなところでしょうか。
「経験の浅い寿司職人が握り寿司一つに七手かけるのに対して達人は三手しか用いない」みたいなものです。
ただ、わたしは寿司一つに八手かけるぐらいの実力なので、ここに掲載するコードが綺麗だなんて胸を張りはしません。
自分なりの綺麗なソースです。
今回はそんな中で「四捨五入」と「桁数カウント」の二つのコードを掲載します。
※注意
入出力にprintfとscanfを用いているのはポピュラーだからで、ベストだからではありません。
メイン処理のアルゴリズムを考えるのが趣味のため、例外処理は考慮していません。
/*以下、キーボードから入力した正の整数を四捨五入するプログラム*/
#include<stdio.h>
/*指数演算関数 aのb乗*/
int mul(int a,int b){
int c,d=1;
for(c=0;c<b;c++)d*=a;
return d;
}
int main(void){
int a,b;/*a:入力した数値 b:四捨五入対象部分*/
int pla=2;/*整数何桁目で四捨五入するか*/
scanf("%d",&a);
b=a%mul(10,pla);/*pla桁分の数値の取得*/
a=a-a%mul(10,pla)+mul(10,pla)*(b/(mul(10,pla)/2));
printf("%d",a);
return(0);
}
/*以下、キーボードから入力した正の整数の桁数をカウントするプログラム*/
#include<stdio.h>
int main(void){
int a,b=0;
scanf("%d",&a);
while(a>0){
b++;
a/=10;
}
printf("%d",b);
return(0);
}