ソートの検証法

[みけCAT]

最近クイックソートについて質問させていただいたみけCATです。
そのほかにもいろいろなソートのプログラムを作ってみています。
すべて昇順にソートするプログラムです。
そこでそのソートのプログラムが間違っていないか検証したいです。
しかし、今使っている検証プログラムではうまく検証できているか不安です。
このプログラムは、以下の３点を検証します。
・配列の前の値が今の値より大きくないか
・配列の値を全て足したものがソート前と同じか
・配列の値を全てxorしたものがソート前と同じか
このプログラムで間違っている、あっている、
またその他いい方法があるという意見がある方は言ってくれれば嬉しいです。

/*苦Cより*/
int GetRandom(int min,int max)
{
    return min + (int)(rand()*(max-min+1.0)/(1.0+RAND_MAX));
}

int makedata(int** data,int datanum)
{
    int i;
    *data=malloc(datanum*sizeof(int));
    for(i=0;i<datanum;i++)(*data)=GetRandom(0,INT_MAX)*((rand()%2)*2-1);
}

void sortcheck(char* sortname,int datanum,void (*sortfunc)(int*,int)) {
    static int doornot=0;
    int* data;
    unsigned int starttime;
    unsigned int keikatime;
    int i;
    int ok;
    int sum;
    int xor;
    int sumafter;
    int xorafter;
    if(doornot!=2) {
        printf("%sをしますか？\n",sortname);
        printf("0:はい　1:いいえ　2:すべて\n>");
        scanf("%d",&doornot);
    } else {
        printf("%sをします。\n",sortname);
    }
    if(doornot!=1) {
        makedata(&data,datanum);
        sum=0;
        xor=0;
        for(i=0;i<datanum;i++) {
            sum+=data;
            xor^=data;
        }
        starttime=GetTickCount();
        sortfunc(data,datanum);
        keikatime=GetTickCount()-starttime;
        ok=1;
        for(i=1;i<datanum;i++) {
            if(data<data[i-1]) {
                ok=0;
                break;
            }
        }
        if(ok) {
            sumafter=0;
            xorafter=0;
            for(i=0;i<datanum;i++) {
                sumafter+=data;
                xorafter^=data;
            }
            if(sum!=sumafter || xor!=xorafter)ok=0;
        }
        if(ok)printf("ソート成功");
        else printf("ソート失敗");
        printf("　%uミリ秒\n",keikatime);
        free(data);
    }
}

また、自分がだめだと思うのは以下の方法です。
・ソート前とソート後の配列のハッシュ値をとる
　ソートによって配列のデータが変わるので、意味ないと思います。
・ソート前の配列を別にソートし、ソートの結果と比較する
　そのソートがあっているかわからないし、そのソートの時間がもったいないと思います。
よろしくお願いします。

[初級者]

以下の３点、と書かれているうち、２点目と３点目は
どういう意味があるのでしょうか。

例えば、２点目の合計値を比較することで何がわかるのでしょうか。
仮に合計値が同じだとしても、それでもって
「昇順ソートが成功したかどうか」は全くわかりませんよね。

[みけCAT]

この関数では、上に挙げた３つの検証を全て行い、
全てＯＫなら「ソート成功」と表示するようにしています。
２つめと３つめの検証は、データの組み合わせが変わっていないかの検証です。
例えば、5,2,1,4,3という配列があったとします。
これが1,3,3,4,5となった場合、
元のデータと組み合わせが違っているので、ソートに成功したとは言えないと思います。
こういうのをチェックするために２番目と３番目の検証を作りました。

[たいちう]

標準関数でソートした結果と比べてみるとか、
ソート前後にテキストで出力して、Excelでのソート結果と比較するとか。

何のための検証なのか書いてもらえます？
自分で納得したいとか、第三者（顧客や課題を出した先生や先輩）を納得させたいとか。
テストについての本を読むと幸せになれるのかもしれません。

その場合、一応お勧めの本。
『はじめて学ぶソフトウェアのテスト技法』
http://www.amazon.co.jp/dp/4822282511/

# 一応とあるのは、現在手元にないので似たタイトルの他の本と
# 間違えているかもしれないからです。
# 多分大丈夫だと思うけど、今はもっと良い本があるかもしれないので、
# 興味があるならば探してみて下さい。

[初級者]

たいちうさんの「標準関数でソートした結果と比べる」に
激しく同意します。

なるべく自分で作り込まないことをおすすめします。
作り込んだ検証プログラムが間違っていたら目も当てられませんからね。

[みけCAT]

>標準関数でソートした結果と比べる
確かにこれでいいと思います。
検証用のソートにかかる時間については、
最初に一度だけソートするデータの作成と検証用のソートを行い、
毎回同じデータをソートするようにすればいいと思います。

[みけCAT]

>何のための検証か書いてもらえませんか？
自分で納得するためです。
将来ホームページを作った時にこのソートのプログラムを公開したいと思っています。

[tex]

みけCATさんの行われている検証法の1つ目とIndex毎の小計を比較すれば
それでソートが成功しているかどうかの十分条件になるんじゃないかな？
必要条件はちょっとわかんないや
もしかしたら今みけCATさんが行っている検証法がそうかも？

[みけCAT]

qsortでソートした結果と比べる方法を採用しました。
ありがとうございました。
とりあえずsortcheck関数のみ貼ります。
全てのソースコードは添付ファイルを見てください。

void sortcheck(char* sortname,int* arr,int* arrans,
        int datanum,void (*sortfunc)(int*,int)) {
    static int doornot=0;
    int* data;
    unsigned int starttime;
    unsigned int keikatime;
    int i;
    int ok;
    if(doornot!=2) {
        printf("%sをしますか？\n",sortname);
        printf("0:はい　1:いいえ　2:すべて\n>");
        scanf("%d",&doornot);
    } else {
        printf("%sをします。\n",sortname);
    }
    if(doornot!=1) {
        data=malloc(datanum*sizeof(int));
        memcpy(data,arr,datanum*sizeof(int));
        starttime=GetTickCount();
        sortfunc(data,datanum);
        keikatime=GetTickCount()-starttime;
        ok=1;
        for(i=0;i<datanum;i++) {
            if(data!=arrans) {
                ok=0;
                break;
            }
        }
        if(ok)printf("ソート成功");
        else printf("ソート失敗");
        printf("　%uミリ秒\n",keikatime);
        free(data);
    }
}

[みけCAT]

No.64814の添付ファイルのsort.hを以下の内容に差し替えてください。

extern void bubblesort(int*,int);
extern void insertsort(int*,int);
extern void quicksort(int*,int);
extern void shellsort(int*,int);
extern void heapsort(int*,int);
extern void dosuusort(int*,int);
extern void dosuusort2(int*,int);