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