import java.util.*;

class Sorts {
    /*
     *  Utility Functions
     */
    private static void swap(float[] arr, int a, int b) {
        // swap arr[a] and arr[b]
        // may come in handy in your code (or might not)
        float tmp;
        tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }


    public static void builtinSort(float[] arr) {
        // wrapper for the built-in sorting algorithm
        // ...just to make it work like the others.
        Arrays.sort(arr);
    }
    
    /*
     *  Selection Sort
     */
    public static void selectionSort(float[] arr) {
        // implementation of selection sort.  Sorts arr in-place.
        int min, i;
        float tmp;
        for(int pos=0; pos<arr.length-1; pos++ ) {
            // find next-smallest element
            min = pos;
            for(i=pos+1; i<arr.length; i++) {
                if ( arr[min] > arr[i] ) {
                    min = i;
                }
            }
            // swap it into place
            swap(arr, pos, min);
        }
    }
    
    /*
     *  Quicksort
     */
    static Random r = new Random();
    public static void quickSort(float[] arr, int first, int last) {
        // randomized quicksort implementation
        // sorts arr[first] to arr[last-1].
        if ( last-first <= 1 ) {
            // base case
            // could set the base case around 10 and then:
            //   insertionSort(arr, first, last);
            return;
        }
        
        float pivot, tmp;
        int pivotpos, left=first+1, right=last-1;
        
        // choose random pivot
        pivotpos = first + r.nextInt(last-first);
        // other possible pivotpos values: first; (first+last)/2;
        pivot = arr[pivotpos];
        swap(arr, first, pivotpos);
        
        while ( left < right ) {
            // find something too big to be before the pivot
            while ( left < right && arr[left] <= pivot ) {
                left++;
            }
            // find something too small to be after the pivot
            while ( left < right && arr[right] >= pivot ) {
                right--;
            }
            // swap them (if that's really what we found)
            if ( left < right ) {
                swap(arr, left, right);
                left++;
                right--;
            }
        }
        if ( arr[left] > pivot ) {
            // whether or not to do this depends how we exited the loop.
            left--;
        }
        swap(arr, first, left); // pivot at position 'left'--it's final pos

        quickSort(arr, first, left);
        quickSort(arr, left+1, last);
    }

    public static void quickSort(float[] arr) {
        quickSort(arr, 0, arr.length);
    }
    
    /*
     *  Your code...
     */



}