/** This program is intended to be used with the book "Java 6 -- What Do You Want To Do?"
 * by Steven P. Warr and is distributed free of charge and without and expectations of remuneration.
 * Chapter ALG   NOTE most program names begin with the title of the chapter in which
 * they are intended to be used.   Copyright 2010 Steven P. Warr All rights reserved
 */

import java.io.*;   		// needed so you can use the File class
import java.util.*;  		//needed for Scanner
public class Alg10
{
	public static void main(String[ ] args) throws IOException
		{
		     int numItems = 0;
			 int x = 0;
			 File filename = new File("nameOfFile.data");  
			 Scanner inFile = new Scanner(filename);
			 while(inFile.hasNext())  // This loop counts the items in the file
					{                 // so that the array can be dimensioned
						inFile.nextDouble();  //to the correct size
						x++;
					}	
			 inFile.close();		
			 numItems = x;		
             double [ ]price = new double [numItems]; 	//Dimension the array to numItems.
			 x = 0;		                       			// reinitialize LCV
			 inFile = new Scanner(filename);   			//reset data file to beginning
			 while(inFile.hasNext())
					{
				          price[x] = inFile.nextDouble( );  // read one item and 
 				   											//point to the next one.
					      x ++;  				// add one so there is a new index.
					}
			 inFile.close();		
             System.out.println("\nOriginal list\n");
		     for(int c = 0;c < price.length ; c++)   
				System.out.println(c + ". " + String.format("%7.2f",price[c]));  
             quickSort(price, 0, price.length-1);
             System.out.println("\nSorted list\n");
		     for(int c = 0;c < price.length ; c++)   
				System.out.println(c + ". " + String.format("%7.2f",price[c]));  
        }
    public static void quickSort(double [] list,int from, int to)
    {
    	if (from >= to)                    //base case - ends recursion
    		return;
    	int p = part(list, from, to);
    	quickSort(list,from, p);
    	quickSort(list,p + 1, to);	
    }	    
    public static int part(double [] list, int from, int to)
    {
    	double pivot = list[from];
    	int x = from - 1;
    	int y = to + 1;
    	while( x < y)
    		{
    			x ++;
    			while (list[x] < pivot)
    			       x ++;
    			y --;
    			while (list[y] > pivot)
    			       y --;
    		    if (x < y)
    		        swap (list,x , y);  
    		} 
    	return y;	       
    }
    public static void swap(double[] list, int x , int y)
    {
	    double temp = list[x];    //The same swap algorithm as in sequential,  
        list[x] = list[y];        //selection, and bubble sorts.
        list[y] = temp;      	 
    }

}