【掲示板ご利用上の注意】

　※題名は具体的に！
　※学校の課題の丸投げ禁止！
　※ソースの添付は「HTML変換ツール」で字下げ！
　※返信の引用は最小限に！
　※環境（OSとコンパイラ）や症状は具体的に詳しく！
　※返信付き投稿の削除は禁止！
　※マルチポスト（多重投稿）は慎んで！

　詳しくはこちら


本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
　守ってくださいね。お願いします。（by管理人）

C言語ソース⇒HTML形式ツール掲示板２はこちら


管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧
No.23511
VCTK2003 の qsort()
投稿者---まきじ(2005/10/06 00:42:48)


間違ってたら突っ込んでください。

以下のソースで、Visual C++ Toolkit 2003 の qsort() が
クイックソートか否か確かめてみたところ、(最大値の)選択ソートの様です。
よって、qsort() の比較関数で 2 つの値が同じである時
1 を返せば安定したソートになると思います。
よって 23502のソースも少なくともVCTK2003では安定なソートです。

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

typedef struct TEST{
    int no; /* データ(data)に対しての連番 */
    int data; /* データ */
}DATA;

DATA array[7]={{1,4},{2,5},{3,6},{4,3},{5,1},{6,1},{7,1}};
int size = sizeof(array) / sizeof(DATA);

void print_array(DATA* array,int size){

    int i;
    
    for(i = 0; i < size; i++) printf("%d,%d\n",array[i].no,array[i].data);
    puts("");
    
}

int comp(const void *a, const void *b){

    int diff = ((DATA*)a)->data - ((DATA*)b)->data;

    printf("a = %d,%d, b = %d,%d\n",((DATA*)a)->no,((DATA*)a)->data,((DATA*)b)->no,((DATA*)b)->data);
    print_array(array,size);
    getchar();
    
    if(diff) return diff;
    
    /* return 0;    安定でない */
    return 1;   /* 安定 */
    

}

int main(void){

    puts("before");
    print_array(array,size);
    qsort(array,size,sizeof(DATA),comp);
    puts("after");
    print_array(array,size);
}


この投稿にコメントする

削除パスワード
発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:VCTK2003 の qsort() 23513 YuO 2005/10/06 02:39:45

No.23513
Re:VCTK2003 の qsort()
投稿者---YuO(2005/10/06 02:39:45)


>以下のソースで、Visual C++ Toolkit 2003 の qsort() が
>クイックソートか否か確かめてみたところ、(最大値の)選択ソートの様です。
>よって、qsort() の比較関数で 2 つの値が同じである時
>1 を返せば安定したソートになると思います。

Visual Stduio 6.0〜Visual Stduio 2005 β2のソースコードを簡単に調べましたが，
これら全てのqsort実装は，要素数が8個以下では選択ソートを，9個以上ではクイックソートを使っています。


>よって 23502のソースも少なくともVCTK2003では安定なソートです。

例示のコードを次のように変更しました。
DATA array[]={{1,4},{2,5},{3,6},{4,3},{5,1},{6,1},{7,1},{8,3},{9,1}};


結果は，次のようになります(中間部省略)。
before
1,4
2,5
3,6
4,3
5,1
6,1
7,1
8,3
9,1

after
9,1
5,1
7,1
6,1
4,3
8,3
1,4
2,5
3,6

見てわかるとおり，{5,1}よりも{9,1}が前に来るようになります。
つまり，ソートは不安定です。


この投稿にコメントする

削除パスワード
No.23514
Re:VCTK2003 の qsort()
投稿者---まきじ(2005/10/06 02:55:30)


>Visual Stduio 6.0〜Visual Stduio 2005 β2のソースコードを簡単に調べましたが，

ありがとうございます。

>これら全てのqsort実装は，要素数が8個以下では選択ソートを，9個以上ではクイックソートを使っています。

要素数でアルゴリズムを変えてるのですね。
という事は 23502 のソースでは要素数が 9 個なので安定でないですね。
納得いきました。


この投稿にコメントする

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