sorts :: quick sort
public class QuickSortDemo
{
public static void main (String[] args)
{
int a[] = {53, 43, 63, 93, 103, 83, 13, 33, 23, 6, 73};// last subscript: 10
System.out.println ("53, 43, 63, 93, 103, 83, 13, 33, 23, 6, 73");
System.out.println ("");
quickSort (a, 0, 10);
System.out.println ("");
// output sort
for (int i = 0 ; i < a.length ; i++)
{
System.out.print (a [i] + " ");
}
} // end of main
public static void quickSort (int a[], int start, int end)
{
if (start < end)
{
/*
rearrange into 2 sub arrays, from a[start] to a[split]
and from a[split + 1] to a[end] in such a way that every
element in the left part is less than or equal to the every
element in the right part
*/
int split = partition (a, start, end);
// show split
System.out.println ("split " + split);
System.out.println ("");
// sort the left sublist
quickSort (a, start, split);
// now sort the right sublist
quickSort (a, split + 1, end);
}
}
// rearrange the portion of the array a[] so that each element
// in a[start]....a[split] is less than or equal to each element in
// a[split + 1].....a[end], and return the index split
public static int partition (int a[], int start, int end)
{
// start with 2 indices, top and bottom,
// just outside of the list we are partitioning
int bottom = start - 1;
int top = end + 1;
// pick a value pivot.Arrange the list according to: <= or >= to pivot
int pivot = a [start];
System.out.println ("pivot is " + pivot);
// walk bottom and top towards each other, using them to swap array
// elements as we go, and stopping when bottom and top pass each other
while (bottom < top)
{
// walk until you find an element that is not in its current sublist
do
{
bottom++;
}
while (a [bottom] < pivot);
do
{
top--;
}
while (a [top] > pivot);
// swap a[bottom] and a[top], thus putting the values in the
// correct sublist
int temp = a [bottom];
a [bottom] = a [top];
a [top] = temp;
}
// undo the last swap that took place after the bottom and top
// indices passed each other
int temp = a [bottom];
a [bottom] = a [top];
a [top] = temp;
// finally, return split index
return top;
} // end of partition method
} // end of QuickSortDemo class