a1204773 a1204773 - 1 month ago 17
C# Question

Implementing quicksort algorithm

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);
I get this error
An unhandled exception of type 'System.StackOverflowException' occurred
it pass empty array... when call function like this
quicksort(arr,0,arr.Length);
I get error
Index was outside the bounds of the array.
on this line
int pivot = input[high];
but array passed successfully.

I also want to print it like this
print(input,tbQuick);
but where to place it so it would print when quicksort finished?

Answer

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);
}