// file:    quicksort.java
// author:  Robert Keller
// purpose: illustrating Quicksort

import java.lang.*;
import java.io.*;
import java.util.*;

class quicksort
  {
  private float a[];

  /**
    *  Calling quicksort constructor on array of floats sorts the array.
    *  Parameter N is the number of elements to be sorted.
   **/

  quicksort(float array[], int low, int high)
    {
    a = array;

    if( low >= high )
      return;				// basis case, <= 1 element

    float pivot = a[(low + high)/2];	// select pivot

    // shift elements <= pivot to bottom
    // shift elements >= pivot to top

    int i = low-1;
    int j = high+1;

    for( ; ; )
      {                             // find two elements to exchange
      do { i++; } while( a[i] < pivot );	// slide i up
      do { j--; } while( a[j] > pivot );	// slide j down

      if( i >= j ) break;			// if sliders meet or cross

      swap(i, j);                   // swap elements and continue
      }

    new quicksort(a, low, i-1);     // sort lower half
    new quicksort(a, j+1, high);    // sort upper half
    }


  /**
    *  swap(i, j) interchanges the values in a[i] and a[j]
   **/

  void swap(int i, int j)
    {
    float temp = a[i];
    a[i] = a[j];
    a[j] = temp;
    }


  /**
    *  test program for quicksort; reads arbitrarily-many numbers 
    *  from standard input, sorts them, then writes them to standard output.
   **/

  public static void main(String[] args)
    {
    StreamTokenizer in = new StreamTokenizer(System.in);

    int Size = 1;			// initial allocation
    int N = 0;				// number of elements in array
    float array[] = new float[Size];	// initial array allocation

    try
      {
      // while more numbers in file
      while( in.nextToken() != java.io.StreamTokenizer.TT_EOF )	
	{
	if( N == Size )			// if the array is full
	  {
	  array = reallocate(array);    // float the array size
	  Size *= 2;	
	  }
	array[N++] = (float)in.nval;	// put item in array
	}
      }
    catch(IOException e)
      {
      System.err.println("*** IOException caught");
      }

    Date startTime = new Date();

    System.err.println("Sorting started");

    new quicksort(array, 0, N-1);	// calling constructor sorts

    Date endTime = new Date();

    long time = endTime.getTime() - startTime.getTime();

    System.err.println("Sorting finished in " + time + " ms");

    for( int i = 0; i < N; i++ )
      {
      System.out.print(array[i] + " ");
      }    

    System.out.println();

    System.err.println("Sorting " + N + " elements using quicksort took " + 
                        time + " ms");
    }


  /**
    *  reallocate allocates a new array float the size of the original
    *  and copies the original into it.  The new array is returned.
   **/

  static float[] reallocate(float array[])
    {
    float[] newArray = new float[2*array.length];
    for( int i = 0; i < array.length; i++ )		// copy old array
      newArray[i] = array[i];    
    return newArray;
    }
  }