掲示板ランキング  インターネット・Web開発(セキュリティー管理)


掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板1

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧

No.6644

ドリル&ゼミナール演習102、クイックソート
投稿者---cap_p(2006/10/10 21:38:31)


os:Windows98
compiler:borland/c++compiler/5.5.1

下は<ドリル&ゼミナール>の演習102、クイックソートのコードですが、
気になることがありますので質問いたします。  

 #include <stdio.h>
 #define N 8

 void quick_sort(int *p,int left,int right);

 int main(void)
 {
 int data[N]={16,41,28,33,64,2,75,59};
 int i;

 quick_sort(data,0,N-1);

 for(i=0;i<N;i++)
 printf("%d,",data[i]);

 return 0;
 }

 void quick_sort(int *p,int left,int right)
 {
 int i,j,c,pivot,temp;

 c=(left+right)/2;
 pivot=*(p+c);
 i=left; j=right;
 while(1){
 while(*(p+i)<pivot)i++;
 while(pivot<*(p+j))j--;
 if(i>=j)break;
  temp=*(p+i);
  *(p+i)=*(p+j);
 *(p+j)=temp;
  i++;j--;
 }  
 if(left<i-1)
 quick_sort(p,left,i-1);
i f(j+1<right)
 quick_sort(p,j+1,right);
 }

quick_sort関数内のiとjのインクリメント、デクリメントの重複が気になり、
二度目のを削除して実行したところ、削除前と同じ結果になりました。
試しに配列の要素数と数値を変えてみても正しい結果が表示されました。
これは試した二種類の配列に限っての事なのか、それとも一般的に通用することなのか、どなたか教えてください。
また、省略可能なものならば、あえて重複して記述した訳はなんでしょうか?
宜しくお願いします。



この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:ドリル&ゼミナール演習102、クイックソート 6645 yoh2 2006/10/10 22:29:35


No.6645

Re:ドリル&ゼミナール演習102、クイックソート
投稿者---yoh2(2006/10/10 22:29:35)


2度目のインクリメント、デクリメントがなければ、p[i]、p[j]、pivotが全て等しい場合、無限ループに陥ります。
例: data[N] = { 64, 41, 28, 33, 64, 2, 75, 64 };


この投稿にコメントする

削除パスワード

No.6649

Re:ドリル&ゼミナール演習102、クイックソート
投稿者---cap_p(2006/10/13 20:41:40)


>2度目のインクリメント、デクリメントがなければ、p[i]、p[j]、pivotが全て等しい場合、無限ループに陥ります。
>例: data[N] = { 64, 41, 28, 33, 64, 2, 75, 64 };

単純かつ非常に基本的な理由だったのですね。
思ってもみませんでした。目から鱗です。
ありがとうございました。

試しに上の例を入力して実行してみたら、少々ギョッとさせられました。


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧





掲示板提供:(有)リアル・インテグリティ