a1204773 - 11 months ago 92

C# Question

I found quicksort algorithm from this book

This is the algorithm

`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

And I made this c# code:

`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] + " ";

}

}

When I call function like this

`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];`

I also want to print it like this

`print(input,tbQuick);`

Answer Source

You did not properly implement the base case termination, which causes `quicksort`

to never stop recursing into itself with sublists of length 0.

Change this:

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

to this:

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