package sorts;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/**
 * An exercise with sorting algorithms.
 *
 * Complete the stub methods.
 *
 * Here is an example of output from the
 * the completed program:
 *
 *
 * Partly sorted list.
 *  14  17  34  48  63  76  82  99  16  33  72  59  28  20  13  49 
 * 
 * Sorted list.
 *   1   6  14  14  20  23  42  43  50  58  64  69  74  79  87  98 
 * 
 * After swapping elements 3 and 5, the list is:
 *   1   6  14  23  20  14  42  43  50  58  64  69  74  79  87  98 
 * 
 * Unsorted list.
 *  93  18  35  13  33  28  73  66  91   8  44  86  24  70  20  39 
 * 
 * Value of smallest integer in list = 8
 * 
 * Position of smallest integer in list = 9
 * 
 * Position of smallest integers in that 
 *  part of the list that begins at index 8 = 9
 * 
 * After sorting with the selection sort: 
 *   8  13  18  20  24  28  33  35  39  44  66  70  73  86  91  93 
 * 
 *  26  34  36  59  61  65  83  90  50  23   5  56  17  50  96  16 
 * The element at index 8 belongs at position 3
 * 
 * Here is the list with a hole created at the right place.
 *  26  34  36 null  59  61  65  83  90  23   5  56  17  50  96  16 
 * 
 * Here an unsorted list.
 *  11  27  22  64  73  76  63  24  10  54  24  14  45  34  11  54 
 * And here is the same list after sorting with insertion sort.
 *  10  11  11  14  22  24  24  27  34  45  54  54  63  64  73  76 
 * 
 * Here is a list whose two parts are sorted.
 *  20  34  43  48  50  51  55  86   1  36  61  76  81  86  88  95 
 * 
 * Here is the list after the merge of the two parts.
 *   1  20  34  36  43  48  50  51  55  61  76  81  86  86  88  95 
 *
 * @author Your Name
 * @version 02 April 2018
 */
public class Sorts {

    /**
     * The maximum number of integers that
     * should put on a line of output.
     */
    public static final int INTEGERS_ON_A_LINE = 16;

    /**
     * The largest non-negative value that a random
     * number (to be added to a list) may assume.
     */
    public static final int MAX_VALUE = 99;

    /**
     * A random number generator.
     */
    public static final Random rng = new Random();

    /**
     * Create a list of non-negative random numbers whose
     * first part is sorted.
     *
     * @param sortedSize is the number of elements (a non-negative integer)
     * in the sorted part of the list
     * @param totalSize is the total number of elements (a non-negative integer)
     * in the list
     * @param maxValue is the largest value that any
     * of the non-negative random numbers that will be
     * generated and added to the list
     * @return is the list of random integers
     */
    public static List<Integer> makePartlySortedList( int sortedSize, 
            int totalSize, int maxValue ) {

        List<Integer> result = new ArrayList<>();

        return result;
    } // makePartlySortedList( int, int, int )

    /**
     * Create a list of non-negative integers.
     *
     * @param size is the number of integers in the list.
     * @param maxValue is the largest value that any of
     * the non-negative random numbers that are generated
     * and added to the list can assume
     * @return is the list of random integers
     */
    public static List<Integer> makeSortedList( int size, int maxValue ) {

        List<Integer> result = new ArrayList<>();

        return result;
    } // makeSortedList( int, int )

    /**
     * Create a list the contains random non-negative
     * integers and is divided into two parts, both
     * of which are sorted
     *
     * @param prefixSize is the number of integers in
     * the first part of the list
     * @param suffixSize is the number of integers in 
     * the second part of the list
     * @return the list of random integers with its
     * first and second parts sorted
     */
    public static List<Integer> makeTwoPartList( int prefixSize,
            int suffixSize, int maxValue ) {
        List<Integer> result = new ArrayList<>();

        return result;
    } // makeTwoPartList( int, int, int )

    /**
     * Create an unsorted list of random, non-negative integers.
     *
     * @param size is the number of integers in the list
     * @param maxValue is the largest non-negative value that
     * any of the random integers may assume
     * @return the list of integers
     */
    public static List<Integer> makeUnsortedList( int size, int maxValue ) {
        List<Integer> result = new ArrayList<>();

        return result;
    } // makeUnsortedList( int )

    /**
     * Find the smallest integer in a list of integers
     *
     * @param data is the list in which to sort
     * @return the smallest integer in the list
     */
    public static int minimum( List<Integer> data ) {
        return 0;
    } // minimum( List<Integer> )

    /**
     * Find the index of the smallest integer in a list
     * of integers
     *
     * @param data is the list in which to sort
     * @return the index of the smallest integer in the list
     */
    public static int positionOfMinimum( List<Integer> data ) {
        return 0;
    } // positionOfMinimum( List<Integer> )

    /**
     * Find the index of the smallest integer in that
     * part of a list of integers that begins at a specified
     * position
     *
     * @param startingIndex is the position of that part of the
     * list in which to begin the search
     * @param data is the list in which to search
     * @return the index of the smallest integer in that part
     * the list that begins the specified position
     */
    public static int positionOfMinimum( int startingIndex, List<Integer> data ) {
        return 0;
    } // positionOfMinimum( List<Integer> )

