Scribd
Upload
16 views12 pages

Code HS 10.3.5

The document contains Java code for various search and sorting algorithms, including binary search, linear search, and merge sort. It features classes that implement these algorithms, along with methods for testing their performance on arrays of different sizes. Additionally, the code includes print statements for debugging and tracking the number of comparisons made during searches and recursive calls during sorting.

Uploaded by

Karthik Bhattar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
16 views12 pages

Code HS 10.3.5

The document contains Java code for various search and sorting algorithms, including binary search, linear search, and merge sort. It features classes that implement these algorithms, along with methods for testing their performance on arrays of different sizes. Additionally, the code includes print statements for debugging and tracking the number of comparisons made during searches and recursive calls during sorting.

Uploaded by

Karthik Bhattar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 12

public class BinaryExplorer {

public static void main(String[] args) {


int[] testArray = {3, 6, 12, 18, 24, 34, 54, 64, 87, 100};
binaryRec(testArray, 87, 0, testArray.length - 1);
}
/**
* Add Print statements to the binaryRec method:
*
* Print Starting, ending, and midpoint values.
*
* Print when you find a match
*
* Print if you are too high or too low.
*
**/
public static int binaryRec(int[] array, int target, int begin, int end) {
if (begin <= end)
{
int mid = (begin + end) / 2;

System.out.println("Value at start index: " + array[begin]);


System.out.println("Value at mid index: " + array[mid]);
System.out.println("Value at end index: " + array[end]);

// Base Case
if (target == array[mid]) {
System.out.println("Target equals mid!");
return mid;
}

if (target < array[mid]) {


System.out.println("Target is less than mid!");
return binaryRec(array, target, begin, mid - 1);
}

if (target > array[mid]) {


System.out.println("Target is greater than mid!");
return binaryRec(array, target, mid + 1, end);
}
}
return -1; //Alternate Base Case - not found
}
}
import java.util.*;
public class CompareSearch
{
public static void main(String[] args)
{
System.out.println("Table of comparison counts");
System.out.println("Length\t\tBinary Search\tLinear Search");
testArrayOfLength(10);
testArrayOfLength(100);
testArrayOfLength(1000);
testArrayOfLength(10000);
testArrayOfLength(100000);
}

public static void testArrayOfLength(int length)


{
int[] arr = generateArrayOfLength(length);
int index = (int)(Math.random() * length);
int elem = arr[index];
System.out.println(length + "\t\t" + binarySearch(arr, elem) + "\t\t" + linearSearch(arr,
elem));
}

public static int[] generateArrayOfLength(int length)


{
int[] arr = new int[length];
for(int i = 0; i < length; i++)
{
arr[i] = (int)(Math.random() * 100);
}

Arrays.sort(arr);

return arr;
}

public static int binarySearch(int[] array, int number)


{
int low = 0;
int high = array.length - 1;
int comparisons = 0;
while (low <= high)
{
int mid = (low + high) / 2;
comparisons++;

if (array[mid] == number)
{
return comparisons;
}
else if(array[mid] < number)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}

return comparisons;
}

public static int linearSearch(int[] array, int number)


{
int comparisons = 0;

for (int i = 0; i < array.length; i++)


{
comparisons++;

if (array[i] == number)
{
return comparisons;
}
}

return comparisons;
}
}

