スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

マージソート

マージソートのお勉強。
ポイントは、
・ブロックの大きさが完全に1になるまで分け続けること。
・ブロックの前半部分を、マージする前に一度buffという配列にコピーしている。
・配列のインデックスとして使用している変数がどこを指しているのか意識すると
マージソートを理解できる。
ここではkがマージして最終的に生成する配列arrayのインデックス
jが後半ブロックを指す
iが前半ブロック(arrayの前半をbuffにコピーしたもの)を指す

#include <stdio.h>
#include <time.h>

#define N 10
int array[N];

void disp(void){
int idx;
for(idx=0;idx<N;idx++)
printf("[%d]:%d\n", idx, array[idx]);
}

void merge_sort(int num, int array[]){
if(num < 2)
return;

int m = num/2;
merge_sort(m, array);
merge_sort(num-m, array+m);

int buff[num];
int i, j, k;
for(i=0;i<m;i++)
buff[i]=array[i];
i=k=0;
j=m;

while(i<m && j < num)
array[k++]=(buff[i]<array[j])? buff[i++] :array[j++];
while(i<m)
array[k++]=buff[i++];
while(j<num)
array[k++]=array[j++];
}



int main(void){

srand((unsigned int)time(NULL));
int idx;
for(idx=0;idx<N;idx++)
array[idx]=rand();
disp();
merge_sort(N, array);
puts("sort end");
disp();
}


スポンサーサイト
プロフィール

tjnet777

Author:tjnet777
Solaris, VPNのサポート業務を1年

金融系SIerで業務アプリの開発、メンテを3年半

離職して大学院大学 1年生

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QR
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。