掲示板ランキング  タイツ・スパッツ  その他  下着  肌着  パジャマ  その他  リュックサック


掲示板利用宣言

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

 私は

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

掲示板1

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

No.6956

クイックソートに関して質問
投稿者---つとむ(2006/12/22 07:00:18)


まずはクイックソートのサブルーチンのみ摘出して書きます。

void quicksort(int a[],int first,int last)
{
    /*lastは含まない*/
    int temp;
    int forward = first;
    int backward = last-1;

    /*軸を配列の末尾要素とする*/
    register int pivot = a[backward--];

    /*配列の要素が1個なら終了する*/
    if(first >= last-1)
        return;

    /*配列の要素を軸を基準にして左側に小グループ、右側に大の部ループと振り分ける*/
    while(1)
    {
        /*小グループならforwardを前進する*/
        while(a[forward]<pivot)
            forward++;
        /*大グループならbackwardを後退する*/
        while(pivot<a[backward])
            backward--;
        /*forwardがbackwardと合流していれば配置換えを終える*/
        if(forward >=backward)
            break;

        /*forwardが前進できずbackwardが後退できないので、forward要素とbackward要素はともに、軸に対し逆の大小関係にある*/

        /*forward要素とbackward要素を交換する*/
        temp = a[forward];
        a[forward++] = a[backward];
        a[backward--] = temp;
    }

    /*軸を所定の位置に置く*/
    a[last-1] = a[forward];
    a[forward] = pivot;

    /*左側を分類する(forwardを含まない)*/
    qasort(a,first,forward);
    /*右側を分類する(lastを含まない)*/
    qasort(a,forward+1,last);
}


ランダムな数値列を昇順ソートするプログラムです。
基準値pivotは数値列の末尾要素とします。
クイックソートサブルーチンの中にある
pivot = a[backward--];
の部分なんですが、backwardを更にデクリメントしている意味がよく分かりません。
pivot、backward、backward--の各値を宣言部分の直後で調べてみるとlastの値を9とした場合
pivot = 末尾要素の値
backward = 6
backward-- = 7
となるのも納得がいきません。

どなたかご教授願えないでしょうか?

使用環境
LSI C-86 Ver.3.30c 試食版
WinXP


この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:クイックソートに関して質問 6957 - 2006/12/22 10:16:51


No.6957

Re:クイックソートに関して質問
投稿者----(2006/12/22 10:16:51)


>void quicksort(int a[],int first,int last)
(中略)
> /*左側を分類する(forwardを含まない)*/
> qasort(a,first,forward);
> /*右側を分類する(lastを含まない)*/
> qasort(a,forward+1,last);

再帰呼び出しができない状態です。
コンパイルができるコードを載せてください。


この投稿にコメントする

削除パスワード

No.6958

Re:クイックソートに関して質問
投稿者---つとむ(2006/12/22 10:33:41)


すいませんでした。 一応プログラム全部もってきました。

#include<stdio.h>
void qasort(int a[],int first,int last)
{
    int temp;
    int forward = first;
    int backward = last-1;
    register int pivot = a[backward--];
    if(first >= last-1)
        return;
    while(1)
    {
        while(a[forward]<pivot)
            forward++;
        while(pivot<a[backward])
            backward--;
        if(forward >=backward)
            break;
        temp = a[forward];
        a[forward++] = a[backward];
        a[backward--] = temp;
    }
    a[last-1] = a[forward];
    a[forward] = pivot;
    qasort(a,first,forward);
    qasort(a,forward+1,last);
}
int main(void)
{
    int i;
    int a[] = {2,8,6,3,9,5,1,7,4};
    int n = 9;
    for(i=0;i<n;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    qasort(a,0,n);
    for(i=0;i<n;i++){
        printf("%d ",a[i]);
    }
    return 0;
}   



この投稿にコメントする

削除パスワード

No.6959

Re:クイックソートに関して質問
投稿者---kolona(2006/12/22 12:06:45)


配列の最終要素をピボットにしているからです。ピボットを

register int pivot = a[backward--];

のように設定した後、デクリメントしておかなければ

while(pivot<a[backward])
backward--;

で最終要素が判定されてしまいます。これはクイックソート関数が呼び出されるたびに起こりますが、
軸に使っているのでこのソート条件に引っかからないのは明らかです。
で、最後に

a[last-1] = a[forward];
a[forward] = pivot;

で軸を真ん中に持っていくんだと思います。


この投稿にコメントする

削除パスワード

No.6960

Re:クイックソートに関して質問
投稿者----(2006/12/22 12:30:43)


No.6958のコードをもとに、
pivotとbackwardの値を出力するprintfを追加してみました。
(前略)
    int backward = last-1;
    register int pivot = a[backward--];
    printf("pivot=%d\n", pivot);
    printf("backward=%d\n\n", backward);
    if(first >= last-1)
        return;
(以下省略)

すると、以下の結果を得ました。
2 8 6 3 9 5 1 7 4 
pivot=4
backward=7

pivot=3
backward=1

pivot=1
backward=0

pivot=2147348480
backward=-2
(以下省略)

ソートの結果そのものは正しいのですが、
途中経過で、pivotとbackwardの値が正しくなくなっています。
qasort関数のロジックを見直す必要があるのかもしれません。



この投稿にコメントする

削除パスワード

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





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