Saturday, March 14, 2009

Quick Sort - Java Vector

Here is a small code snippet to sort a 2D Vector in Java.

//pos is the column number to be sorted with
private void quickSortVector(Vector v, int start, int end, int pos)
{
int i = start; // index of left-to-right scan
int k = end; // index of right-to-left scan

if (end - start >= 1) // check that there are at least two elements to sort
{
String pivot = (String)((Vector)v.elementAt(start)).get(pos); // set the pivot as the first element in the partition

try {
while (k > i) // while the scan indices from left and right have not met,
{
while (((String)((Vector)v.elementAt(i)).get(pos)).compareToIgnoreCase(pivot) <= 0 && i <= end && k > i) // from the left, look for the first
i++; // element greater than the pivot
while (((String)((Vector)v.elementAt(k)).get(pos)).compareToIgnoreCase(pivot) > 0 && k >= start && k >= i) // from the right, look for the first
k--; // element not greater than the pivot
if (k > i) // if the left seekindex is still smaller than
swapVector(v, i, k); // the right index, swap the corresponding elements
}
swapVector(v, start, k); // after the indices have crossed, swap the last element in
// the left partition with the pivot
quickSortVector(v, start, k - 1, pos); // quicksort the left partition
quickSortVector(v, k + 1, end, pos); // quicksort the right partition
}
catch (ArrayIndexOutOfBoundsException ae) {
System.out.println("Could not sort vector : Array out of bound exception for column "+ pos);
return;
}
catch (Exception e) {
System.out.println("Could not sort vector : Exception "+ e);
return;
}
}
else // if there is only one element in the partition, do not do any sorting
{
return; // the array is sorted, so exit
}
}

No comments:

Post a Comment