Invented (or discovered?) by C.A.R. Hoare in 1962. The most used sort algorithm. My take is that its efficiency is not so much due to reducing the number of comparisons, but rather that it is also very efficient in number of exchanges. Worst case is still O(n2), both for comparisons and exchanges. Interestingly enough, it does not work well when the array is almost sorted, or has some quasi-sorted patterns. This is why some consider 'randomizing' prior to sorting with quick sort. Often seen as a generalization of bubblesort. It can also be very demanding in stack use. Unfortunatley, our visualizer does not show that.
class QuickSort extends AlgoTri {
QuickSort (int t, VueTris v) { super("QuickSort", t, v);
}
void sort(int from, int to) {
delay (ext); // emulates recursion's & stack cost
int pivot=item((from+to)/2);
int ma=to; int mi=from;
do {
while(compare_val(pivot, ma)<0) ma--;
while(compare_val(pivot, mi)>0) mi++;
if(mi <= ma) {
if (mi != ma)
exchange(ma, mi);
ma--; mi++;
}
} while (ma>=mi);
if (from < ma) sort(from, ma);
if (to > mi) sort(mi, to);
}
public void sort () {
sort(0,size-1);
}
};
Some local often used improvements over quicksort: use the median of 3 values to improve chances of partitioning right, and use insertion sort on small lists instead of recursion, to minimize stack use and because partitioning is not efficient on small quasi ordered lists. Note that the 'quasi-ordered' conditions, as we implemented it, is one of the cases where these optimizations do not work well.
class QuickerSort extends AlgoTri {
QuickerSort (int t, VueTris v) { super("QuickerSort", t,
v); }
void insert_sort (int from, int to) {
delay (ext); // emulates recursion's & stack cost
if (to > from) {
for (int i = from+1; i <= to; i++) {
for (int j = i; j > from; j--) {
if (compare(j, j-1)<0)
exchange(j, j-1);
else break;
}
}
}
}
void sort(int from, int to) {
delay (ext); // emulates recursion's & stack cost
int pivot;
// choose the median of three of the values as a pivot
if (compare(to, from) > 0) {
if (compare((from+to)/2, to) > 0) pivot=item(to);
else {
if (compare((from+to)/2, from) > 0)
pivot=item((from+to)/2);
else pivot=item(from);
}
} else {
if (compare((from+to)/2, from)>0) pivot=item(from);
else {
if (compare((from+to)/2, to) > 0)
pivot=item((from+to)/2);
else pivot=item(to);
}
}
int ma=to; int mi=from;
do {
while(compare_val(pivot, ma)<0) ma--;
while(compare_val(pivot, mi)>0) mi++;
if(mi <= ma) {
if (mi != ma)
exchange(ma, mi);
ma--; mi++;
}
} while (ma>=mi);
// if array is small, do insertion instead of recursion
if (Math.abs(ma - from) > 10) sort(from, ma);
else insert_sort(from, ma);
if (Math.abs(to - mi) > 10) sort(mi, to);
else insert_sort(mi, to);
}
public void sort () {
sort(0,size-1);
}
};