毎回ソートして表示するよりも、線形リストで途中に挿入していったほうが早いのではないかという結論になったのですが、
線形リストの代わりに配列を使った方が早いのではないかと思い、時間を測定してみました。
(こうなるとソートと呼ぶのはふさわしくない気がしますが)
配列は毎回全部のデータをfree、全部のデータをコピー、しなければならないので、一見遅そうに思えますが、測定してみて、意外な結果になりました。
3000回入力(rand()による自動入力)でソート表示、これを1000回行った計算時間です。
線形リストを使ったソート
計算時間 32.453秒
配列を使ったソート
計算時間 5.187秒
各測定に使用したコードはこちらです。大量にログが出てしまうので、printf文は省略してあります。
線形リストを使ったソート
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct node {
int data;
struct node *next;
} node_t;
//新規リストを作成．
node_t *list_new(void){
node_t *list;
if((list = (node_t *)malloc(sizeof(node_t))) == NULL)
exit(9);
list->next = NULL;
return list;
}
//node の後ろに，data を保持する節点を追加し，その節点を返す．
node_t *node_insert_after(node_t *node, int data){
node_t *new_node;
if((new_node = (node_t *)malloc(sizeof(node_t))) == NULL)
exit(9);
new_node->data = data;
new_node->next = node->next;
node->next = new_node;
return new_node;
}
//リスト解放
void list_delete(node_t *list)
{
node_t *node, *next;
for (node = list; node != NULL; node = next) {
next = node->next;
free(node);
}
}
int main(void){
int x;
node_t *list, *node,*copy;
clock_t t1,t2;
t1=clock();
for(int j=0;j<=1000;j++){
/*1回分のソートここから*/
list = list_new();
for(int i=0;i<3000;i++){
x = rand();
copy=list;
if(list->next==NULL){//一番最初なら
node_insert_after(copy,x);
}
else{
for (node = list->next; node != NULL; node = node->next){
if(node->data>x){//比較で見つかった値の一つ前に挿入
node_insert_after(copy,x);
break;
}
else if(node->next==NULL){//最後まで比較で見つからなかったら最後に挿入
node_insert_after(node,x);
break;
}
copy=node;
}
}
if(j%10==0)
printf("作業進行率%3d％\r",j/10);
}
list_delete(list);
/*ここまで*/
}
t2=clock();
printf("\n\n計算時間 %.3f秒\n",double(t2-t1)/1000);
return 0;
}
配列を使ったソート
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void sort(int *p,int num,int x){
int i,j;
for(i=0;i<num;i++)
if(p>x)
break;
for(j=num;j>=i;j--)
p[j+1]=p[j];
p=x;
return ;
}
int main(void){
int i,j,num=0,*p,x;
clock_t t1,t2;
t1=clock();
for(int s=0;s<=1000;s++){
p = (int *)malloc(sizeof(int)*(num+1));
for(int t=0;t<3000;t++){
x=rand();
if(num>0){
p=(int *)realloc(p,sizeof(int)*(num+2));
sort(p,num,x);
}
else p[0]=x;
num++;
}
if(s%10==0){
printf("作業進行率%3d％\r",s/10);
}
num=0;
free(p);
}
t2=clock();
printf("\n\n計算時間 %.3f秒\n",double(t2-t1)/1000);
return 0;
}私としてはこの結果から線形リストより配列を使うほうがかなり早いのかと思いましたが、どこかに無駄があるために線形リストが遅くなっていたりするのでしょうか・・。
この問題の解答として一番早いソートのしかたはなんなのか気になったので調べてみました。
何かご意見くだされば光栄です。
メニュー
カレンダー
Clock
最新メンバー
投稿数
統計データ
Link to us
カウンター