バブルソートで降順、ランダム順に並んでいるデータを読み込ませて昇順に並び替える実行時間について質問です。

バブルソートにおける計算時間は、データ数が多いほど、並び替える回数が多いほど長くなるはずですが、実際に実行したところ、並び替える回数が多いはずの降順のほうがランダム順よりも早くなりました。

なぜこのようになるのですか?

よろしくお願いします。

A 回答 (6件)

CPUの分岐予測が原因ではないでしょうか。


※分岐予測についてはWikipediaを参照してください。

逆順のデータに対しては、常に入れ替え動作をします。
分岐予測の種類によりますが、常に「実行されるとCPUが予測している」なら、パイプラインを最大限に活用して高速な処理を実現できます。

一方、ランダムなデータであれば、分岐結果が一定ではないので予測の失敗が多発します。この場合パイプラインを生かし切れずに性能が劣化します。

今回の場合入れ替え動作自体がごく単純であるがために、予測に失敗することによるオーバーヘッドのほうが大きくなっているのでしょう。

期待する結果を得るには、入れ替え動作自体のオーバーヘッドが大きくなるようにする必要があります。たとえば大きな構造体を使うようにします。

ただし、普通大きな構造体などを利用する場合、ポインタを使います。ポインタであれば入れ替えのオーバーヘッドが小さくなります。
結局、
「適切な分岐予測をするCPUでのバブルソートでは、逆の順序に並べたデータの処理は、ランダムに並んだデータよりも早い」
という結論になります。

参考URL:http://ja.wikipedia.org/wiki/%E5%88%86%E5%B2%90% …
    • good
    • 0
この回答へのお礼

回答ありがとうございます。

s117さんの回答と補足資料を見る限り、これが原因であるとみて間違いないようですね。
CPUにはそのような機能もあるんですね、勉強になりました。

ご回答いただきありがとうございました。

お礼日時:2009/05/17 01:28

>このif文を何回実行しているかを数える方が、



これは正確な回答ではありませんでした。
「このif文を実行した結果が何回真になったか」が正しいです。
つまり、降順にきれいに並んでいるデータと
ランダムに並んでいるデータとで、
実際の入れ替え処理を何回実行したか、を比べてみては?ということです。

この回答への補足

回答ありがとうございます。

if文の下にカウンターをつけて実行したところ、
ランダム順 約25億
降順    約 7億
という結果になりました。

これはコンパイラの処理の仕方によって異なるのかなと考えましたが、s117さんの回答と資料を拝見したところ、CPUの分岐予測が原因ではないかという結論にたどり着きました。

何度もご回答いただき、ありがとうございました。

補足日時:2009/05/17 01:21
    • good
    • 0
この回答へのお礼

すいません、こちらに書くべきでしたね。

何度もご回答いただき、ありがとうございました。

お礼日時:2009/05/17 01:24

ソート後のデータを出力するよりも、



