Assignment #14 CS360

Assignment #1
"Merge Sort & Merge Sort Test"
10-21-10









/*

//Merge Sort

*/

import java.util.Random;

public class MergeSort
{
private int[] data; //array of values
private static 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 range 10-99
for( int i = 0; i < size; i++ )
data[i] = 10 + generator.nextInt( 90 );
}

//calls recursive split method to begin merge sorting
public void sort()
{
sortArray( 0, data.length - 1); //split entire array
}

//splits array, sort subarrays and merges subarrays into sorted array
private void sortArray( int low, int high )
{
//test 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 ) );

//split array in half; sort each half of array
sortArray( low, middle1 ); //first half of array
sortArray( middle2, high ); //second half of array

//merge 2 sorted arrays after split calls return
merge( low, middle1, middle2, high );
}
}

//merge 2 sorted subarrays into one sorted sub array
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 temp. work array
int[] combined = new int[data.length]; //working array

//output 2 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 2 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++];
}

//if array is empty
if( leftIndex == middle2 )
//copy in rest of right array
while( rightIndex <= right )
combined[combinedIndex++] = data[rightIndex++];
else
//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();

}

//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();
}

//method to output values in array
public String toString()
{
return subarray( 0, data.length - 1 );
}
}






/*

//main function

*/

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 );
}
}

Assignment #13 CS360

Assignment #13
"Insertion Sort & Insertion Sort Test"
10-21-10






/*

//Insertion Sort
*/

import java.util.Random;

public class InsertionSort
{
private int[] data; //array of values
private static Random generator = new Random();

//create array of given size to fill
public InsertionSort( int size)
{
data = new int[size]; //create space for arrays

//fill arrays with random numbers 10-99
for( int i = 0; i < size; i++ )
data[i] = 10 + generator.nextInt(90);
}

//sort array using insertion sort
public void sort()
{
int insert; //temp; variable to hold element to insert

//loop over data.length - elements
for( int next = 1; next < data.length; next++ )
{
//sort 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--;
}

data[moveItem] = insert; //place inserted element
printPass( next, moveItem ); //output pass of algorithm
}
}

//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 = index + 1; i < data.length; i++ )
System.out.print( data[i] + "");

System.out.print( "\n "); //for allignment

//indicate amount of array that is sorted
for( int i = 0; i <= pass; i++ )
System.out.print( "--" );
System.out.println( "\n" ); //add endline
}

//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();
}
}





/*

//main function

*/

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 ); //print unsorted array

sortArray.sort();

System.out.println( "Sorted array: ");
System.out.println( sortArray ); //print sorted array
}
}

Assignment #12 CS360

Assignment #12
"Selection Sort & Selection Sort Test"
10-14-10





/*

//Selection Sort Algorithm
*/

import java.util.Random;

public class SelectionSort
{
private int[] data; //array of value
private static Random generator = new Random();

//create array if given size and fill w/ random int
public SelectionSort( int size )
{
data = new int[size]; //create space for array

//fill array with random int 10-99
for(int i = 0; i < size; i++ )
data[i] = 10 + generator.nextInt( 90 );
}

//sort array using slection sort
public void sort()
{
int smallest; //index of smallest element

//loop over data length -1
for(int i = 0; i < data.length - 1; i++)
{
smallest = i; //first index of remaining array

//loops 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 elements into position
printPass( i + 1, smallest );
}
}

//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
}

//print a pass of algorigthm
public void printPass( int pass, int index )
{
System.out.print( String.format( "after pass %2d; ", pass) );

//output elements till selectem item
for (int i = 0; i < index; 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.println("\n"); //add endline
}

//method to output balues in array
public String toString()
{
StringBuilder temporary = new StringBuilder();

//iterate through array
for( int element : data)
temporary.append( element + " " );

temporary.append("\n");
return temporary.toString();
}
}

~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|

/*

//main function
*/

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 ); //print unsorted array

sortArray.sort(); //sort array

System.out.println( "Sorted Array:" );
System.out.println( sortArray ); //print sorted array
}
}

Assignment #11 CS360

Assignment #11
"Towers of Hanoi & Towers of Hanoi Test"
10-07-10





/*
Towers of Hanoi
*/


public class TowersOfHanoi
{
private int numDisks; //number of disks to move

public TowersOfHanoi( int disks )
{
numDisks = disks;
}

//recursively more disks between towers
public void solveTowers( int disks, int sourcePeg, int destinationPeg, int tempPeg)
{
//base case -- only one disk to move
if( disks == 1)
{
System.out.printf( "\n%d --> %d", sourcePeg, destinationPeg);
return;
}

//recursion step -- move (disk 1) disks from sourcePeg
//to tempPeg using destinationPeg
solveTowers( disks - 1, sourcePeg, tempPeg, destinationPeg );

//move last disk from sourcePeg to destinationPeg
System.out.printf( "\n%d --> %d", sourcePeg, destinationPeg );

//move (disks - 1) disks from tempPeg to destinationPeg
solveTowers( disks - 1, tempPeg, destinationPeg, sourcePeg );
}
}




~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|~|



/*
main function to be run
*/

public class TowersOfHanoiTest
{
public static void main( String args[])
{
int startPeg = 1; //value 1 used to indicate startPeg in output
int endPeg = 3; //value 3 used to indicate endPeg in output
int tempPeg = 2; //value 2 used to indicate tempPeg output
int totalDisks = 3; //number of disks
TowersOfHanoi towersOfHanoi = new TowersOfHanoi( totalDisks );

//initial nonrecursive call: move all disks
towersOfHanoi.solveTowers( totalDisks, startPeg, endPeg, tempPeg );
}
}