public class Sort
{
    // Precondition: 	provide array[] an array of integers in any order
    //                  size the number of integers in the array
    // Postcondition: 	returns array[] with integers sorted from left
    //                	to right in ascending order using selection sort
    //                	algorithm
    public static void selectionSort(int array[], int size)
    {
            // Set endPos to be the right most element in the array.
            // Decrease endPos by one each iteration as number of sorted
            // elements grows in the array.
            for (int endPos=size-1; endPos>0; endPos--)
            {
                    // Start this scan of the unsorted elements in the array
                    // by assuming the first element is the largest.
                    int maxPos = 0;

                    // Scan the unsorted elements of the array looking for
                    // position of largest element.
                    for (int index=0; index<=endPos; index++)
                    {
                            if (array[maxPos] < array[index]) 
                            {
                                    maxPos = index;
                            }
                    }

                    // Swap value of last unsorted element in array
                    // with value of largest unsorted element in array.
                    int temp = array[maxPos];
                    array[maxPos]=array[endPos];
                    array[endPos]=temp;
            }
    }

    // Precondition: 	provide array[] an array of integers in any order
    //                  size the number of integers in the array
    // Postcondition: 	returns array[] with integers sorted from left
    //                	to right in ascending order using bubble sort
    //                	algorithm
    public static void bubbleSort(int array[], int size) 
    {
            for (int endPos=size-1; endPos>0; endPos--)
            {
                    // Starting at the beginning of the array.  Bubble up the largest
                    // unsorted value in the array.  To do this, move the largest value from 
                    // left to right by looking at array value pairs.  Swap pair values if
                    // if the left is greater than right value.  Stop when you've reached the
                    // sorted values in the array.

                    for (int index=0; index<endPos; index++)
                    {
                            // swap pair values if left greater than right
                            if (array[index]>array[index+1])
                            {
                                    // swap array[bubble_pos] and array[bubble_pos+1]
                                    int temp = array[index];
                                    array[index] = array[index+1];
                                    array[index+1]=temp;
                            }
                    }
            }
    }

    // Precondition: 	provide array[] an array of integers in any order
    //                  size the number of integers in the array
    // Postcondition: 	returns array[] with integers sorted from left
    //                	to right in ascending order using insertion sort
    //                	algorithm
    public static void insertionSort(int array[], int size)
    {
            // start at position 1 because position 0 is sorted
            for (int nextUnsortedPos=1; nextUnsortedPos<size; nextUnsortedPos++)
            {
                    int index;
                    // Save the unsorted value, we're about to lose it
                    int temp = array[nextUnsortedPos];

                    // Move from RIGHT to LEFT through the sorted portion of the
                    // array.  Keep shifting values in array one to the right
                    // until we find temp's position.  We find temp's position when:
                    // (1) We run off the left end of the array or (temp should be copied 
                    //     to array[0])
                    // (2) We find a value which is less than or equal to temp (temp 
                    //     should be copied to array[index+1])
                    for (index=nextUnsortedPos-1; index>=0; index--)
                    {
                            // Did we find the position in the sorted array for temp?
                            if (array[index]<=temp)
                            {
                                    break;
                            }
                            // Otherwise, shift array value one to the right
                            else
                            {
                                    array[index+1] = array[index];
                            }
                    }

                    // index is location of value which is smaller than temp
                    // index+1 is location we need to copy temp into
                    array[index+1] = temp;
            }
    }

    // Precondition: 	provide array[] an array of integers in any order
    //                  size the number of integers in the array
    // Postcondition: 	outputs contents of array to standard out
    public static void displayArray(final int array[], int size)
    {
            for (int i=0; i<size; i++)
            {
                    System.out.print(array[i] + " ");
            }
            System.out.println();

    }

    // Precondition: 	provide array[] an array of integers
    //                  size the number of integers in the array
    // Postcondition: 	array[] is populated with random integers between 0 and 100000
    public static void populateArray(int array[], int size)
    {
            for (int i=0; i<size; i++)
            {
                array[i]= (int)(Math.random() * 1000000) + 1;
            }

    }

    // Precondition: 	provide array[] an array of integers
    //                  size the number of integers in the array
    // Postcondition: 	array[] is populated with an ordered set of integers between where each
    //                  integer differs randomly from its neighbor by no more than 10
    public static void populateSortedArray(int array[], int size)
    {
        for (int i = 0; i < size; i++)
        {
            if (i == 0)
                array[i] = (int)(Math.random() * 100) + 1;
            else
                array[i] = (int)(Math.random() * 100) + 1 + array[i - 1];
        }
    }

    public static void main(String[]args)
    {
            int score[] = {99, 95, 79, 89, 77};
            int size=5;

            //populateArray(score,size);
            System.out.println("Array unsorted is: ");
            //displayArray(score,size);

            long start = System.currentTimeMillis();
            bubbleSort(score,size);
            long stop = System.currentTimeMillis();

            System.out.println("time taken is: " + (stop - start) + " ms");

            System.out.println("Array sorted is: ");
            displayArray(score,size);

    }
}