I would like to check if this is a correct implementation of QuickSort, It seems to be doing the job, but Am I missing out anything?
public class QuickSort implements Sorter {
public void sort(Comparable[] items) {
QuickSort(items, 0, items.length - 1);
}
static void QuickSort(Comparable[] items, int a, int b) {
int lo = a;
int hi = b;
if (lo >= hi) {
return;
}
Comparable mid = items[(lo + hi) / 2];
Comparable T;
while (lo < hi) {
while (items[lo].compareTo(mid)<0) {
lo++;
}
while (mid.compareTo(items[hi])<0) {
hi--;
}
if (lo < hi) {
T = items[lo];
items[lo] = items[hi];
items[hi] = T;
}
}
QuickSort(items, a, lo);
QuickSort(items, lo == a ? lo + 1 : lo, b);
}
}
fixed:
private static void quickSort(Comparable[] items, int a, int b) {
int i = a;
int j = b;
Comparable x = items[(a+ b) / 2];
Comparable h;
do {
while (items[i].compareTo(x) < 0) {
i++;
}
while (items[j].compareTo(x) > 0) {
j--;
}
if (i <= j) {
h = items[i];
items[i] = items[j];
items[j] = h;
i++;
j--;
}
} while (i <= j);
if (a < j) {
quickSort(items, a, j);
}
if (i < b) {
quickSort(items, i, b);
}
}
1. Quick sort uses which of the following algorithm to implement sorting? Explanation: Quick sort uses the technique of divide and conquer in order to sort a given array. It divides the array into two parts about the pivot and then apply a quick sort to both the parts.
In quick sort, a large array is divided into two arrays in which one holds values that are smaller than the specified value (Pivot), and another array holds the values that are greater than the pivot. After that, left and right sub-arrays are also partitioned using the same approach.
You can implement an iterative version of Quicksort with a queue rather than a stack.
If you define "in-place" as requiring a constant amount of memory, then quicksort is not "in-place" as it requires log(N) memory for the recursion. If you define "in-place" as more human-friendly "does not move the data outside the input structure", then quicksort is again not "in-place".
1 small point- there's a potential int overflow here:
(lo + hi) / 2
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