You are given the source code for four sorting algorithms, namely, insertion sort, selection sort, quick sort, and merge sort. Each algorithm is implemented in a single java source file, e.g., quick sort is in file QuickSort.java. Each sorting algorithm has a small driver program to test the algorithm, e.g., QuickSortTest.java is a program that creates a quick sort object and instructs the object to sort an array with 1,000 random integer elements. The Test.java files are given to you to demonstrate how to create and call the sorting classes. You will not be using them for the lab; however, you will be using the files that implement the sorting algorithms
Step 1:
Modify each sorting algorithm so that it keeps track of the number of comparisons it performs and the number of exchanges (swaps) it performs during a single sorting operation. Keep track of these numbers using two long integer counters; one to keep track of the number of comparisons and another to keep track of the number of swaps.
Step 2:
Write a driver program (i.e., a main program) that instantiates a selection sort, quick sort, merge sort, and insertion sort objects and then instructs each object to sort an array of 50,000 random integer elements, then 100,000 elements, then 200,000 elements, then 300,000 elements, and finally 400,000 elements. Your program should record the number of exchanges and comparisons for each algorithm andeach data set that was sorted. Your program should also keep track of how much time each sorting algorithm needed to sort each array. Hence, for each algorithm you should record the time elapsed for each of the five sorting processes [Hint: use Java's java.lang.System.currentTimeMillis()method, which returns a long integer that represents the current time in milliseconds. You will need to call this method twice, once just before the sorting process, and once right after the sorting process. The difference will be the time elapsed in milliseconds].
Step 3:
Write a simple graphics program that outputs a bar chart that visually depicts the relative performance of each sorting algorithm with respect to time, number of comparisons, and number of swaps for each data set (e.g., 50,000 -400,000 random integers). Use your imagination to create a suitable bar chart format. For example, one idea is to create 4 bar charts. Each one of the four bar charts will have the different sorting algorithms on the x-axis (i.e., insertion, selection, quick, merge) and one of: time, number of exchanges (swaps), number of comparisons on the y-axis.
Each algorithm will have 5 bars corresponding to the 5 data sets. The height of these bars will depend on the performance of the algorithm for that data set
import java.util.Arrays;
import java.util.Random;
public class InsertionSort
{
private int[] data; // array of values
private static final Random generator = new Random();
// create array of given size and fill with random integers
public InsertionSort( int size )
{
data = new int[ size ]; // create space for array
// fill array with random ints in range 10-99
for ( int i = 0; i < size; i++ )
data[ i ] = 10 + generator.nextInt( 90 );
} // end InsertionSort constructor
// sort array using insertion sort
public void sort()
{
int insert; // temporary variable to hold element to insert
// loop over data.length - 1 elements
for ( int next = 1; next < data.length; next++ )
{
// store value in current element
insert = data[ next ];
// initialize location to place element
int moveItem = next;
// search for place to put current element
while ( moveItem > 0 && data[ moveItem - 1 ] > insert )
{
// shift element right one slot
data[ moveItem ] = data[ moveItem - 1 ];
moveItem--;
} // end while
data[ moveItem ] = insert; // place inserted element
printPass( next, moveItem ); // output pass of algorithm
} // end for
} // end method sort
// print a pass of the algorithm
public void printPass( int pass, int index )
{
System.out.print( String.format( "after pass %2d: ", pass ) );
// output elements till swapped item
for ( int i = 0; i < index; i++ )
System.out.print( data[ i ] + " " );
System.out.print( data[ index ] + "* " ); // indicate swap
// finish outputting array
for ( int i = index + 1; i < data.length; i++ )
System.out.print( data[ i ] + " " );
System.out.print( "\n " ); // for alignment
// indicate amount of array that is sorted
for( int i = 0; i <= pass; i++ )
System.out.print( "-- " );
System.out.println( "\n" ); // add endline
} // end method printPass
// method to output values in array
public String toString()
{
return Arrays.toString( data );
} // end method toString
} // end class InsertionSort
public class InsertionSortTest
{
public static void main( String[] args )
{
// create object to perform insertion sort
InsertionSort sortArray = new InsertionSort( 10 );
System.out.println( "Unsorted array:" );
System.out.println( sortArray + "\n" ); // print unsorted array
sortArray.sort(); // sort array
System.out.println( "Sorted array:" );
System.out.println( sortArray ); // print sorted array
} // end main
} // end class InsertionSortTest
import java.util.Random;
public class MergeSort
{
private int[] data; // array of values
private static final Random generator = new Random();
// create array of given size and fill with random integers
public MergeSort( int size )
{
data = new int[ size ]; // create space for array
// fill array with random ints in range 10-99
for ( int i = 0; i < size; i++ )
data[ i ] = 10 + generator.nextInt( 90 );
} // end MergeSort constructor
// calls recursive split method to begin merge sorting
public void sort()
{
sortArray( 0, data.length - 1 ); // split entire array
} // end method sort
// splits array, sorts subarrays and merges subarrays into sorted array
private void sortArray( int low, int high )
{
// test base case; size of array equals 1
if ( ( high - low ) >= 1 ) // if not base case
{
int middle1 = ( low + high ) / 2; // calculate middle of array
int middle2 = middle1 + 1; // calculate next element over
// output split step
System.out.println( "split: " + subarray( low, high ) );
System.out.println( " " + subarray( low, middle1 ) );
System.out.println( " " + subarray( middle2, high ) );
System.out.println();
// split array in half; sort each half (recursive calls)
sortArray( low, middle1 ); // first half of array
sortArray( middle2, high ); // second half of array
// merge two sorted arrays after split calls return
merge ( low, middle1, middle2, high );
} // end if
} // end method sortArray
// merge two sorted subarrays into one sorted subarray
private void merge( int left, int middle1, int middle2, int right )
{
int leftIndex = left; // index into left subarray
int rightIndex = middle2; // index into right subarray
int combinedIndex = left; // index into temporary working array
int[] combined = new int[ data.length ]; // working array
// output two subarrays before merging
System.out.println( "merge: " + subarray( left, middle1 ) );
System.out.println( " " + subarray( middle2, right ) );
// merge arrays until reaching end of either
while ( leftIndex <= middle1 && rightIndex <= right )
{
// place smaller of two current elements into result
// and move to next space in arrays
if ( data[ leftIndex ] <= data[ rightIndex ] )
combined[ combinedIndex++ ] = data[ leftIndex++ ];
else
combined[ combinedIndex++ ] = data[ rightIndex++ ];
} // end while
// if left array is empty
if ( leftIndex == middle2 )
// copy in rest of right array
while ( rightIndex <= right )
combined[ combinedIndex++ ] = data[ rightIndex++ ];
else // right array is empty
// copy in rest of left array
while ( leftIndex <= middle1 )
combined[ combinedIndex++ ] = data[ leftIndex++ ];
// copy values back into original array
for ( int i = left; i <= right; i++ )
data[ i ] = combined[ i ];
// output merged array
System.out.println( " " + subarray( left, right ) );
System.out.println();
} // end method merge
// method to output certain values in array
public String subarray( int low, int high )
{
StringBuilder temporary = new StringBuilder();
// output spaces for alignment
for ( int i = 0; i < low; i++ )
temporary.append( " " );
// output elements left in array
for ( int i = low; i <= high; i++ )
temporary.append( " " + data[ i ] );
return temporary.toString();
} // end method subarray
// method to output values in array
public String toString()
{
return subarray( 0, data.length - 1 );
} // end method toString
} // end class MergeSort
public class MergeSortTest
{
public static void main( String[] args )
{
// create object to perform merge sort
MergeSort sortArray = new MergeSort( 10 );
// print unsorted array
System.out.println( "Unsorted:" + sortArray + "\n" );
sortArray.sort(); // sort array
// print sorted array
System.out.println( "Sorted: " + sortArray );
} // end main
} // end class MergeSortTest
import java.util.Random;
public class QuickSort
{
private int[] data; // array of values
private static Random generator = new Random();
// create array of given size and fill with random integers
public QuickSort( int size )
{
data = new int[ size ]; // create space for array
// fill array with random ints in range 10-99
for ( int i = 0; i < size; i++ )
data[ i ] = 10 + generator.nextInt( 90 );
} // end QuickSort constructor
// call recursive method quicksortHelper
public void sort()
{
quickSortHelper( 0, data.length - 1 );
} // end method sort
// recursive method to sort array using quicksort
private void quickSortHelper( int left, int right )
{
int pivot = partition( left, right );
if ( left < pivot - 1 ) // if more than one element on left
quickSortHelper( left, pivot - 1 ); // sort left side
if ( pivot + 1 < right ) // if more than one element on right
quickSortHelper( pivot + 1, right ); // sort right side
} // end method quickSortHelper
// partition the given range and return final index of pivot
private int partition( int left, int right )
{
int pivot = left; // index of pivot element
// loop until two edges meet
while ( true )
{
// search for data to right of pivot greater than pivot
while ( data[ right ] >= data[ pivot ] )
{
if ( right == pivot )
return pivot; // partitioning completed
--right; // move left one element
} // end while
swap( pivot, right ); // move right element into correct location
pivot = right--; // update pivot location and move right edge left
while ( data[ left ] <= data[ pivot ] )
{
if ( left == pivot )
return pivot; // partitioning completed
++left; // move right one element
} // end while
swap( pivot, left ); // move left element into correct location
pivot = left++; // update pivot location and move left edge right
} // end while
} // end method partition
// helper method to swap values in two elements
private void swap( int first, int second )
{
int temporary = data[ first ]; // store first in temporary
data[ first ] = data[ second ]; // replace first with second
data[ second ] = temporary; // put temporary in second
} // end method swap
// method to output values in array
public String toString()
{
StringBuilder temporary = new StringBuilder();
// iterate through array
for ( int element : data )
temporary.append( element + " " );
temporary.append( "\n" ); // add endline character
return temporary.toString();
} // end method toString
} // end class QuickSort
public class QuickSortTest
{
public static void main( String[] args )
{
// create object to perform selection sort
QuickSort sortArray = new QuickSort( 10 );
System.out.println( "Before:" );
System.out.println( sortArray ); // print unsorted array
sortArray.sort(); // sort array
System.out.println( "After:" );
System.out.println( sortArray ); // print sorted array
} // end main
} // end class QuickSortTest
import java.util.Arrays;
import java.util.Random;
public class SelectionSort
{
private int[] data; // array of values
private static final Random generator = new Random();
// create array of given size and fill with random integers
public SelectionSort( int size )
{
data = new int[ size ]; // create space for array
// fill array with random ints in range 10-99
for ( int i = 0; i < size; i++ )
data[ i ] = 10 + generator.nextInt( 90 );
} // end SelectionSort constructor
// sort array using selection sort
public void sort()
{
int smallest; // index of smallest element
// loop over data.length - 1 elements
for ( int i = 0; i < data.length - 1; i++ )
{
smallest = i; // first index of remaining array
// loop to find index of smallest element
for ( int index = i + 1; index < data.length; index++ )
if ( data[ index ] < data[ smallest ] )
smallest = index;
swap( i, smallest ); // swap smallest element into position
printPass( i + 1, smallest ); // output pass of algorithm
} // end outer for
} // end method sort
// helper method to swap values in two elements
public void swap( int first, int second )
{
int temporary = data[ first ]; // store first in temporary
data[ first ] = data[ second ]; // replace first with second
data[ second ] = temporary; // put temporary in second
} // end method swap
// print a pass of the algorithm
public void printPass( int pass, int index )
{
System.out.print( String.format( "after pass %2d: ", pass ) );
// output elements till selected item
for ( int i = 0; i < index; i++ )
System.out.print( data[ i ] + " " );
System.out.print( data[ index ] + "* " ); // indicate swap
// finish outputting array
for ( int i = index + 1; i < data.length; i++ )
System.out.print( data[ i ] + " " );
System.out.print( "\n " ); // for alignment
// indicate amount of array that is sorted
for( int j = 0; j < pass; j++ )
System.out.print( "-- " );
System.out.println( "\n" ); // add endline
} // end method printPass
// method to output values in array
public String toString()
{
StringBuilder temporary = new StringBuilder();
// iterate through array
for ( int element : data )
temporary.append( element + " " );
temporary.append( "\n" ); // add endline character
return Arrays.toString( data );
} // end method toString
} // end class SelectionSort
public class SelectionSortTest
{
public static void main( String[] args )
{
// create object to perform selection sort
SelectionSort sortArray = new SelectionSort( 10 );
System.out.println( "Unsorted array:" );
System.out.println( sortArray + "\n" ); // print unsorted array
sortArray.sort(); // sort array
System.out.println( "Sorted array:" );
System.out.println( sortArray ); // print sorted array
} // end main
} // end class SelectionSortTest