package com.company;

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        // Code which tests the selectionSort() method.  We'll create arrays of various
        // sizes, some that are already sorted and some that are not, and call selectionSort
        // on them.  We have a separate method which checks the results.

        // Array with just a single element (already sorted).
        double[] array1 = { 12.4 };
        double[] result1 = selectionSort(array1);
        assert isArraySorted(result1);

        // Array with 3 elements, unsorted.
        double[] array2 = { 12.4, 7.5, -1.1 };
        double[] result2 = selectionSort(array2);
        assert isArraySorted(result2);

        // Array with 5 elements, sorted.
        double[] array3 = { -5.4, -1.1, 6.2, 9.8, 73.0 };
        double[] result3 = selectionSort(array3);
        assert isArraySorted(result3);

        // Array with 8 elements, unsorted.
        double[] array4 = { 99.9, -41.3, 73.0, -17.4, -8.1, 23.7, 106.2, 49.4 };
        double[] result4 = selectionSort(array4);
        assert isArraySorted(result4);

        // Array with 20 randomly-generated elements between 0 - 1000.
        double[] array5 = new double[20];
        for (int i = 0; i < array5.length; i++) {
            array5[i] = Math.random() * 1000.0;
        }
        double[] result5 = selectionSort(array5);
        assert isArraySorted(result5);
    }

    /**
     * An implementation of the selection sort algorithm to sort an array of floating-point numbers.
     * Selection sort works by "selecting" the smallest element in the array and placing it first,
     * then the next-smallest element and placing it second, etc., until all elements are selected
     * and placed properly.
     * @param array Array to be sorted.
     * @return A sorted version of the passed-in array.
     */
    public static double[] selectionSort(double[] array) {
        for(int a = 0; a < array.length - 1; a++) {
            int min_idx = a;
            for(int b = a + 1; b < array.length; b++) {
                if(array[b] < array[min_idx]) {
                    min_idx = b;
                }
            }
            double temp_arr = array[min_idx];
            array[min_idx] = array[a];
            array[a] = temp_arr;
        }
        return array;
    }

    /**
     * Check to see if an array of doubles are sorted.
     *
     * Precondition:  there are no duplicate elements.
     * @param array The array of doubles to check.
     * @return  true if the array is sorted, false otherwise.  Returns true for an array of length 0
     */
    public static boolean isArraySorted(double[] array) {
        // For an array of length 0, there's nothing to check, so we
        // just return true.
        if (array.length < 1) {
            return true;
        }

        // We compare every element in the array to the previous element; if it's less than
        // or equal to the previous element, the array isn't sorted, so we return false.  (The
        // reason we can include "or equal to" in our check is because we have the precondition
        // in all of our tests that none of the original arrays have duplicate items.
        for (int i = 1; i < array.length; i++) {
            if (array[i] <= array[i-1]) {
                return false;
            }
        }

        // If we make it to the end of the array without returning false, it means all of the
        // elements are in increasing order, so we can return true that the array is sorted.
        return true;
    }
}