import java.util.*;
public class BinarySearchTest {
static int count;
public static void main(String[] args) {
testBinarySearch(100);
testBinarySearch(1000);
testBinarySearch(10000);
testBinarySearch(100000);
}

public static void testBinarySearch(int size) {


int[] array = generateArrayOfLength(size);

int randomIndex = (int)(Math.random() * size);


int target = array[randomIndex];

int maxIterations = binaryMax(size);

count = 0;

int result = binaryRec(array, target, 0, array.length - 1);

System.out.println("Array Size: " + size);


System.out.println("Max iterations: " + maxIterations);
System.out.println("Actual iterations: " + count);
System.out.println();
}

public static int binaryRec(int[] array, int target, int begin, int end) {
if (begin <= end)
{
int mid = (begin + end) / 2;
count++;

if (target == array[mid]) {
return mid;
}

if (target < array[mid]) {


return binaryRec(array, target, begin, mid - 1);
}

if (target > array[mid]) {


return binaryRec(array, target, mid + 1, end);
}
}
return -1;
}

public static int[] generateArrayOfLength(int length)


{
int[] arr = new int[length];
for(int i = 0; i < length; i++)
{
arr[i] = (int)(Math.random() * 100);
}
Arrays.sort(arr);
return arr;
}

private static int binaryMax(int length) {


return (int) (Math.log(length) / Math.log(2)) + 1;
}
}

public class MergeSortPrint {

public static void main(String[] args) {


int[] myArray = {20, 9, 13, 34, 11, 22, 13, 10};
System.out.print("Unsorted: ");
for (int num : myArray) {
System.out.print(num + " ");
}
System.out.println("\n");

mergeSort(myArray, myArray.length);

System.out.print("Sorted: ");
for (int num : myArray) {
System.out.print(num + " ");
}
System.out.println();
}

public static void mergeSort(int[] current, int length) {


if (length < 2) {
return;
}

System.out.println("Splitting ...");
int mid = length / 2;
int[] left = new int[mid];
int[] right = new int[length - mid];

System.out.print("*** Left Half: ");


for (int i = 0; i < mid; i++) {
left[i] = current[i];
System.out.print(left[i] + " ");
}
System.out.println();

System.out.print("*** Right Half: ");


for (int i = mid; i < length; i++) {
right[i - mid] = current[i];
System.out.print(right[i - mid] + " ");
}
System.out.println("\n");

mergeSort(left, mid);
mergeSort(right, length - mid);

merge(current, left, right);

System.out.print("*** Sorted so Far: ");


for (int n : current) {
System.out.print(n + " ");
}
System.out.println("\n");
}

public static void merge(int[] current, int[] left, int[] right) {


System.out.println("Merging ... ");
int leftSize = left.length;
int rightSize = right.length;

int i = 0, j = 0, k = 0;
while (i < leftSize && j < rightSize) {
if (left[i] <= right[j]) {
current[k++] = left[i++];
} else {
current[k++] = right[j++];
}
}
while (i < leftSize) {
current[k++] = left[i++];
}
while (j < rightSize) {
current[k++] = right[j++];
}
}
}

import java.util.ArrayList;

public class SortTester {

public static void main(String[] args) {


int[] testArray;
long startTime, endTime;
int arraySize = 50000;

// Random Array
testArray = makeRandomArray(arraySize);
startTime = System.currentTimeMillis();
Sorter.mergeSort(testArray, testArray.length);
endTime = System.currentTimeMillis();
System.out.println("Random Array: " + (endTime - startTime) + " ms");

// Almost Sorted Array


testArray = makeAlmostSortedArray(arraySize);
startTime = System.currentTimeMillis();
Sorter.mergeSort(testArray, testArray.length);
endTime = System.currentTimeMillis();
System.out.println("Almost Sorted Array: " + (endTime - startTime) + " ms");

// Reverse Array
testArray = makeReverseArray(arraySize);
startTime = System.currentTimeMillis();
Sorter.mergeSort(testArray, testArray.length);
endTime = System.currentTimeMillis();
System.out.println("Reverse Array: " + (endTime - startTime) + " ms");
}

/**
* This method returns an array in random order
* @param number- the length of the desired almost sorted array
* @return array - returns an array length number.
*/
public static int[] makeRandomArray(int number){
int[] array = new int[number];
ArrayList<Integer> sorted = new ArrayList<Integer>(number);
// Create the sorted list
for (int i = 0; i < number; i++){
sorted.add(i);
}

// Now shuffle it.


int index = 0;
while (sorted.size() > 0){
int randomIndex = (int)(Math.random()*sorted.size());
array[index] = sorted.remove(randomIndex);
index ++;
}

return array;
}

/**
* This method returns an array in reverse order starting from the parameter number
* and going to the value 0.
* @param number- the length of the desired almost sorted array
* @return array - returns an array length number. Index 0 is the value number, and
* index array.length-1 is 0
*/
public static int[] makeReverseArray(int number)
{
int[] array = new int[number];
int counter = number;
for(int i = 0; i < number; i++)
{
array[i] = counter;
counter--;
}
return array;
}

/**
* This method returns an array that is almost sorted, but the last index
* and last index-1 are switched.
* @param number- the length of the desired almost sorted array
* @return array - returns an array length number with index array.length - 1
* and array.length- 2 swapped.
*/
public static int[] makeAlmostSortedArray(int number)
{
int[] array = new int[number];
for(int i= 0; i < number; i++)
{
array[i] = i+1;
}
int temp = array[array.length-1];
array[array.length-1] = array[array.length - 2];
array[array.length - 2] = temp;
return array;

}
}

