Implementing quicksort algorithm

algorithm, c#, quicksort

Solution

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

Problem

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?

Original source