20

この本からクイックソートアルゴリズムを見つけました

これがアルゴリズムです

QUICKSORT (A, p, r)
if p < r
    q = PARTITION(A, p, r)
    QUICKSORT(A, p, q-1)
    QUICKSORT(A, q+1, r)

PARTITION(A, p, r)
x=A[r]
i=p-1
for j = p to r - 1
  if A <= x
     i = i + 1
     exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i + 1

そして、私はこのC＃コードを作りました：

private void quicksort(int[] input, int low, int high)
{
    int pivot_loc = 0;

    if (low < high)
        pivot_loc = partition(input, low, high);
    quicksort(input, low, pivot_loc - 1);
    quicksort(input, pivot_loc + 1, high);
}

private int partition(int[] input, int low, int high)
{
    int pivot = input[high];
    int i = low - 1;

    for (int j = low; j < high-1; j++)
    {
        if (input[j] <= pivot)
        {
            i++;
            swap(input, i, j);
        }
    }
    swap(input, i + 1, high);
    return i + 1;
}



private void swap(int[] ar, int a, int b)
{
    temp = ar[a];
    ar[a] = ar[b];
    ar[b] = temp;
}

private void print(int[] output, TextBox tbOutput)
{
    tbOutput.Clear();
    for (int a = 0; a < output.Length; a++)
    {
        tbOutput.Text += output[a] + " ";
    }
}

このような関数を呼び出すquicksort(arr,0,arr.Length-1);と、このエラーが発生An unhandled exception of type 'System.StackOverflowException' occurredし、空の配列が渡されます...このような関数を呼び出すと、この行でquicksort(arr,0,arr.Length);エラーが発生しますが、配列は正常に渡されました。Index was outside the bounds of the array.int pivot = input[high];

私もこのように印刷したいのですprint(input,tbQuick);が、クイックソートが終了したときに印刷されるようにどこに配置すればよいですか?

4

7 に答える 7

25

基本ケースの終了を適切に実装していませんでした。これによりquicksort、長さ 0 のサブリストでそれ自体への再帰が停止しなくなります。

これを変える：

if (low < high)
    pivot_loc = partition(input, low, high);
quicksort(input, low, pivot_loc - 1);
quicksort(input, pivot_loc + 1, high);

これに：

if (low < high) {
    pivot_loc = partition(input, low, high);
    quicksort(input, low, pivot_loc - 1);
    quicksort(input, pivot_loc + 1, high);
}
于 2012-11-30T15:36:50.737 に答える
16

Deestanの答えに加えて、これも間違っています：

for (int j = low; j < high-1; j++)

そのはず：

for (int j = low; j < high; j++)
于 2012-11-30T15:49:12.487 に答える