掲示板利用宣言

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

 私は

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

掲示板2

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

No.30045

クイックソートのプログラム
投稿者---disfere(2007/04/16 17:01:34)


クイックソートのプログラムを、
自分なりに考えてなんとか形になったのですが、
ソートする配列の要素数の変化により、
ソートができたりできなかったりします。
アドバイスをいただけたらと思います。

ちなみに、ソートする配列 temp[m] はグローバルで宣言し、
rand( ) % 100 を用いて、m個の乱数を入れています。
(実際はtemp[m]ではなく、temp[1000]とか、適当な数字で宣言し、
main関数で最大個数mを聞いて、その数だけ乱数を入れています。)

main関数では quick(0, m) でquick関数を呼んでいます。

コンパイラは「Microsoft Visual C++ 6.0」です。


void quick(int left, int right)
{
    int i, j, p, z;
    
    p = (left + right)/2;
    i = left;
    j = right;
    
    while (1)
    {
        while ( temp[i] < temp[p] ) i++ ;
        while ( temp[j] > temp[p] ) j-- ;
        
        if ( i >= j ) break;
        
        z = temp[i];
        temp[i] = temp[j];
        temp[j] = z;
        
        i++;
        j--;
    }
    if ( left < i-1 ) quick(left, i-1);
    if ( j+1 < right ) quick(j+1, right);
}



この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:クイックソートのプログラム 30046 bugs 2007/04/16 17:07:30


No.30046

Re:クイックソートのプログラム
投稿者---bugs(2007/04/16 17:07:30)


>ソートする配列の要素数の変化により、
>ソートができたりできなかったりします。

例えば、要素数がいくつならばソートができて、
いくつならばできないのでしょうか?

>main関数では quick(0, m) でquick関数を呼んでいます。

要素数m個の配列をソートするのであれば、第2引数はm-1でないと
まずくないですか?


この投稿にコメントする

削除パスワード

No.30047

Re:クイックソートのプログラム
投稿者---disfere(2007/04/16 17:39:00)


コメントありがとうございます。
できる時とできない時の差は、個数で決まっていると思っていたのですが、
実際何回も実行してみたところ個数とは関係がないようです。

・実行結果1

0からいくつまでの乱数にしますか?
100
何個の乱数にしますか?
10
ソート前:
45 34 26 60 76 19 1 12 31 20
ソート後:
1 12 26 34 45 19 20 60 31 76

・実行結果2

0からいくつまでの乱数にしますか?
100
何個の乱数にしますか?
10
ソート前:
2 3 52 92 60 82 78 23 1 78
ソート後:
1 2 3 23 52 60 78 78 82 92

二つ目のご指摘は、私の書き間違いです。
第二引数は m-1 で行っています。


ものすごく長文になり、申し訳なく思いますが、
ソースをすべて記載します。
見てもらえたら幸いです。
(一部前回の投稿とソースが異なる部分がありますが、ご了承ください。)


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

void SetData(void);
void quick(int left, int right);
void main(void);

int a[1000];
int m;
int keta;

void SetData(void)
{
    int i;
    
    srand(time(NULL));
    
    for (i = 0; i < m; i++)
        a[i] = rand(  ) % keta;

}

void quick(int left, int right)
{
    int i, j, p, z;
    
    p = (left + right)/2;
    i = left;
    j = right;
    
    while (1)
    {
        while ( a[i] < a[p] ) i++ ;
        while ( a[j] > a[p] ) j-- ;
        
        if ( i >= j ) break;
        
        z = a[i];
        a[i] = a[j];
        a[j] = z;
        
        i++;
        j--;
    }
    if ( left < i-1 ) quick(left, i-1);
    if ( j+1 < right ) quick(j+1, right);
}

void main(void)
{
    int i,j;

    j = 0;

    printf("0からいくつまでの乱数にしますか?\n");
    scanf("%d",&keta);

    printf("\n");

    printf("何個の乱数にしますか?\n");
    scanf("%d",&m);
    
    SetData(  );

    printf("ソート前:\n\n");

    for (i = 0; i < m; i++) {
        printf("%5d ", a[i]);
        j++;
        if (j == 10){
            printf("\n");
            j = 0;
        }
    }
    
    printf("\n");
    printf("\n");
    
    quick(0, m-1);

    printf("\n");
    
    printf("ソート後:\n\n");
    
    j = 0;

    for (i = 0; i < m; i++){
        printf("%5d ", a[i]);
        j++;
        if (j == 10){
            printf("\n");
            j = 0;
        }
    }

    return;
}



この投稿にコメントする

削除パスワード

No.30048

Re:クイックソートのプログラム
投稿者---chu-(2007/04/16 20:39:39)


ピボットを表す変数pの扱いが誤っています。
配列のインデックスではなく、数値として扱うべきです。
現在の扱い方では、ピボットをしきい値とした二分割処理中にしきい値が変化してしまいます。
例えば以下のようにすると正しくソートされます。

void quick(int left, int right)
{
    int i, j, p, z;

/*  p = (left + right)/2;   */
    p = (a[left] + a[right])/2;
    i = left;
    j = right;

    while (1)
    {
/*      while ( a[i] < a[p] ) i++ ; */
/*      while ( a[j] > a[p] ) j-- ; */
        while ( a[i] < p ) i++ ;
        while ( a[j] > p ) j-- ;

        if ( i >= j ) break;

        z = a[i];
        a[i] = a[j];
        a[j] = z;

        i++;
        j--;
    }
    if ( left < i-1 ) quick(left, i-1);
    if ( j+1 < right ) quick(j+1, right);
}



この投稿にコメントする

削除パスワード

No.30049

Re:クイックソートのプログラム
投稿者---disfere(2007/04/17 09:17:16)


なるほどなるほど。
確かにそのとおりですね。
ご指摘を受けた部分を修正したら、正常にソートされるようになりました。

丁寧なご回答、ありがとうございました。


この投稿にコメントする

削除パスワード

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