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

*/

import java.util.Vector;
import java.io.*;

public class QuickSort
{
    private Vector array;
    
    public QuickSort(FileInput f){
      array = new Vector();
      while (!f.eof()){
		   array.add(f.getString());
		}
    
    } 
    // Sorts entire array
    public void sort()
    {
       sort( 0, array.size() - 1);
      // for (int i=0;i<array.size();i++)
         //System.out.println(array.elementAt(i));
    }

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

    protected int compare(Comparable a, Comparable b)
    {
       return a.compareTo(b);
    }

    protected int partition(int start, int end)
    {
        int left, right;
        Comparable partitionElement;

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

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

        return left;
    }

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

        temp = array.elementAt(i);
        array.setElementAt(array.elementAt(j), i);
        array.setElementAt(temp, j);
    }
    
    public void printFile(File f){
       try {
        FileOutputStream fstream = new FileOutputStream(f);
        PrintStream target = new PrintStream(fstream);
	    for (int i=0;i<array.size();i++)
	        target.println(array.elementAt(i));
       }
       catch (FileNotFoundException e) {
			System.out.println("File not found.");
		}        
	    
    }
    
    public void printFrequencies(File f){
      int[] A = new int[30];
      for (int i=0;i<array.size();i++)
         A[((String)array.elementAt(i)).length()]++; 
      
      try {
        FileOutputStream fstream = new FileOutputStream(f);
        PrintStream target = new PrintStream(fstream);
	     for (int j=0;j<30;j++)
	        target.println("The length " + j + "=" + A[j]); 
       }
       catch (FileNotFoundException e) {
			System.out.println("File not found.");
		}             
    
    }
}