>if(str[j-1]>str[j]){

このif文を何回実行しているかを数える方が、
問題解決にとって有益かもしれません。
    • good
    • 0

>バブルソートの部分のソースを提示させていただきます。



提示された箇所以外はこちらで勝手に書いてもいいのですか?
当方で、あなたのところとできるだけ同じ条件で実験するためには、
お手持ちのコードを「そっくりそのまま」載せてくださる方がよいと思います。
いかがでしょうか。

この回答への補足

申し訳ございません。ソースコード全体を提示させていただきます。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int main(int argc,char **argv){
int i,j,temp;
int count=0;
int str[1000000];
clock_t c_start,c_end;
FILE *fp;

if(argc!=2){
fprintf(stderr,"File has not been opened\n");
exit(1);
}

if((fp=fopen(argv[1],"r"))==NULL){//ファイルを読み込む
fprintf(stderr,"File has not been opened\n");
exit(1);
}

while(fscanf(fp,"%d",&str[count]) != EOF) {//EOFまで1行づつデータを読み込む
count++;
}

c_start=clock();//クロックスタート

for(i=0;i<count;i++){//バブルソートを行う
for(j=count;j>i;j--){
if(str[j-1]>str[j]){
temp=str[j];
str[j]=str[j-1];
str[j-1]=temp;
}//End if
}//End for j
}//End for i

c_end=clock();//クロックストップ

printf("permute it in ascending order\n");

for(i=0;i<count;i++) printf("%d\n",str[i]);//ソート後のデータを出力する

printf("Time:%f\n",(double)(c_end-c_start)/CLOCKS_PER_SEC);//実行時間の出力

return 0;

}//End main

よろしくお願いします。

補足日時:2009/05/16 20:50
    • good
    • 0

どういったソースコードで実験されたかを提示してください。

この回答への補足

回答ありがとうございます。

バブルソートの部分のソースを提示させていただきます。

c_start=clock();//クロックスタート

for(i=0;i<count;i++){//count=データ数
for(j=count;j>i;j--){
if(str[j-1]>str[j]){
temp=str[j];
str[j]=str[j-1];
str[j-1]=temp;
}//End if
}//End for j
}//End for i

c_end=clock();//クロックストップ

なお、他のソースコードで実験した人も同様の結果になったので、ソースコードが原因ではないと考えています。

補足日時:2009/05/16 20:40
    • good
    • 0

>なぜこのようになるのですか?



測定方法(データ数はいくつなのか?、
1回の測定か0、何回かの平均値か?等)、
及び測定環境(CPU, メモリ、OS等)が明示されていないので、
原因は分かりません。

可能性をあげることはできます。

例えば、降順、ランダム、1回きりの場合で
Windows上でシングルCPU(HTもない)で測定した場合に、
たまたま、ランダム測定中に別プロセスにタスク・スイッチが切り替わった。
GetTickCount()での時間測定なので、
他のタスク実行時間も含めて評価してしまった。

とか、

データ数がCPUのキャッシュに全部収まる範囲だったので
後に実行した場合は、キャッシュアクセスで済んでしまった。

等々

何回かの平均をとらないと、比較に耐えるデータにはならないと
おもいますが、平均をとったかいなか文章からは読み取れません。

条件を明示してください。

この回答への補足

回答ありがとうございます。条件が不足していてすいません。

データ数は100000個でそれぞれ3回ずつ実行しました。これは学校の実験で行ったのですが、他の人も同じ結果になっていました。(バブルソートのソースはみんなバラバラです)

OSはLINUXです。メモリ、CPUはわかりません。

使用したコンパイラはgccで、emacsを使用しました。

よろしくお願いします。

補足日時:2009/05/16 20:30
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

QVBでのバブルソートの課題です。

VBでのバブルソートの課題です。


まったくの初心者でパソコン自体苦手なので何がなんだかわかりません。
型宣言?とセル?の意味もよくわかりません…
課題は↓です…締め切りが今日の夜9時までなんです…
どなたか手を貸していただけませんか…

次のように並んでいる数列をバブルソートを用いてソートしなさい。
9 6 7 1 2
途中の過程もシート上に出力すること。

Aベストアンサー

>VBでの
セル?という言葉が出ているのでエクセルVBAでしょう。VBと核になる点(文法など)は同じですが、全体では別物なので正確に書いておくこと。
>型宣言?
プログラム言語でプログラムするとき、データは一旦変数という記憶領域に蓄えます。
そのデータ性格や記憶域の長さを決めるのが、型宣言です。ーー>データ型を宣言する
VBAはVB6に当たるので、Googleででも「VB 型宣言」で照会すると沢山解説が有るが、
http://hanatyan.sakura.ne.jp/vbhlp/hensu.htm
の変数の型の種類などを読むこと。
質問者の今の情況では、整数型と文字列型を使う例題が多いだろう。
>バブルソート
Googleでも「バブルソート」で照会して記事を読むこと。バブルは水の泡のことで、泡は水中の下のほうに発生すると上に浮かび上がってくる。このイメージから命名されている。
http://aitech.ac.jp/~koikelab/webp/vba/vba_9.html
など
この隣接(セル)交換法でやってみる。
エクセルのシートにA1:A5に
9
6
7
1
2
があるとすると、隣接交換法であるから1行目と2行目を比較して、小さいほうを上行に持っていく。次に2行目と3行目を比較するが、2行目は置き換わった後のデータである場合もある。
それに並べ替え完了をどう理解するかも初心者には難しい。
一回下行まで行くと1つの最大値が決ると理解すると良い。
上記のWEBの下から最大値が確定していく様を見て考えてください。
あまりなれない課題でミス無きを祈るが
Sub test01()
j = 1
k = 4
p1:
For i = 1 To k
Range(Cells(1, j), Cells(5, j)).Copy Range(Cells(1, j + 1), Cells(5, j + 1))
j = j + 1
If Cells(i, j) < Cells(i + 1, j) Then
'そのまま
Else
'Cells(i, j) > Cells(i + 1, j)
w = Cells(i, j) '大
Cells(i, j) = Cells(i + 1, j) '小を上に
Cells(i + 1, j) = w '大を下に
End If
Next i
k = k - 1
If k = 0 Then
Exit Sub
End If
GoTo p1
End Sub
Goto文を使わないのが普通らしいが、繰り返しの仕組みのステートメントを使わないためにあえて使った。
ーー
途中経過(上記実行結果)
エクセルシート
96666666111
69777711622
77911172266
11192227777
22229999999
9確定7確定6確定2確定
>途中の過程もシート上に
先生は理解のために言ったのだろうが、エクセルVBAをよく知ってないとうまく行かないし、簡単な課題ではないし、バブルソートの理解とは別の技法だと思う。
バブルソートの考えやコードが霞んでしまうと思うが、上記には組み込んだので判りにくくなっている  部分があるだろう。
ーーーー
エクセルでやるのは、入力や途中経過や最終結果出力を記録出来て見やすいが、VBAの知識が少し要るということ。

>VBでの
セル?という言葉が出ているのでエクセルVBAでしょう。VBと核になる点(文法など)は同じですが、全体では別物なので正確に書いておくこと。
>型宣言?
プログラム言語でプログラムするとき、データは一旦変数という記憶領域に蓄えます。
そのデータ性格や記憶域の長さを決めるのが、型宣言です。ーー>データ型を宣言する
VBAはVB6に当たるので、Googleででも「VB 型宣言」で照会すると沢山解説が有るが、
http://hanatyan.sakura.ne.jp/vbhlp/hensu.htm
の変数の型の種類などを読むこと。
質問者の今...続きを読む

Q配列をランダムに並び替えてもとに戻したい

C言語のプログラミングで質問があります。

ある配列をランダムに並び替えて、ある処理をした後にまた元の配列の順番に戻したいと考えているのですが、どのように組めばいいのか解りません。

回答をお願い致します。

Aベストアンサー

ポインタを使えばよいのではないでしょうか?

並び替えたい配列を int A[100] と仮定して、
アドレスを入れておく一時的な配列、int *B[100]を用意して、
for( i = 0; i < 100; i++ ) B[ i ] = &A[ i ];
としておきます。

あとは、B[]の要素をランダムに入れ替え、
何らかの処理を *B[ i ] に対して行えばよいですね。

これであれば、元のA[]の内容は変わりますが、
順番は一切変わりませんので、面倒な操作は発生しません。

Qバブルソートの実行時間について

バブルソートで降順、ランダム順に並んでいるデータを読み込ませて昇順に並び替える実行時間について質問です。

バブルソートにおける計算時間は、データ数が多いほど、並び替える回数が多いほど長くなるはずですが、実際に実行したところ、並び替える回数が多いはずの降順のほうがランダム順よりも早くなりました。

なぜこのようになるのですか?

よろしくお願いします。

Aベストアンサー

CPUの分岐予測が原因ではないでしょうか。
※分岐予測についてはWikipediaを参照してください。

逆順のデータに対しては、常に入れ替え動作をします。
分岐予測の種類によりますが、常に「実行されるとCPUが予測している」なら、パイプラインを最大限に活用して高速な処理を実現できます。

一方、ランダムなデータであれば、分岐結果が一定ではないので予測の失敗が多発します。この場合パイプラインを生かし切れずに性能が劣化します。

今回の場合入れ替え動作自体がごく単純であるがために、予測に失敗することによるオーバーヘッドのほうが大きくなっているのでしょう。

期待する結果を得るには、入れ替え動作自体のオーバーヘッドが大きくなるようにする必要があります。たとえば大きな構造体を使うようにします。

ただし、普通大きな構造体などを利用する場合、ポインタを使います。ポインタであれば入れ替えのオーバーヘッドが小さくなります。
結局、
「適切な分岐予測をするCPUでのバブルソートでは、逆の順序に並べたデータの処理は、ランダムに並んだデータよりも早い」
という結論になります。

参考URL:http://ja.wikipedia.org/wiki/%E5%88%86%E5%B2%90%E4%BA%88%E6%B8%AC

CPUの分岐予測が原因ではないでしょうか。
※分岐予測についてはWikipediaを参照してください。

逆順のデータに対しては、常に入れ替え動作をします。
分岐予測の種類によりますが、常に「実行されるとCPUが予測している」なら、パイプラインを最大限に活用して高速な処理を実現できます。

一方、ランダムなデータであれば、分岐結果が一定ではないので予測の失敗が多発します。この場合パイプラインを生かし切れずに性能が劣化します。

今回の場合入れ替え動作自体がごく単純であるがために、予測に失...続きを読む

Qc言語のプログラミングの問題で50以下の正の偶数を降順(大きい順)で表示するプログラムを作成できる方

c言語のプログラミングの問題で50以下の正の偶数を降順(大きい順)で表示するプログラムを作成できる方お願いします

Aベストアンサー

No3の方から既に回答がでていますが、別解です。
#include <stdio.h>

int main()
{
printf("50\n");
printf("48\n");
printf("46\n");
printf("44\n");
printf("42\n");
printf("40\n");
printf("38\n");
printf("36\n");
printf("34\n");
printf("32\n");
printf("30\n");
printf("28\n");
printf("26\n");
printf("24\n");
printf("22\n");
printf("20\n");
printf("18\n");
printf("16\n");
printf("14\n");
printf("12\n");
printf("10\n");
printf("8\n");
printf("6\n");
printf("4\n");
printf("2\n");
return 0;
}

以下、実行結果です。
------------------------------------
50
48
46
44
42
40
38
36
34
32
30
28
26
24
22
20
18
16
14
12
10
8
6
4
2

No3の方から既に回答がでていますが、別解です。
#include <stdio.h>

int main()
{
printf("50\n");
printf("48\n");
printf("46\n");
printf("44\n");
printf("42\n");
printf("40\n");
printf("38\n");
printf("36\n");
printf("34\n");
printf("32\n");
printf("30\n");
printf("28\n");
printf("26\n");
printf("24\n");
printf("22\n");
printf("20\n");
printf("18\n");
printf("16\n");
printf("14\n");
printf("12\n");
printf("10\n");
printf("8\n");
printf("6\n");
printf("...続きを読む

Q挿入ソートとバブルソート

挿入ソートとバブルソートについて教えてください。どのようなアルゴリズムでソートされるのでしょうか?

Aベストアンサー

下記のページが参考になりませんか。

C言語によるアルゴリズム(コメント付き)http://www.sra.co.jp/people/miyata/algorithm/

並べ換えの問題
 http://www.cs.u-gakugei.ac.jp/~miyadera/Education/Lecture/ElecBook2/ptech17.htm

Q単語の出現回数を数え、出現回数順に表示するには?

標準入力または入力ファイルから単語の出現回数を調べるプログラムの一部です。ENTRY *add_entry(ENTRY *new)関数で以前に出てきた単語か(正確には以前に同一内容の行があったかを)判断し、既出ならばvoid do_one(FILE *fp)関数内部でp->count++として出現回数に加算しています。void do_one(FILE *fp)関数の最後の方のprintfで単語とその出現回数を表示します。これだとappleという単語が2回出てくれば、
apple:1
apple:2
と表示されます。この場合は
apple:2
だけ表示させ、さらに、出現回数の多い順に単語を並べて表示させたいんです。どういう風にすればいいでしょうか?

typedef struct entry_t {
char *str;
struct entry_t *next;
int count; /* 単語の出現回数 */
} ENTRY;

int main(int argc, char **argv)
{
FILE *fp;
char *s;
init_hash();
--argc;
++argv;
if (argc == 0)
do_one(stdin);
else {
while (argc--) {
if ((fp = fopen(*argv, "r")) == NULL)
cant(*argv); /* no return */
do_one(fp);
fclose(fp);
argv++;
}
}
free_all_entries();
return (0);
}

void do_one(FILE *fp)
{
ENTRY *p;
char buf[MAX_SIZE];
int i;

while (fgets(buf, MAX_SIZE, fp) != NULL) {
if ((p = malloc(sizeof(ENTRY))) == NULL)
error("can't alloc memory"); /* no return */
if ((p->str = strdup(buf)) == NULL)
error("can't alloc memory"); /* no return */
if (add_entry(p) != p) {
p->count++;/* 登録済みなので単語の出現回数を1増やす */
free(p->str); /* すでに登録されているので開放 */
free(p);
}
else/* 新しく単語を登録する場合 */
p->count =1;/* 単語の出現回数を1にする */
printf("%s : %d\n", p->str, p->count);
}
}

void init_hash(void)
{
int i;

for (i = 0; i < HASHSIZE; i++)
table[i] = NULL;
}

ENTRY *add_entry(ENTRY *new)
{
ENTRY *p;
int h;

h = hash(new->str); /* 追加する単語のハッシュ値を求める */
for (p = table[h]; p != NULL; p = p->next)
if (strcmp(p->str, new->str) == 0) {/* 追加済みの単語ならば */
return (p);/* そのデータのポインタを返す */
}
new->next = table[h];
table[h] = new;/* 単語を追加する */
return (new);
}

標準入力または入力ファイルから単語の出現回数を調べるプログラムの一部です。ENTRY *add_entry(ENTRY *new)関数で以前に出てきた単語か(正確には以前に同一内容の行があったかを)判断し、既出ならばvoid do_one(FILE *fp)関数内部でp->count++として出現回数に加算しています。void do_one(FILE *fp)関数の最後の方のprintfで単語とその出現回数を表示します。これだとappleという単語が2回出てくれば、
apple:1
apple:2
と表示されます。この場合は
apple:2
だけ表示させ、さらに、出現回数の多い順に単...続きを読む

Aベストアンサー

(英単語限定!)

★配列を使ったら「簡単」では・・?
 (短所:オーバーフロー(▼)の都度、要調整)

#define MAXCNT (2000) // ▼
#define un_char unsigned char // 大小比較あるため
int igStoreCnt = 0; // 出現単語カウンタ(グローバル)
typedef struct{
 un_char cStr[16]; // 1単語16文字以内
 int iCount; // 当単語の出現回数
}ENTRY;
ENTRY sStore[MAXCNT]; // 単語収録(▼)

★まず読み込んだ1行を単語毎(◆)に分割
int OneLineWordCount( un_char cBuf[] )
{
 int i, iTop, iLen = 0;

 for( i = 0; i < 2048; i++ ){ // レコード長 2048 以内

  if( 0x09 == cBuf[i] ) cBuf[i] = 0x20; // タブ
  if( 0x0D >= cBuf[i] ){ // 行末

   if( iLen ) WordCount( iTop, cBuf, i ); // ◆

   return( 0 );
  }
  if( 0x27 == cBuf[i] ) continue; // 例) it's の '

  if( ! isalpha( cBuf[i] ) ){ // デリミタ
   if( 0 == iLen ) continue;

   WordCount( iTop, cBuf, i ); // ◆

   iLen = 0;
   continue;
  }
  if( 0 == iLen ) iTop = i;
  iLen++;
 }
 return( 0 );
}

★カウント部分
int WordCount( int iTop, un_char cBuf[], int iii )
{
 int k;

 cBuf[iii] = 0x00;

 for( k = 0; k < igStoreCnt; k++ ){

  if( NULL == strcmp( sStore[k].cStr, &cBuf[iTop] ) ){

   sStore[k].iCount++; // 既存

   return( 0 );
  }
 }
 strncpy( sStore[igStoreCnt].cStr, &cBuf[iTop], 16 );

 sStore[igStoreCnt].iCount = 1; // 新単語

 igStoreCnt++;

 if( MAXCNT < igStoreCnt ) ErrorStop( "Over" ); // ▼

 return( 0 );
}

★出力部分(同数の場合出現順)
void Ranking( void )
{
 int k, j, iMax, iBasyo;

 for( k = 0; k < igStoreCnt; k++ ){

  iMax = 0;

  for( j = 0; j < igStoreCnt; j++ ){

   if( sStore[j].iCount > iMax ){

    iMax = sStore[j].iCount;

    iBasyo = j;
   }
  }
  printf( "%4d ", k );
  printf( "%-16s", sStore[iBasyo].cStr );
  printf( "%3d\n", sStore[iBasyo].iCount );

  sStore[iBasyo].iCount = 0; // 用済み
 }
}
void ErrorStop( un_char *cMess )
{
 fprintf( stderr, "Err %s\n", cMess );

 exit( 0 );
}
注:インデントに全角空白を使用しています。

(英単語限定!)

★配列を使ったら「簡単」では・・?
 (短所:オーバーフロー(▼)の都度、要調整)

#define MAXCNT (2000) // ▼
#define un_char unsigned char // 大小比較あるため
int igStoreCnt = 0; // 出現単語カウンタ(グローバル)
typedef struct{
 un_char cStr[16]; // 1単語16文字以内
 int iCount; // 当単語の出現回数
}ENTRY;
ENTRY sStore[MAXCNT]; // 単語収録(▼)

★まず読み込んだ1行を単語毎(◆)に分割
int OneLineWordCount( un_char cBuf[] )
...続きを読む

Qバブルソートとクイックソート

まだソートについて勉強し始めたばかりですが
バブルソートは対象の総数が増えるとそれに伴い比較回数は増加するのに対し
クイックソートはそれほど増加しないのはなぜでしょうか??
検索してみてもプログラムが書いてあってよくわからないので...

根本的なところなのでしょうがどなたか教えてください!

Aベストアンサー

では「計算量」というキーワードも追加して検索してください。
また、計算量を表わすのに使われる「オーダー」「ランダウの漸近記法」についても調べてみてください。

おおざっぱに言うと

まじめに比較すれば、
一つ目と残りn-1個の比較
2つ目とそれ以降のn-2個の比較
...
と、要素数nの二乗に比例した回数の比較必要です。これがバブルソートの計算量です。

これを、大きいもの方と小さい方の半分に分けてそれぞれを並び変えれば、
1つの並び換えが(n/2)の二乗= 1/4 * nの2乗
それが大と小の2回で * 2
合わせて 1/4 * nの2乗 * 2
= 1/2 * nの2乗
とバブルソートの半分になります。その半分のものを更に半分に...とやっていくと、最後には n * log2 n に比例する値になります。 これが、クイックソートの計算量です。(正確には平均ですが)

細かい点は省略しているので、最初に書いたような検索の結果や、「アルゴリズム」について詳しく書かれた専門書などを読んでください。

Q双方向リストのバブルソートについて

双方向リストをバブルソートを用いてソートしたいです。
下記がプログラム(一部)ですが、ソートした後にリスト表示すると
無限ループに陥ります。
どこがいけないのでしょうか。

#include <stdio.h>
#include <stdlib.h>

struct cell{
int data;
struct cell *next, *prev;
};

void insert_head(struct cell **head, int num){
struct cell *p, *p1;

p = *head;
p1 = make_cell();
*head = p1;
p1->data = num;
p1->next = p;

if(p1->next != (struct cell *)NULL){
p1->next = p;
p->prev = p1;
}
}

void print_list(struct cell *head){
struct cell *p;

p = head;
printf("data = \n");
while(p != (struct cell *)NULL){
printf("%d\n", p->data);
p = p->next;
}
}

void sort_list(struct cell **head){
struct cell *p, *p2;
int i, n;

n = 0;
p = *head;
while(p->next != (struct cell *)NULL){
p = p->next;
n++;
}

for(i = 0, p = *head; i < n-2; i++){
if(p->data > p->next->data){
if(p == *head){
*head = p->next;
}else{
p->prev->next = p->next;
}
p2 = p->next;
p->next = p->next->next;
p->next->next = p;
p->next->next->prev = p;
p->next->prev = p->prev;
p->prev = p2;
}else
p = p->next;
}
}

int main(void){
struct cell *head = (struct cell *)NULL;
int n;

while(1){
printf("1:Insert head 2:Insert tail 3:Delete 4:List 5:Sort 6:Exit\n");
scanf("%d", &n);
switch(n){
case 1:
printf("num = ");
scanf("%d", &n);
insert_head(&head, n);
break;
case 2:
printf("num = ");
scanf("%d", &n);
insert_tail(&head, n);
break;
case 3:
printf("num = ");
scanf("%d", &n);
delete_cell(&head, n);
break;
case 4:
print_list(head);
break;
case 5:
sort_list(&head);
break;
case 6:
return 0;
break;
}
}
}

双方向リストをバブルソートを用いてソートしたいです。
下記がプログラム(一部)ですが、ソートした後にリスト表示すると
無限ループに陥ります。
どこがいけないのでしょうか。

#include <stdio.h>
#include <stdlib.h>

struct cell{
int data;
struct cell *next, *prev;
};

void insert_head(struct cell **head, int num){
struct cell *p, *p1;

p = *head;
p1 = make_cell();
*head = p1;
p1->data = num;
p1->next = p;

if(p1->next != (struct cell *)NULL){
p1->next = p;
...続きを読む

Aベストアンサー

p2 = p->next;
p->next = p->next->next;
p->next->next = p;
p->next->next->prev = p;
p->next->prev = p->prev;
p->prev = p2;

の部分で

p->next->next = p;

の後に

p->next->next->prev = p;

をやると、これは

p->prev = p;

と同じ意味になる。

「自分の前は自分」と言う状態になり、この状態で、もう一度上記のルーチンを通ると「自分の次は自分」と言う状況が出来上がる。

表示ルーチンは「自分の次が、次」とやっているのだから、リストが「自分の次は自分」になってれば、無限ループするのが当たり前。

ソートルーチンで、2つの要素を入れ替えする場合は、以下に示した[1]~[6]の6つのポインタを書き換えないといけない筈。

pの---[1]-->p---[3]-->p2---[5]-->p2の
前 <--[2]--- <--[4]---  <--[6]---次

質問者さんのプログラムでは「5つしか書き換えてない」ので、それだけで「バグっている」のが明白。

以上を踏まえると、pとp2の入れ替えは、以下のようになる。

p2=p->next;
if (*head!=p) p->prev->next = p2; /*pに前が居る場合だけ、 [1]の付け替え*/
if (p2->next) p2->next->prev = p; /*p2に次が居る場合だけ、[6]の付け替え*/
p->next = p2->next;         /*               [3]の付け替え*/
if (*head!=p) p2->prev = p->prev; /*pに前が居る場合だけ、 [4]の付け替え*/
p2->next = p;             /*               [5]の付け替え*/
p->prev = p2              /*               [2]の付け替え*/
if (*head==p) *head = p2;      /*pがheadだったら、p2が新しいheadになる*/

p2 = p->next;
p->next = p->next->next;
p->next->next = p;
p->next->next->prev = p;
p->next->prev = p->prev;
p->prev = p2;

の部分で

p->next->next = p;

の後に

p->next->next->prev = p;

をやると、これは

p->prev = p;

と同じ意味になる。

「自分の前は自分」と言う状態になり、この状態で、もう一度上記のルーチンを通ると「自分の次は自分」と言う状況が出来上がる。

表示ルーチンは「自分の次が、次」とやっているのだから、リストが「自分の次は自分」になってれば、無限ループするのが当た...続きを読む

Qバブルソートとセレクションソートの交換回数について

はじめまして。自学でCを学んでいるものです。いきなりですが、タイトルの通り、バブルソートとセレクションソート(直選択ソート)の交換回数が同じになるということは分かるのですが、その理由が分かりません。
何となくわかっているのですが、nや数式を用いて論理的に説明しろと言われると、お手上げです。自分の理解のためにもこの点はしっかりと押さえておきたいと思っています。
何卒よろしくお願いします。

Aベストアンサー

> 比較回数はバブルソートと同様だが、要素の数が同じなら交換回数は常に同じという、安定性の高いアルゴリズムである。

これは、「バブルソートと選択ソートで交換回数は同じ」という意味ではありません。

「選択ソートでは、要素の数が同じなら、どんな入力データでも交換回数は同じ」という意味です。

たとえば、10要素の選択ソートなら、
「順序的に1番目にくるべき要素を、1番目と交換」
「順序的に2番目にくるべき要素を、2番目と交換」

「順序的に9番目にくるべき要素を、9番目と交換」
という流れになり、
どんな入力データであっても、10要素のソートなら交換回数は必ず9回になります。

一方、バブルソートの場合は、入力データの並びによって、交換回数が変わってきます。

QC言語の構造体にてバブルソートが上手くいきません‥

C言語の構造体にてバブルソートが上手くいきません‥

初めて質問致します。

以下は、構造体で、身長順にバブルソートを行うソース文ですが、
結果表示が、最下部に示したように、
5つのレコードのうち1つが消えてしまい、
残った4つのレコードのうちの1つが重複されて表示されてしまいます。
これが、なかなか解決できません‥。

既に結構調べており、また、早く解決できないといけないこともあり、
すみませんが、回答の形式でお願いできますと大変幸いです。
何卒よろしくお願い致します。


#include<stdio.h>
#include<string.h>

typedef struct kojin {
char name[21];
int length;
int weight;
}KOJIN;

int main(void)
{
int i, c, j;
char buf[4];
KOJIN data[10];
KOJIN *d;

printf(

C言語の構造体にてバブルソートが上手くいきません‥

初めて質問致します。

以下は、構造体で、身長順にバブルソートを行うソース文ですが、
結果表示が、最下部に示したように、
5つのレコードのうち1つが消えてしまい、
残った4つのレコードのうちの1つが重複されて表示されてしまいます。
これが、なかなか解決できません‥。

既に結構調べており、また、早く解決できないといけないこともあり、
すみませんが、回答の形式でお願いできますと大変幸いです。
何卒よろしくお願い致します。


#i...続きを読む

Aベストアンサー

>for(i=0;i<10;i++) {
>d = &data[i];

最終的には、 dには &data[9] 、つまり、data[9]へのポインタが入っているわけです。
そして、そのまま

>*d= data[i];
>data[i]= data[j];
>data[j]= *d;
を実行したら
*dはdata[9]になりますから

data[9]= data[i];
data[i]= data[j];
data[j]= data[9];

と同じ事、となります。
一応、data[i]とdata[j]との入れ替えにはなりますが、同時にdata[i]がdata[9]へコピーされてしまい、もとあったdata[9]の内容が失われます。
最終的に、最後の入れ替えが発生したときのdata[i]と同じ値がdata[9]に入っているとこになります。

対策は、この KOJIN *d を使わないことです
KOJIN temp ;
としておいて

temp= data[i];
data[i]= data[j];
data[j]= temp;

とします。

ところで、これ、バブルソートじゃないですよ。
単純ソートというアルゴリズムになってます。
アルゴリズムの参考書等をもう一度よく確認してください。

>for(i=0;i<10;i++) {
>d = &data[i];

最終的には、 dには &data[9] 、つまり、data[9]へのポインタが入っているわけです。
そして、そのまま

>*d= data[i];
>data[i]= data[j];
>data[j]= *d;
を実行したら
*dはdata[9]になりますから

data[9]= data[i];
data[i]= data[j];
data[j]= data[9];

と同じ事、となります。
一応、data[i]とdata[j]との入れ替えにはなりますが、同時にdata[i]がdata[9]へコピーされてしまい、もとあったdata[9]の内容が失われます。
最終的に、最後の入れ替えが発生したときのdata[...続きを読む


人気Q&Aランキング

おすすめ情報