/*
   Quick Sort Class
	
	author: A.D. Gunawardena
	course: 15-111 Java Programming 
	section: 
	date: 	10/2/01

*/

import java.io.*;

import java.util.*;

public class QuickSort
{
    // Sorts entire array
    public static void sort(Vector array)
    {
        sort(array, 0, array.size() - 1);
    }

    // Sorts partial array
    public static void sort(Vector array, int start, int end)
    {
        int p;
        if (end > start)
        {
            p = partition(array, start, end);
            sort(array, start, p-1);
            sort(array, p+1, end);
        }
    }

    protected static int compare(Object a, Object b)
    {
       return a.compare(b);
    }

    protected static int partition(Vector array, int start, int end)
    {
        int left, right;
        Object partitionElement;

        // Arbitrary partition start...there are better ways...
        partitionElement = array.elementAt(end);

        left = start - 1;
        right = end;
        while (true)
        {
            while (compare(partitionElement, array.elementAt(++left)) == 1)
            {
                if (left == end) break;
            }
            while (compare(partitionElement, (Sortable)array.elementAt(--right)) == -1)
            {
                if (right == start) break;
            }
            if (left >= right) break;
            swap(array, left, right);
        }
        swap(array, left, end);

        return left;
    }

    protected static void swap(Vector array, int i, int j)
    {
        Object temp;

        temp = array.elementAt(i);
        array.setElementAt(array.elementAt(j), i);
        array.setElementAt(temp, j);
    }
}