import java.util.ArrayList;

public class MergeSortCounter {

private static int numCalls;

public static void main(String[] args) {


int[] sizes = {100, 1000, 10000, 100000};

for (int size : sizes) {


numCalls = 0;
int[] arr = makeRandomArray(size);
mergeSort(arr, arr.length);
System.out.println(
"Number of recursive calls with "
+ size
+ " elements: "
+ numCalls
);
}
}

public static void mergeSort(int[] current, int length) {


numCalls++;
if (length < 2) {
return;
}
int mid = length / 2;
int[] left = new int[mid];
int[] right = new int[length - mid];

for (int i = 0; i < mid; i++) {


left[i] = current[i];
}
for (int i = mid; i < length; i++) {
right[i - mid] = current[i];
}

mergeSort(left, mid);
mergeSort(right, length - mid);
merge(current, left, right);
}

public static void merge(int[] current, int[] left, int[] right) {


int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
current[k++] = left[i++];
} else {
current[k++] = right[j++];
}
}
while (i < left.length) {
current[k++] = left[i++];
}
while (j < right.length) {
current[k++] = right[j++];
}
}

public static int[] makeRandomArray(int number) {


int[] array = new int[number];
ArrayList<Integer> pool = new ArrayList<>(number);
for (int i = 0; i < number; i++) {
pool.add(i);
}
int idx = 0;
while (!pool.isEmpty()) {
int r = (int)(Math.random() * pool.size());
array[idx++] = pool.remove(r);
}
return array;
}
}

import java.util.ArrayList;

public class SortTester {

public static void main(String[] args) {


int arraySize = 20000;
long startTime, endTime;

int[] testArray = makeRandomArray(arraySize);


startTime = System.currentTimeMillis();
Sorter.selectionSort(testArray);
endTime = System.currentTimeMillis();
System.out.println("Selection Sort: " + (endTime - startTime) + " ms");

testArray = makeRandomArray(arraySize);
startTime = System.currentTimeMillis();
Sorter.insertionSort(testArray);
endTime = System.currentTimeMillis();
System.out.println("Insertion Sort: " + (endTime - startTime) + " ms");

testArray = makeRandomArray(arraySize);
startTime = System.currentTimeMillis();
Sorter.mergeSort(testArray, testArray.length);
endTime = System.currentTimeMillis();
System.out.println("Merge Sort: " + (endTime - startTime) + " ms");
}

public static int[] makeRandomArray(int number){


int[] array = new int[number];
ArrayList<Integer> pool = new ArrayList<>(number);
for (int i = 0; i < number; i++) {
pool.add(i);
}
int idx = 0;
while (!pool.isEmpty()) {
int r = (int)(Math.random() * pool.size());
array[idx++] = pool.remove(r);
}
return array;
}
}

You might also like