    /**
     * Exchange the values of the elements at 
     * positions i and j in a list.
     *
     * @param i is an index in the list and in the
     * interval [0, data.size() - 1]
     * @param j is an index in the list and in the
     * interval [0, data.size() - 1]
     * @param data is the list that contains the
     * two elements
     */
    public static void swap( int i, int j, List<Integer> data ) {

    } // swap( int, int, List<Integer> )

    /**
     * Sort a list of integers using the selection sort algorithm.
     *
     * @param data is the list to be sorted
     */
    public static void selectionSort( List<Integer> data ) {

    } // selectionSort( List<Integer> )

    /**
     * Find the position in the sorted part of a list
     * in which to insert the next element.
     *
     * This will be the last element (in a search from right
     * to left) that is greater than or equal to a given element 
     * 
     * @param index is the position at which to begin the left to
     * right search and is also the position of the element
     * to which all other elements in the search will be compared
     * @param data is the list in which to search
     * @return the index of the insertion point
     */
    public static int positionOfGE( int index, List<Integer> data ) {

        return 0;
    } // positionOfGE( int, List<Integer> )

    /**
     * Create a hole in a list into which to insert
     * an element in the next step of an insertion sort.
     *
     * @param i is the index of the element to be inserted
     * (0 <= j <= i <= data.size - 1)
     * @param j is the position at which the element is to
     * be inserted (0 <= j <= i <= data.size - 1)
     */
    public static void createHole( int i, int j, List<Integer> data ) {

    } // createHole( int, int,  List<Integer> )

    /**
     * Sort a list using the insertion sort algorithm.
     *
     * @param data is the list to be sorted
     */
    public static void insertionSort( List<Integer> data ) {

    } // insertionSort( List<Integer> )

    /**
     * Merge the two parts of a list (when those
     * two parts are already sorted)
     *
     * The two parts of the list will contain
     * consecutive elements elements of the list.
     *
     * The two parts need not make up the whole 
     * list---there may be other elements before and/or
     * after these two parts
     *
     * @param prefixStart is the index of the first
     * element in the first part of the list
     * @param suffixStart is the index of the first
     * element in the second part of the list
     * @param suffixEnd is the end of the list
     * element in the second part of the list
     * @param data is the list
     * @return the original list with the specified
     * two parts now sorted
     */
    public static void merge( int prefixStart,
            int suffixStart, int suffixEnd, List<Integer> data ) {

    } // merge( List<Integer>, List<Integer> )

    /**
     * Sort a list using the merge sort algorithm.
     *
     * @param data is the list to be sorted.
     */
    public static void mergeSort( List<Integer> data ) {

    } // mergeSort( List<Integer> )

    public static void printList( List<Integer> list ) {
        for( int i = 0; i < list.size(); i++ ) {
            System.out.printf( "%3d ", list.get(i) );
            if( i != 0 && i % INTEGERS_ON_A_LINE == 0 ) {
                System.out.println();
            } // if
        } // for
        System.out.println();
    } // printList( List<Integer> )

    public static void main( String [] args ) {

        List<Integer> a = makePartlySortedList( 8, INTEGERS_ON_A_LINE, MAX_VALUE );
        List<Integer> b = makeSortedList( INTEGERS_ON_A_LINE, MAX_VALUE );
        List<Integer> c = makeUnsortedList( INTEGERS_ON_A_LINE, MAX_VALUE );
        
        System.out.println( "Partly sorted list." );
        printList( a );
        System.out.println();

        System.out.println( "Sorted list." );
        printList( b );
        System.out.println();

        System.out.println( "After swapping elements 3 and 5, the list is:" );
        swap( 3, 5, b );
        printList( b );
        System.out.println();

        System.out.println( "Unsorted list." );
        printList( c );
        System.out.println();

        System.out.println( "Value of smallest integer in list = " +
            minimum( c ) );
        System.out.println();

        System.out.println( "Position of smallest integer in list = " +
            positionOfMinimum( c ) );
        System.out.println();

        System.out.println( "Position of smallest integers in that \n" +
            " part of the list that begins at index 8 = " +
            positionOfMinimum( 8, c ) );
        System.out.println();

        System.out.println( "After sorting with the selection sort: " );
        selectionSort( c );
        printList( c );
        System.out.println();

        a = makePartlySortedList( 8, INTEGERS_ON_A_LINE, MAX_VALUE );
        printList( a );
        int j = positionOfGE( 8, a );
        System.out.println( "The element at index 8 belongs at position " + j );
        System.out.println();

        System.out.println( "Here is the list with a hole created at the right place." );
        createHole( 8, j, a );
        printList( a );
        System.out.println();

        c = makeUnsortedList( INTEGERS_ON_A_LINE, MAX_VALUE );
        System.out.println( "Here an unsorted list." );
        printList( c );
        insertionSort( c );
        System.out.println( "And here is the same list after sorting with insertion sort." );
        printList( c );
        System.out.println();

        List<Integer> d = makeTwoPartList( 8, 8, MAX_VALUE );
        System.out.println( "Here is a list whose two parts are sorted." );
        printList( d );
        System.out.println();

        merge( 0, 8, d.size() - 1, d );
        System.out.println( "Here is the list after the merge of the two parts." );
        printList( d );

    } // main( String [] )

} // Sorts