/**
    FILE:           FindKthLargest.java
    AUTHOR:         Cheng, Jeff
    LAST CHANGE:    3-22-02
    Functions:      FindKth()--------> creates an array, may be presorted.
                    createAndFind()--> creates an array and find the
                                       kth largest element, may print
                                       array to the screen.
                    find()-----------> find the kth largest element
                    print()----------> print the entire array
                    split()----------> split the array around a pivot
                    
    COPYRIGHT:      You may use, modify, or distribute my code for 
                    non-commerical use only; you must cite me, Jeff Cheng, 
                    as the source. 
*/

package sorts;

class FindKthLargest{
    public static final int MAX_VALUE = 1000000;
    private int a[];
    
    public FindKthLargest(int arraySize, boolean presorted){
        a = new int[arraySize];
        
        if (presorted){  //  sorted array
            for (int i=0; i< a.length; i++){
                a[i] = i;
                }
        }
        else{
            //  seed the array elements randomly
            for (int i=0; i < a.length; i++){
                a[i] = (int)(Math.random()*MAX_VALUE);   
        }
        }
    }
    
    public static void createAndFind(int arraySize, boolean presorted, 
                                     int kthElement, boolean printIt){
        long timeBegan = 0;
        long timeFinished = 0; 
        long timeNeeded = 0;
        
        //  create an array of integers;
        FindKthLargest kthLargestFinder 
        = new FindKthLargest(arraySize, presorted);

        //  time the sorting algorithm
        timeBegan = System.currentTimeMillis();
        
        System.out.println("\t Element = " + 
                           kthLargestFinder.find(kthElement));

        timeFinished = System.currentTimeMillis();
        timeNeeded = timeFinished - timeBegan;
        System.out.println("\t Finding the " + kthElement + "th element" +
                            " took = " + timeNeeded + " milliseconds.");       
                                
        if (printIt){
            System.out.println("\n\t Now print the array elements:\n" +
                               "\t Note if the array is too large, " +
                               "the elements may run off the screen!\n");
            kthLargestFinder.print();
            }                        
    }
    
  public void print(){
    for (int i = 0; i < a.length;i++){
        System.out.println(" a[" + i + "] = " + a[i] + "\n");
        }
 }
 
 public int find(int a[], int low, int high, int kthLargest) {
	
    int pivot = split(a, low, high);
	
    if ((kthLargest-1) == pivot){   
        return a[pivot]; 
        }
	else if ((kthLargest-1) > pivot){ 
	    return find(a, pivot+1, high, kthLargest);
	    }
    else {   //  ((nthElem-1) < pivot)
	    return find(a, low, pivot-1, kthLargest);
	    } 
    }

public int split(int a[], int low, int high){
    //  we are trying to split the array like so:
    //  a[ elements < pivot] || a[pivot] || a[elements > pivot]
    int lastSmallIndex = low;
    int temp = 0;
    
    for (int i = low + 1; i <= high; i++){
        if (a[i] < a[low]){
            //  if a smaller element is found, we extend the "small"
            //  region to the right and swap it with temp
            lastSmallIndex++;
            temp = a[i];
            a[i] = a[lastSmallIndex];
            a[lastSmallIndex] = temp;
            }
    }
    
    //  now the array has the small region and the large region,
    //  relative to the pivot that is.
    //  but remember that we are pivoting around the element, a[low]
    //  all we need to do now is swap the last element in the small
    //  region with the pivot element to create the following 3 parts:
    //  small region, pivot element, and large region.
    temp = a[low];  //  the rightful middle element
    a[low] = a[lastSmallIndex]; //  last element in small region
    a[lastSmallIndex] = temp;
    
    return lastSmallIndex;
    }
    
 public int find(int nthElement){
    return find(a, 0, a.length-1, nthElement);}
 // used to avoid the use of static int data member
}