Sorting Algorithms

public class Algorithms {
    /**
     * nlogn - Quicksort
     * n^2 - Insertion Sort
     */
    public static void main(String[] args) {
        int[] quickData = {10, 9, 1, 18, 5, 6, 2, 12, 15, 7};
        int[] insertionData = {10, 9, 1, 18, 5, 6, 2, 12, 15, 7};

        // QUICK-SORT
        printArray(quickData);
        checkArrayForIntegrity(quickData, "Pre - QuickSort");
        QuickSort quickSortObject = new QuickSort();
        // Begin the sort with the smallest at element 0, largest at array.length and move inwards recursively
        quickSortObject.sort(quickData, 0, quickData.length - 1);
        printArray(quickData);
        checkArrayForIntegrity(quickData, "Post - QuickSort");


        // INSERTION SORT
        printArray(insertionData);
        checkArrayForIntegrity(insertionData, "Pre - InsertionSort");

        InsertionSort insertionSortArray = new InsertionSort();
        int[] postInsertionSortData = insertionSortArray.sort(insertionData);

        printArray(postInsertionSortData);
        checkArrayForIntegrity(postInsertionSortData, "Post - InsertionSort");

    }


    private static double getTotalRuntime(double startingRunTime) {
        return System.currentTimeMillis() - startingRunTime;
    }

    private static void printArray(int[] inputArray) {
        System.out.print("\nArray Status: ");
        for (int currentArrayFocus : inputArray) {
            System.out.print(currentArrayFocus + " ");
        }
        System.out.print("\n");
    }

    // Returns a check on whether or not the new array has been properly sorted from greatest to least
    private static void checkArrayForIntegrity(int[] array, String consoleStringMessage) {
        boolean status = true;
        for (int i = 0; i < array.length && status; i++) {
            // As soon as there's a falsity this essentially breaks the loop and forces it to return false
            if (i < (array.length - 1)) {
                // ^^^^ Make sure it iterates up till the last element to prevent an OutOfBoundsException
                // Resulting in it stopping at the 2nd-last element
                status = array[i] < array[i + 1];
            }
        }
        System.out.println("Integrity : [" + consoleStringMessage + "] : [" + status + "]\n");
    }
}


class InsertionSort extends Algorithms {

    // This didn't work :(

    /*
    private int[] inputArray = {};

    int[] sort(int[] inputArray) {

        int j, currentNumber;
        // Start the sort at the 2nd element and compare backwards, could start at zero and compare forwards but I
        // rather wouldn't because of it being easier to ArrayOutOfBoundsException
        for (int i = 1; i < inputArray.length; i++) {
            currentNumber = inputArray[i];
            j = i;

            // Check so that the i-1 focus we have is in the array limitations, and that it's greater than the number,
            // then if so then move it over in position
            while (j > 0 && inputArray[j] > currentNumber) {
                inputArray[i] = inputArray[j - 1];
                j--;
            }
            inputArray[j] = currentNumber;
        }

        // Store the array to reference later cause apparently is doesn't want to behave :(
        this.inputArray = inputArray;
        return this.inputArray;
    }
    */

    // But this did :)
    public int[] sort (int[] inputArray) {
        int pivot;   // Self Explanatory
        int backwardsComparisonKey;
        // ^^^^ When we make the comparison, use this to iterate back in the array as many times as necessary until fine
        int currentNumberKey; // What number we're looking at initially on the pivot
        int tempSwapNumber; // Self explanatory as well, but the space we use to swap the numbers each time we iterate

        // Set the pivot at 1 so we can look back. Could also do it at the start and compare forwards but this works
        for (pivot = 1; pivot < inputArray.length; pivot++) {
            currentNumberKey = inputArray[pivot];
            // Sets up a simple way to reference the number before the 'focus' of the loop
            backwardsComparisonKey = pivot - 1;

            // Wouldn't want the comparison we're making to go into the negative portions of the array would we? ;)
            // Also, guarantee that it will only swap the pivot and the number before it if it's actually less than it
            while (backwardsComparisonKey >= 0 && currentNumberKey < inputArray[backwardsComparisonKey]) {
                tempSwapNumber = inputArray[backwardsComparisonKey];
                inputArray[backwardsComparisonKey] = inputArray[backwardsComparisonKey + 1];
                inputArray[backwardsComparisonKey + 1] = tempSwapNumber;

                // Iterate the key backwards and see if the number before the backwardsComparisonKey can also be swapped
                //  out or not.
                backwardsComparisonKey--;
            }
        }
        // Tried to do this with a void method like in quicksort, but it didn't seem to like that and treated it as
        // though it was static. Not sure why, but this works also, so why not.
        return inputArray;
    }

}

class QuickSort extends Algorithms {
    /**
     * Requires two portions to the algorithm, one partitions and one sorts.
     * In this case I decided to set the pivot at the end of the array, as per the first line of the partition()
     * method.
     */
    private int partition(int[] inputArray, int lowestIndex, int highestIndex) {

        int pivotPoint = inputArray[highestIndex]; // Use the last element in the [current] array to be the pivot
        int i = (lowestIndex - 1);

        for (int j = lowestIndex; j < highestIndex; j++) {
            /**
             ^^ Goes from the lowestIndex to highestIndex and iterates through (of the sample size we're
             recursively looking at right now)
             If the current element is smaller or equal to the pivot - go ahead and swap
             */
            if (inputArray[j] <= pivotPoint) {
                i++; // Moves where we need to consider the elements because an element has to go behind.
                // Needs to swap the index of the j
                int temp = inputArray[i];
                inputArray[i] = inputArray[j];
                inputArray[j] = temp;
            }
        }

        // Swap the smaller element and the highest targeted element (which may be the pivot) around

        int temp = inputArray[i + 1];
        inputArray[i + 1] = inputArray[highestIndex];
        inputArray[highestIndex] = temp;

        // Returns one above the 'pivot'
        return i + 1;
    }

    void sort(int[] inputArray, int lowestIndex, int highestIndex) {
        // Only run if the low is actually the lowestIndex - Base case for recursion so it doesn't stack overflow
        if (lowestIndex < highestIndex) {
//            System.out.println("Entering Sort Method, lowest index " + lowestIndex + "[:" + inputArray[lowestIndex]
//                    + "] and highest index " + highestIndex + "[:" + inputArray[highestIndex] + "]");

            int partitionIndex = partition(inputArray, lowestIndex, highestIndex);
            // This is where we actually recursively sort stuff above and below the pivot point
//            System.out.println("Starting Recursive Spawning");

            sort(inputArray, lowestIndex, partitionIndex - 1); // Covers first half
            sort(inputArray, partitionIndex + 1, highestIndex); // Covers second half
        }
    }

}