MIDTERM - InsertionSortTest

/*

Insertion Sort Midterm
*/

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 MIDTERM
*/
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 14 - Merge Sort Test

/*

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 - Insertion Sort Test

/*
Assignment 13
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 palce 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();
}
}


---------------------------------------------------------------------------------


/*
Assignment 13
main function
*/
public class InsertionSortTest
{
public static void main( String[] args )
{
//create object to preform 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 - Selection Sort Test

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

Towers of Hanoi

/* 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) disk 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 (disk-1) disk 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 usedto 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);
}
}

Binary Search Test

/*
Assignment #
*/

import java.util.Random;
import java.util.Arrays;

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

//create array of any size and fill with random int
public BinaryArray( int size )
{
data = new int[ size ]; //create space for array

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

Arrays.sort( data );
}

//preform binary search in data
public int binarySearch( int searchElement )
{
int low = 0; //low end of search area
int high = data.length - 1; //high end of search area
int middle = (low + high + 1)/2; //middle element
int location = -1; //retunr value; -1 if not found

do //loop to search element
{
//print remaining elements of array
System.out.print( remainingElements( low, high ) );

//output spaces for alignment
for(int i=0; i
System.out.print( " " );
System.out.println( " * " ); //indicate current middle

//if the element is found at the middle
if(searchElement == data[ middle ])
location = middle; //location is the current middle

//middle element is too high
else if(searchElement
high = middle - 1; //eliminate the higher half
else //middle element too low
low = middle + 1; //eliminate the lower half

middle = (low + high + 1)/2; //recalculate the middle
}

while( (low <= high) && (location == -1) );

return location; //return location of search key
}

//method to output certain values in array
public String remainingElements( int low, int high )
{
StringBuilder temporary = new StringBuilder();

//output spaces for alignment
for(int i=0; i
temporary.append(" ");

//output elements left in array
for(int i=low; i<=high; i++)
temporary.append( data[ i ] + " " );

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

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

-------------------------------------------------------------------

import java.util.Scanner;

public class BinarySearchTest
{
public static void main( String args[] )
{
// create Scanner object to input data
Scanner input = new Scanner( System.in );

int searchInt; //search key
int position; //location of search key in array

//create array and output it
BinaryArray searchArray = new BinaryArray( 15 );
System.out.println( searchArray );

//get input from user
System.out.print( "Please enter an integer value (-1 to quit): ");
searchInt = input.nextInt(); //read an int from user
System.out.println();

//repeadtedly ubput an integer; -1 terminates the program
while(searchInt != -1)
{
//use binary search to try to find integer
position = searchArray.binarySearch( searchInt );

//return value of -1 indicates indicates integer was not found
if(position == -1)
System.out.println( "The integer " + searchInt + " was not found.\n" );

else
System.out.println( "The integer " + searchInt + " was found in position "
+ position + ".\n" );

//get input from user
System.out.print( "Please enter an integer value (-1 to quit): " );
searchInt = input.nextInt(); //read an int from user
System.out.println();
}
}
}