random select algorithm(選択アルゴリズム)

≪アルゴリズムの選択｜Select Algorithm｜oem_src≫:ソートされていないシーケンスでK番目に小さい要素を選択します.
 

static int random_select(int begin, int end, int k)
{
        assert(begin < end);
        assert(k >= 0);
        assert(k < end-begin);

        int rand = randint(begin, end);
        int left, right;

        partition(begin, end, rand, &left, &right);
        int idx = k+begin;
        if (idx < left)
                return random_select(begin, left, k);
        else if (idx >=left && idx<=right)
                return idx;
        else
                return random_select(right+1, end, idx-right-1);

}

static void partition(int begin, int end, int pivot_index, int *ret_left, int *ret_right)
{
#if 0
        printf("***********in partition*****************
");
        print_array(begin, end);
        printf("pivot_index = %d
", pivot_index);
#endif
        int pivot = A[pivot_index];
        swap(begin, pivot_index);

        int left = begin;
        int right = begin;
        int i;
        for (i=begin+1; i<end; i++)
        {
                if (A[i] > pivot)
                        ;
                else if (A[i] == pivot)
                {
                        swap(right+1, i);
                        right += 1;
                }
                else
                {
                        swap(left, i); left += 1;
                        swap(right+1, i); right += 1;
                }

        }
        *ret_left = left;
        *ret_right = right;
#if 0
        print_array(begin, end);
        printf("left = %d, right = %d 
", left, right);
        printf("***********end partition*****************
");
#endif
}

pseudo codeで書き終わると、5分もかかりませんでしたが、実際にコードデバッグに変換するのに30分以上かかりました.以下はいくつかの原因です.
1.普段pseudo codeを書くときは、人間との正常な思考がずっと続き、配列は1から始まり、最小のk番目の要素は最小のk番目の要素である.実際にコードを書くのは、配列時に0から始まります.この点は、混同しやすい.私の感覚は、pseudo codeとプログラムコードの約束が一致するように、自分の記号とルールを定義することです.例えば、ランキングは0から始めて、0が小さくて、1が小さくて、..k番目は小さいです.例えば、集合統一は半開半閉の表現方法を採用し、配列に関する呼び出しの伝達パラメータ(begin,end)はすべて半開半閉である.A[begin:end)
2.divide-and-conque法で問題を解決する場合、境界条件が間違えやすい.境界条件を書くときは、簡単な例で正しいかどうかを見たほうがいいと思います.さもないと、プログラムが走って、崩壊したら、悲劇になります.
3.関数の定義は明確にし、その意味は必ず明確にしなければならない.入力されたパラメータの意味、返された値の意味.私が今回バグを作ったのはrandomのせいだselect関数が最初に定義した値の意味は明確ではありません.
刀を研いで柴刈りを間違えず、定義を明確にしてから手を出す.