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

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

 詳しくはこちら



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

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


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

No.18963

クイックソートのロジックについて
投稿者---アルゴリズム勉強中(2005/01/02 18:05:09)


はじめまして。アルゴリズム勉強中です。
現在、C言語による実用アルゴリズム入門の42ページのクイックソートアルゴリズムがわかりません。以下にソースを記述します。
void quick_sort(int d[], int top, int end)
{
    int key, wk, i, j;

    key = d[(top + end) / 2];
    i = top - 1; j = end + 1;
    while (1) {
        while (d[++i] < key)     
            ;
        while (d[--j] > key)     
            ;
        if (i >= j) break;
        wk = d[i]; d[i] = d[j]; d[j] = wk;
    }
    if (top < i - 1) quick_sort(d, top, i - 1);
    if (j + 1 < end) quick_sort(d, j + 1, end);
}

上記の,良分がどのような処理を行っているのかがわかりません。
たとえば、main部分でd[]に50,30,70,60,90,40,80,10をquick_sort関数に渡した場合、どのようにトレースされるのかを大変恐縮ではございますが教えていただけないでしょうか?

よろしくお願いいたします。


この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:クイックソートのロジックについて 18965 RAPT 2005/01/02 19:41:35


No.18965

Re:クイックソートのロジックについて
投稿者---RAPT(2005/01/02 19:41:35)


そんなもん、自分で出力すればいいでしょう?

#include <stdio.h>

void put_var(const char *str, int i, int d[], int key)
{
    printf("%.20s\td[%d]=(%d)\tkey(%d)\n", str, i, d[i], key);
}

void quick_sort(int d[], int top, int end)
{
    int key, wk, i, j;

    key = d[(top + end) / 2];
    i = top - 1; j = end + 1;
    for(;;) {
        printf("i = (%d)\n", i);
        ++i;
        put_var("while前:i", i, d, key);
        while( d[i] < key ){
            put_var("while中:i", i, d, key);
            ++i;
        }

        printf("j = (%d)\n", j);
        --j;
        put_var("while前:j", j, d, key);
        while( d[j] > key ){
            put_var("while中:j", j, d, key);
            --j;
        }

        if (i >= j) break;
        wk = d[i]; d[i] = d[j]; d[j] = wk;
    }
    if (top < i - 1) quick_sort(d, top, i - 1);
    if (j + 1 < end) quick_sort(d, j + 1, end);
}


int main()
{
    int d[] = { 50,30,70,60,90,40,80,10, };
    const int size = sizeof d / sizeof d[0];
    int i;
    
    quick_sort(d, 0, size-1);
    for (i = 0; i < size; i++){
        printf("%d\n", d[i]);
    }
    return 0;
}




この投稿にコメントする

削除パスワード

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