C言語関係掲示板

過去ログ

No.1207 クイックソートのアルゴリズムを理解する

[戻る] [ホームページ]
No.15854

*クイックソートのアルゴリズム*
投稿者---tomo(2004/07/25 11:28:35)


クイックソートのアルゴリズム自体は何度も読み理解している
つもりなのですが、サンプルプログラムをみても
プログラム自体が理解しきれません。
どうぞご教授お願い致します。

質問ヾ愎瑤慮討喀个靴琉数の内容がよくわかりません
quick_sort(data, 0, SIZE - 1);
(data, 0, SIZE - 1)この引数は何を表しているのでしょうか?

質問関数の定義内にif(left<right)とありますが、
勿論意味自体はわかりますが、ここでの表現の意味がわかりません。

質問i=left-1; j=right+1; とありますが、
なぜ-1と+1がつくのですか?
-1、+1の意味を理解しようと、削除してコンパイルすると
不正な処理としてエラーがでてしまいました。

コンパイラはボーランドの C++ 5になります。


/* クイックソートによるデータソート(昇順) */

#include <stdio.h>

void quick_sort(int [], int, int);

int main(void)
{
    int data[] = {8,4,5,1,2,7,6,3,9,0}; // ソートするデータ

    int SIZE = sizeof(data) / sizeof(int);  // データ数

    int i;

    for ( i = 0; i < SIZE; i++ )
        printf("%d ",data[i]);
    
    printf(" <- default data\n");

    quick_sort(data, 0, SIZE - 1);

    for ( i = 0; i < SIZE; i++ )
        printf("%d ",data[i]);
    
    printf(" <- sort complete\n");
    
    return 0;
}

void quick_sort(int data[], int left, int right)
{
    int point;
    int tmp;
    int i;
    int j;
    
    if (left < right)
    {      
        point = data[(left+right)/2];
        i = left - 1;
        j = right + 1;
        
        while(1)
        {
            while(data[++i] < point);
            while(data[--j] > point);
            
            if (i >= j)
                break;
                
            tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }
        
        quick_sort(data, left, i-1);
        quick_sort(data, j+1, right);
    }
}



No.15858

Re:*クイックソートのアルゴリズム*
投稿者---RAPT(2004/07/25 12:43:17)


>クイックソートのアルゴリズム自体は何度も読み理解している
>つもりなのですが、サンプルプログラムをみても
>プログラム自体が理解しきれません。

もしかして、コードだけを見て勉強しているつもりでしょうか?
であれば、参考文献を買うなり、Webページで勉強するなりして、
紙と鉛筆でソートの方法について感覚的に理解してください。
ソート関係は基礎分野なので、参考文献はたくさんあると思います。

あとは、そのソートの手順に従ってコードを起こせばいいのです。

この順序を間違えると、理解できるものも理解できないかと思われます。

■質問1について
SIZEがソートを行なうデータの要素数です。
C言語では、配列が n 個の要素をもつとき、array[0] 〜 array[n-1] まで
が利用可能です。今回は、ソートを行なう配列の一番左の要素番号と一番右の
要素番号を関数に渡すので、0 と SIZE-1 を渡しています。

■質問2について
>質問関数の定義内にif(left<right)とありますが、
>勿論意味自体はわかりますが、ここでの表現の意味がわかりません。
?(・_。)?(。_・)?
質問の意味が私にはサッパリ分かりません。
「意味自体」とは? 「表現の意味」とは?
私には同じことのように思われますが…。
# ソーティングのアルゴリズムが分かっていれば、問題ないはず。

■質問3について
これも、ソーティング(ソート処理)のアルゴリズムが分かっていれば
解決します。

C言語も分からない。基礎アルゴリズムも分からない。
のであれば、一度に両方をやろうとするのは無謀です。

普通の人が、いきなり名医になる! とか言っても一朝一夕には無理なことと
同じです。まずは、知識をつけて、それから技術を磨くでしょう?
最低限の基礎知識もないまま突っ込んでいっても大変なだけです。



No.15859

Re:*クイックソートのアルゴリズム*
投稿者---tomo(2004/07/25 13:45:21)


