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?
Step 1 − Pick an element from an array, call it as pivot element. Step 2 − Divide an unsorted array element into two arrays. Step 3 − If the value less than pivot element come under first sub array, the remaining elements with value greater than pivot come in second sub array.
Overview of quicksort. Like merge sort, quicksort uses divide-and-conquer, and so it's a recursive algorithm. The way that quicksort uses divide-and-conquer is a little different from how merge sort does.
Example of Quick Sort:Comparing 44 to the right-side elements, and if right-side elements are smaller than 44, then swap it. As 22 is smaller than 44 so swap them. Now comparing 44 to the left side element and the element must be greater than 44 then swap them. As 55 are greater than 44 so swap them.
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);
}
In addition to Deestan's answer, you also have this wrong:
for (int j = low; j < high-1; j++)
It should be:
for (int j = low; j < high; j++)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With