Is this a correct implementation of quicksort? [closed]
Question
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);
}
}
Solution 5
public static void quicksort( Comparable [ ] a ) {
quicksort( a, 0, a.length - 1 );
}
private static final int CUTOFF = 10;
private static void quicksort( Comparable [ ] a, int low, int high ) {
if( low + CUTOFF > high )
insertionSort( a, low, high );
else {
int middle = ( low + high ) / 2;
if( a[ middle ].compareTo( a[ low ] ) < 0 )
swapReferences( a, low, middle );
if( a[ high ].compareTo( a[ low ] ) < 0 )
swapReferences( a, low, high );
if( a[ high ].compareTo( a[ middle ] ) < 0 )
swapReferences( a, middle, high );
swapReferences( a, middle, high - 1 );
Comparable pivot = a[ high - 1 ];
int i, j;
for( i = low, j = high - 1; ; ) {
while( a[ ++i ].compareTo( pivot ) < 0 )
;
while( pivot.compareTo( a[ --j ] ) < 0 )
;
if( i >= j )
break;
swapReferences( a, i, j );
}
swapReferences( a, i, high - 1
quicksort( a, low, i - 1 ); // Sort small elements
quicksort( a, i + 1, high ); // Sort large elements
}
}
public static final void swapReferences( Object [ ] a, int index1, int index2 )
{
Object tmp = a[ index1 ];
a[ index1 ] = a[ index2 ];
a[ index2 ] = tmp;
}
private static void insertionSort( Comparable [ ] a, int low, int high ) {
for( int p = low + 1; p <= high; p++ ) {
Comparable tmp = a[ p ];
int j;
for( j = p; j > low && tmp.compareTo( a[ j - 1 ] ) < 0; j-- )
a[ j ] = a[ j - 1 ];
a[ j ] = tmp;
}
}
From http://java-blackberry.blogspot.com/2007/12/quick-sort-implementation-with-median.html
OTHER TIPS
1 small point- there's a potential int overflow here:
(lo + hi) / 2
Take this opportunity to learn how to write a unit-test. (Google on "junit", for example). Generate large arrays and make sure that they are sorted properly, for example: arrays filled with random numbers, arrays filled with 0, 1, Integer.MAX_INT. Try to provoke things like integer overflow and other weird cornercases.
EDIT: My bad for missing the java tag, sorry... The below is C# generic quickSort... I'll leave it here anyway for .net readers...
It looks ok at first glance, but how about this generic one?
public class QuickSort<T> where T : IComparable<T>
{
#region private variable to sort inplace
readonly private IList<T> itms;
#endregion private variable to sort inplace
#region ctor
private QuickSort() { } // Hide parameterless constructor
/// <summary>
/// Constructor requires IList<T> T must implement CompareTo() method.../>
/// </summary>
/// <param name="Lst">List<T> of elements to sort</param>
public QuickSort(IList<T> Lst):this)() { itms = Lst; }
#endregion ctor
#region public sort method
public void Sort() { Sort(0, itms.Count - 1); }
/// <summary>
/// Executes QuickSort algorithm
/// </summary>
/// <param name="L">Index of left-hand boundary of partition to sort</param>
/// <param name="R">Index of right-hand boundary of partition to sort</param>
private void Sort(long L, long R)
{
// Calls iSort (insertion-sort) for partitions smaller than 5 elements
if (R - L < 4) iSort(L, R);
else
{
long i = (L + R) / 2, j = R - 1;
// Next three lines to set upper and lower bounds
if (itms[L].CompareTo(itms[i]) > 0) Swap(L, i);
if (itms[L].CompareTo(itms[R]) > 0) Swap(L, R);
if (itms[i].CompareTo(itms[R]) > 0) Swap(i, R);
Swap(i, j);
// --------------------------------
T p = itms[j]; // p = itms[j] is pivot element
i = L;
while (true)
{
while (itms[++i].CompareTo(p) < 0) {}
while (itms[--j].CompareTo(p) > 0) {}
if (j < i) break;
Swap(i, j);
}
Swap(i, R - 1);
Sort(L, i); // Sort Left partition -- HERE WAS TYPO BUG
Sort(i + 1, R); // Sort Right partition
}
}
#endregion public sort method
#region private Helper methods
private void Swap(long L, long R)
{
T t = itms[L];
itms[L] = itms[R];
itms[R] = t;
}
private void iSort(long L, long R)
{
for (long i = L; i <= R; i++)
{
T t = itms[i];
long j = i;
while ((j > L) && (itms[j - 1].CompareTo(t) > 0))
{
itms[j] = itms[j - 1];
j--;
}
itms[j] = t;
}
}
#endregion private Helper methods
}
And here's a javascript version... QuickSort(a, comp, desc)
- a is of course the array to be sorted.
- comp is the compare function that has to take two values and return -1, 0 or +1 depending on how the 2 arguments should sort.
desc is boolean to reverse the sort order.
function QuickSort(a, comp, desc) { function defComp(L, R) {return((L>R)? 1: (L<R)? -1: 0);} var cmp = (comp)? comp: defComp; var siz = a.length; qSort(0, siz-1); if (desc) reverse(); // ------------------ function qSort(L, R) { if (R - L < 4) {iSort(L, R);} // insertion-sort-- else { var i = parseInt((L+R) /2), j=R-1; if (cmp(a[L], a[i]) > 0) swap(L,i); if (cmp(a[L], a[R]) > 0) swap(L,R); if (cmp(a[i], a[R]) > 0) swap(i,R); swap(i,j); // ------------------------------------------ var p=a[j]; // p=a[j] is pivot i=L; while (true) { while(cmp(a[++i], p) < 0); while(cmp(a[--j], p) > 0); if (j < i) break; swap(i,j); } swap(i,R-1); qSort(L,i); // Left Partition qSort(i+1,R); // Right Partition } } function swap(L,R) {var t=a[L]; a[L]=a[R]; a[R]=t;} function reverse() {for(var i=0; i<parseInt(siz/2); i++) swap(i,(siz-i-1));} // insertion-sort function iSort(L,R) { var j,t; for(var i=L; i<=R; i++) { t = a[i], j = i; while ((j>L) && (cmp(a[j-1], t) > 0)) {a[j] = a[j-1]; j--;} a[j] = t; } } }