>もしかして、コードだけを見て勉強しているつもりでしょうか?
>であれば、参考文献を買うなり、Webページで勉強するなりして、
>紙と鉛筆でソートの方法について感覚的に理解してください。
>ソート関係は基礎分野なので、参考文献はたくさんあると思います。
>
>あとは、そのソートの手順に従ってコードを起こせばいいのです。
>
>この順序を間違えると、理解できるものも理解できないかと思われます。
>
>■質問1について
>SIZEがソートを行なうデータの要素数です。
>C言語では、配列が n 個の要素をもつとき、array[0] 〜 array[n-1] まで
>が利用可能です。今回は、ソートを行なう配列の一番左の要素番号と一番右の
>要素番号を関数に渡すので、0 と SIZE-1 を渡しています。
>
>■質問2について
>>質問関数の定義内にif(left<right)とありますが、
>>勿論意味自体はわかりますが、ここでの表現の意味がわかりません。
>?(・_。)?(。_・)?
>質問の意味が私にはサッパリ分かりません。
>「意味自体」とは? 「表現の意味」とは?
>私には同じことのように思われますが…。
># ソーティングのアルゴリズムが分かっていれば、問題ないはず。
>
>■質問3について
>これも、ソーティング(ソート処理)のアルゴリズムが分かっていれば
>解決します。
>
>C言語も分からない。基礎アルゴリズムも分からない。
>のであれば、一度に両方をやろうとするのは無謀です。
>
>普通の人が、いきなり名医になる! とか言っても一朝一夕には無理なことと
>同じです。まずは、知識をつけて、それから技術を磨くでしょう?
>最低限の基礎知識もないまま突っ込んでいっても大変なだけです。

ごもっともでございます。
C言語をマスターする為の勉強の仕方がまちがっているかもしれません。
PCスクールではとにかくサンプルプログラムをみて
「プログラムはこうゆうものなのだ。」ということで進めて、
あとは自力で理解してください。
という方針なのですが、
変数、関数、ポインタ、構造体・・・などと順を追い
アルゴリズムにたどり着いたのですが、
基礎がなっていないようです。
もう一度復習しつつ、参考書等を参考にやり直します。
ありがとうございます。


No.15860

Re:*クイックソートのアルゴリズム*
投稿者---シャノン(2004/07/25 14:09:17)


>■質問2について
>>質問関数の定義内にif(left<right)とありますが、
>>勿論意味自体はわかりますが、ここでの表現の意味がわかりません。
>?(・_。)?(。_・)?
>質問の意味が私にはサッパリ分かりません。
>「意味自体」とは? 「表現の意味」とは?
>私には同じことのように思われますが…。
># ソーティングのアルゴリズムが分かっていれば、問題ないはず。

初めのうちはよくあることだと思いますよ。
left が right より小さいかどうか比較しているという、if文の「意味自体」はわかるのです。
が、何のために比較しているのかが理解できない。

#クイックソートなどの汎用的な処理ならまだいいですが、
#他の人が書いたプログラムを読むときなど、ステップ実行して
#初めてわかることもあります。


No.15862

Re:*クイックソートのアルゴリズム*
投稿者---tomo(2004/07/25 15:15:10)


>初めのうちはよくあることだと思いますよ。
>left が right より小さいかどうか比較しているという、if文の「意味自体」はわかるのです。
>が、何のために比較しているのかが理解できない。
>
>#クイックソートなどの汎用的な処理ならまだいいですが、
>#他の人が書いたプログラムを読むときなど、ステップ実行して
>#初めてわかることもあります。

シャノンさんありがとうございます。
もっともっと勉強して、理解を深めていこうと思います。
とにかくたくさん問題を解き、読み
シャノンさんがおっしゃるように理解していけたらと思います。


No.15866

Re:*クイックソートのアルゴリズム*
投稿者---RAPT(2004/07/25 15:22:56)


>もっともっと勉強して、理解を深めていこうと思います。
>とにかくたくさん問題を解き、読み

確かに、既存のコードを元に理解を深める事は重要ですが、それを弄繰り
回して、いずれは、何も見なくても自分で書けるように反復することが、
より、重要です。

昔から「読み、書き、算盤」とは言いますが、プログラミングも同様で、
「他人のコードを読む」「自分で書く」「(実行を)イメージ(計算)する」
を繰り返す事で向上できます。

がんばってください。


No.15877

Re:*クイックソートのアルゴリズム*
投稿者---tomo(2004/07/25 18:22:49)


>確かに、既存のコードを元に理解を深める事は重要ですが、それを弄繰り
>回して、いずれは、何も見なくても自分で書けるように反復することが、
>より、重要です。
>
>昔から「読み、書き、算盤」とは言いますが、プログラミングも同様で、
>「他人のコードを読む」「自分で書く」「(実行を)イメージ(計算)する」
>を繰り返す事で向上できます。
>
>がんばってください。

RAPTさん
わざわざありがとうございます。
確かに勉強をしていてC言語をマスターすることは
楽でもないし、簡単でもありません。正直私は頭もさほどよくもありません。
自分にプログラミングが向いているかもわかりません。
ただ勉強していて楽しいので続けております。

そのようななかで、RAPTさんやシャノンさんのように
C言語を究めている方からのアドバイスというものは
私にとって大変ありがたいです。

RAPTさんからの言葉、肝に銘じて前進していきます。
ありがとうございます。