2

クイックソートのコードを書き込もうとしていますが、無限ループに陥り続けています。次のコードでエラーを見つけるのに苦労しました。誰か助けてください。

#include<stdio.h>
#include<stdlib.h>

int arr[100];

void quicksort(int low,int high)
{
    int i = low,j = high,pivotIndex,pivot;
    pivotIndex = rand()%20;
    pivot = arr[pivotIndex];

    if(i>=j)
        return;

    while(i<j)
    {

        while(arr[i]<pivot && i<j)
        {
            i++;
        }

        while(arr[j]>pivot && j>i)
        {
            j--;
        }

        if(i<j)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

    }
    quicksort(low,i);
    quicksort(i+1,high);
}

int main()
{
    int i,j,temp;

    for(i=0;i<20;i++)
        arr[i] = rand()%21;

    for(i=0;i<20;i++)
        printf("%d ",arr[i]);
    printf("\n");

    quicksort(0,19);

    for(i=0;i<20;i++)
            printf("%d ",arr[i]);
    printf("\n");

    return 0;
}
4

3 に答える 3

7

ピボットの選択が間違っています。ピボットを (index) range[low,high)で選択する必要がありますが、範囲でピボットを選択する必要があります[0,20):

pivotIndex = rand()%20;

後でパーティションがうまくいかなくなり、i後で再帰するために使用する の値が間違ったものになります。

編集：

もう 1 つの問題はパーティショニングに関するものです。ピボット要素とその複製をどうするかを検討する必要があります。ある種の「タイ ブレーカー」が必要です。ピボットは配列の一方の側 (または別の方法) に移動する必要があります。
たとえば、ピボットが5で、配列が であると仮定し[5,3,8,5]ます
。5 を何度も無限に交換することになりますが、これは明らかに間違っています。

于 2012-10-31T08:32:30.210 に答える
1

並べ替えプラグインの作成者として、この種のアルゴリズムを再発明すると、ことわざに苦しむ可能性があることを保証できます。;o)

ピボットの選択には特に注意が必要です (既に述べたように)。算術演算がピボット値にどのように影響するか (たとえば、VBA は浮動小数点で整数演算を行うため、あらゆる種類の奇妙さを引き起こします)。最後のステップで最後のパーティションがどのように処理されるかを確認してください (ここでいくつかのレコードをスキップするのはあなたが初めてではありません)。

多くの言語でアルゴリズムをソートするためのリンクは次のとおりです。

http://rosettacode.org/wiki/Sorting_algorithms/Quicksort

于 2012-10-31T11:05:06.563 に答える
-1 
 pivotIndex = rand()%20;
 pivot = arr[pivotIndex];

ここで、クイックソートを呼び出すたびに、pivotIndex が範囲内 (低、高) にない可能性があります。使用できます

pivotIndex = low+rand()%(high-low);

これにより、範囲内でpivotIndexが生成されると確信しています。

于 2012-10-31T08:39:47.833 に答える