0

私はquickSelectアルゴリズムを理解して実装するためにquickSelectに従いました。ここでよくわからないことが 1 つk-pivotありpivot-first+1ます。

私の実装はこのリンクとまったく同じですが、機能していません。

#include <stdio.h>
#include <string.h>

#define DEBUG 1

#define debug(fmt, ...)\
    do{\
        if(DEBUG)\
            fprintf(stdout, "%s(%d) :   " fmt "\n", __FUNCTION__, __LINE__, __VA_ARGS__);\
    }while(0)

#define swap(a, b)\
    do{\
        if(a != b) {\
            a = a ^ b;\
            b = a ^ b;\
            a = a ^ b;\
        }\
    }while(0)


int
partition(int *a, int low, int high)
{
    int i = low, j = high;

    int pivot = a[i];
    i++;
    while(i < j)
    {
    while(pivot >= a[i])
        i++;
    while(pivot < a[j])
        j--;
    if(i < j)
        swap(a[i], a[j]);
    }

    swap(a[low], a[j]);
    return j;
}


int
quick_select(int *a, int start, int end, int k)
{
    if(start < end)
    {
    int pivot = partition(a, start, end);

    if(k < (pivot - start + 1))
       return quick_select(a, start, pivot, k);
    else if( k > (pivot - start + 1))
       return quick_select(a, pivot+1, end, k - pivot);
    else
    return a[pivot];
    }
}

int
main()
{
    int a[100], k, n;
    int ret, i;

    while(1)
    {
    printf("# of items  :   ");
    scanf("%d", &n);

    printf("Items   :   ");
    for(i = 0; i<n; i++)
        scanf("%d", &a[i]);

    printf("<k> :   ");
    scanf("%d", &k);

    ret = quick_select(a, 0, n-1, k);
    printf("[%d] smallest element = [%d]\n", k, ret);
    }

    return 0;
}

出力:

./a.out 
# of items  :   10
Items   :    1 2 3 4 5 6 7 8 9 10
<k> :   9
[9] smallest element = [32767]
4

2 に答える 2

0

あるケースでピボット 1 を実行しなかっただけで、次の K を見つけるために K から正しい値を減算していませんでした。

8 つの数字があり、ピボットが 5 であるとします。この 5 は何を意味するのでしょうか? これは、非降順でソートしている場合、5 番目のインデックスの数値が 5 番目に小さい要素であり、5 番目のインデックスよりも小さいすべての数値がそれよりも小さいことを意味します。では、7 つの最小の数 (K と呼びましょう) を探している場合、どこを検索すればよいでしょうか? 6～8で探せばいいじゃないですか。しかし、K 数はどうなるでしょうか? 6 から 8 の範囲で最小の 7 つの数を検索する必要がありますか? 権利はありません？

7から6(0から5)の数字を引くべきだと思いませんか? それでもないと思う場合は？それから読んでください。そうでなければ、ここで読むのをやめてください。

あなたには 5 人の弟がいて、その中で一番背が高いとします。目の見えない男性があなたの家に来て、あなたたち全員の中で 5 番目に背が高いのは誰か知りたがっています。それは、5 番目に高い人を見つけるために彼が尋ねることができる唯一の質問です。彼がしていることは、クイックソートに似たものです。彼があなたの 3 番目の兄弟をピボットとして選び、身長が 3 分の 1 未満の兄弟を左に、その他の兄弟を右に並べます。その後、3 番目の兄弟が立っている場所を数えると、3 番目の兄弟が 3 番目に高いことがわかります。あなたの家の中に。さて、彼は 5 番目に高い、明らかに右側のどこを探せばよいでしょうか?いいえ?

しかし、彼は 4 番目に高い人が右に向かって立っている場所を知りません。右？彼が知っているのは、4 番目と 5 番目に高い人が右に向いているということだけです。右に向かって立っている 2 人がいて、どちらも 3 番目よりも背が高く、盲人は 5 番目に高い人を知りたがっていますが、これら 2 人の中で、正しいグループで 4 番目に高いか 2 番目に高い (5-3) を探す必要があります。 (範囲は 4 ～ 5)?

きっともうお分かりだと思います。

quick_select(int *a, int start, int end, int k)
{
    if(start < end)
    {
        int pivot = partition(a, start, end);

        if(k < (pivot - start + 1))
            return quick_select(a, start, pivot-1, k);
        else if( k > (pivot - start + 1))
            return quick_select(a, pivot+1, end, k - (pivot-start+1));
        else
            return a[pivot];
    }
}
于 2015-10-19T07:51:52.710 に答える