a1204773 - 1 year ago 120
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?

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);
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download