Merge Sort and Binary Search Homework Post
Merge sort and binary search homework blog post for AP CSA
public class State {
public String name;
public String governor;
public State(String nameInput, String governorInput) {
name = nameInput;
governor = governorInput;
}
public String getName() {
return name;
}
public String getGovernor() {
return governor;
}
}
public class MergeSort {
public void toString(State[] states) {
String output = "";
for (int i = 0; i < states.length; i++) {
if (i == states.length - 1) {
output += states[i].getName() + "-" + states[i].getGovernor();
} else {
output += states[i].getName() + "-" + states[i].getGovernor() + ", ";
}
}
System.out.println(output);
}
public void sort(String arr[], int l, int r) {
// As long as the component is large enough to be divide, keeping running the functions
if (l < r) {
// Find midpoint of current component, and run functions on it
int m = l + (r - l) / 2;
sort(arr, l, m);
sort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
public void merge(String[] arr, int l, int m, int r) {
// Size of first half
int n1 = m - l + 1;
// Size of second half
int n2 = r - m;
// Left array
String[] L = new String[n1];
// Right array
String[] R = new String[n2];
for (int i = 0; i < n1; ++i) {
L[i] = arr[l + i];
}
for (int j = 0; j < n2; ++j) {
R[j] = arr[m + 1 + j];
}
int i = 0, j = 0;
// Initial index of main array
int k = l;
while (i < n1 && j < n2) {
// Use compareTo function to compare alphabetical standings of words. Merge sort takes place, as words with characters earlier
// in the alphabet are added to arr first
if (L[i].compareTo(R[j]) <= 0) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// Add any remaining elements in the left array
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
//Add any remaining in the right array
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public void sort2(State arr[], int l, int r) {
// As long as the component is large enough to be divide, keeping running the functions
if (l < r) {
// Find midpoint of current component, and run functions on it
int m = l + (r - l) / 2;
sort2(arr, l, m);
sort2(arr, m + 1, r);
merge2(arr, l, m, r);
}
}
public void merge2(State[] arr, int l, int m, int r) {
// Size of first half
int n1 = m - l + 1;
// Size of second half
int n2 = r - m;
// Left array
State[] L = new State[n1];
// Right array
State[] R = new State[n2];
for (int i = 0; i < n1; ++i) {
L[i] = arr[l + i];
}
for (int j = 0; j < n2; ++j) {
R[j] = arr[m + 1 + j];
}
int i = 0, j = 0;
// Initial index of main array
int k = l;
while (i < n1 && j < n2) {
// Use compareTo function to compare alphabetical standings of words. Merge sort takes place, as words with characters earlier
// in the alphabet are added to arr first
if (L[i].getName().compareTo(R[j].getName()) <= 0) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// Add any remaining elements in the left array
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
//Add any remaining in the right array
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public static void main(String[] args) {
String[] words = {"apple", "cucumber", "egg", "banana", "strawberry", "blueberry", "kiwi"};
System.out.println("Unsorted array:");
for (String item : words) {
System.out.print(item + " ");
}
System.out.println("");
MergeSort myObj = new MergeSort();
myObj.sort(words, 0, words.length - 1);
System.out.println("Sorted array:");
for (String item : words) {
System.out.print(item + " ");
}
System.out.println("");
State ohio = new State("Ohio", "DeWine");
State california = new State("California", "Newsom");
State newYork = new State("New York", "Hochul");
State massachusetts = new State("Massachusetts", "Healey");
State indiana = new State("Indiana", "Holcomb");
State[] states = {ohio, california, newYork, massachusetts, indiana};
System.out.println("Unsorted states:");
myObj.toString(states);
System.out.println("");
myObj.sort2(states, 0, states.length - 1);
System.out.println("Sorted states:");
myObj.toString(states);
System.out.println("");
}
}
MergeSort.main(null);
public class BinarySearch {
public static int search(int[] arr, int key, int min, int max) {
// Check if current min and max have a range between them
if (min <= max) {
// Get middle index of current searchable range
int mid = (min + max)/2;
// Conditionals to check if element is found or if the range should be changed
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
// No need to check elements below previous mid
min = mid;
} else if (arr[mid] > key) {
// No need to check elements above previous mid
max = mid;
}
// Recursive calls until index of searched element is found
return search(arr, key, min, max);
}
return -1;
}
public void sort(int arr[], int l, int r) {
// As long as the component is large enough to be divide, keeping running the functions
if (l < r) {
// Find midpoint of current component, and run functions on it
int m = l + (r - l) / 2;
sort(arr, l, m);
sort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
public void merge(int[] arr, int l, int m, int r) {
// Size of first half
int n1 = m - l + 1;
// Size of second half
int n2 = r - m;
// Left array
int[] L = new int[n1];
// Right array
int[] R = new int[n2];
for (int i = 0; i < n1; ++i) {
L[i] = arr[l + i];
}
for (int j = 0; j < n2; ++j) {
R[j] = arr[m + 1 + j];
}
int i = 0, j = 0;
// Initial index of main array
int k = l;
while (i < n1 && j < n2) {
// Use compareTo function to compare alphabetical standings of words. Merge sort takes place, as words with characters earlier
// in the alphabet are added to arr first
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// Add any remaining elements in the left array
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
//Add any remaining in the right array
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public static void main(String[] args) {
// Combining merge sort and binary search to sort and search an array
int[] array = {1, 67, 45, 5, 9, 23, 7, 3};
for (int item : array) {
System.out.print(item + " ");
}
System.out.println("");
BinarySearch myObj = new BinarySearch();
myObj.sort(array, 0, array.length - 1);
for (int item : array) {
System.out.print(item + " ");
}
System.out.println("");
System.out.println("Index of 45: " + myObj.search(array, 45, 0, array.length - 1));
}
}
BinarySearch.main(null);