class MergeSort {
void merge(String arr[], int l, int m, int r) {
// Find the sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
String[] L = new String[n1];
String[] R = new String[n2];
/* Copy data to temp arrays */
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];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarray array
int k = l;
while (i < n1 && j < n2) {
if (L[i].compareTo(R[j]) <= 0) {
// MISSING CODE #1
arr[k] = L[i];
i++;
}
else {
// MISSING CODE #2
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void sort(String arr[], int l, int r) {
if (l < r) {
// COMMENT A
int m = l + (r - l) / 2;
// COMMENT B
sort(arr, l, m);
sort(arr, m + 1, r);
// COMMENT C
merge(arr, l, m, r);
}
}
static void printArray(String arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[]) {
String arr[] = { "Bananas", "Apples", "Cherry", "Eggplant", "Dragonfruit","Grape", "Fig", "Peach", "Orange" }; // initializing the string objects
System.out.println("Original Array:");
printArray(arr);
System.out.println();
MergeSort sort = new MergeSort();
sort.sort(arr, 0, arr.length - 1);
System.out.println("Sorted Array:");
printArray(arr);
}
}
MergeSort.main(null);
import java.util.ArrayList;
import java.util.List;
public class MergeSort <T extends Comparable<T>> {
public List<T> mergeSort(List<T> original) {
List<T> left = new ArrayList<>();
List<T> right = new ArrayList<>();
int center;
if (original.size() == 1) {
return original;
} else {
center = original.size() / 2;
for (int i = 0; i < center; i++) {
left.add(original.get(i));
}
for (int i = center; i < original.size(); i++) {
right.add(original.get(i));
}
left = mergeSort(left);
right = mergeSort(right);
merge(left,right,original);
}
return original;
}
private void merge(List<T>left, List<T>right, List<T>original) {
int leftIndex=0;
int rightIndex=0;
int originalIndex=0;
while(leftIndex<left.size()&& rightIndex<right.size()) {
if(left.get(leftIndex).compareTo(right.get(rightIndex))<0) {
original.set(originalIndex, left.get(leftIndex));
leftIndex++;
}else {
original.set(originalIndex, right.get(rightIndex));
rightIndex++;
}
originalIndex++;
}
while(leftIndex<left.size()) {
original.set(originalIndex, left.get(leftIndex));
originalIndex++;
leftIndex++;
}
while(rightIndex<right.size()) {
original.set(originalIndex, right.get(rightIndex));
originalIndex++;
rightIndex++;
}
}
public static void main(String args[]) {
List<Integer> numbers = new ArrayList<>();
numbers.add(4);
numbers.add(12);
numbers.add(9);
numbers.add(5);
numbers.add(6);
numbers.add(47);
numbers.add(84);
numbers.add(27);
numbers.add(38);
List<String> words = new ArrayList<>();
words.add("bat");
words.add("rat");
words.add("sat");
words.add("fat");
words.add("splat");
words.add("hat");
words.add("mat");
MergeSort test = new MergeSort();
System.out.println("Not Sorted List: ");
System.out.print(numbers);
test.mergeSort(numbers);
System.out.println();
System.out.println("Merge Sorted List: ");
System.out.print(numbers);
System.out.println();
System.out.println();
System.out.println();
System.out.println("Not Sorted List: ");
System.out.print(words);
test.mergeSort(words);
System.out.println();
System.out.println("Merge Sorted List: ");
System.out.print(words);
}
}
MergeSort.main(null);
import java.util.*;
class BinarySearch {
int search(int arr[], int l, int r, int x) {
// right side of the array must be smaller than the left since the array should be in order
if (r>=l && l<= arr.length -1) {
// finds the mid point of the array
int mid = l + (r-1)/2;
// checks if the mid point is the element being searched for
if (arr[mid] == x) {
return mid;
}
// checks if the mid point is larger than the element being search for and recursively calls the function again only ranging from the left to the midpoint
if (arr[mid] > x) {
return search(arr, l, mid - 1, x);
}
// since the wanted value is not less than or equal to the mid point, the algorithm searchs for above the midpoint and recursively calls the function again ranging from the right to above the midpoint
return search(arr, mid + 1, r, x);
}
// finally returns -1 if none of the other if statements work meaning that the value in not in the array
return -1;
}
// print function for the array
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[]) {
BinarySearch sort = new BinarySearch();
int arr[] = { 5, 6, 3, 1, 8, 9, 4, 7, 2 };
// length of the array and prints
int n = arr.length;
printArray(arr);
// element the function is looking for
int x = 45;
System.out.println("Searching for " + x);
// calling the method
int result = sort.search(arr, 0, n - 1, x);
// element is not present
if (result == -1)
// Print statement
System.out.println("Element not present");
// element is present
else
// Print statement
System.out.println("Element found at index "
+ result);
}
}
BinarySearch.main(null);
import java.util.*;
class BinarySearch {
void merge(int arr[], int l, int m, int r) {
// Find the sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int[] L = new int[n1];
int[] R = new int[n2];
/* Copy data to temp arrays */
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];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarray array
int k = l;
while (i < n1 && j < n2) {
if (L[i]<=R[j]) {
// MISSING CODE #1
arr[k] = L[i];
i++;
}
else {
// MISSING CODE #2
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void sort(int arr[], int l, int r) {
if (l < r) {
// COMMENT A
int m = l + (r - l) / 2;
// COMMENT B
sort(arr, l, m);
sort(arr, m + 1, r);
// COMMENT C
merge(arr, l, m, r);
}
}
int search(int arr[], int l, int r, int x) {
// right side of the array must be smaller than the left since the array should be in order
if (r>=l && l<= arr.length -1) {
// finds the mid point of the array
int mid = l + (r-1)/2;
// checks if the mid point is the element being searched for
if (arr[mid] == x) {
return mid;
}
// checks if the mid point is larger than the element being search for and recursively calls the function again only ranging from the left to the midpoint
if (arr[mid] > x) {
return search(arr, l, mid - 1, x);
}
// since the wanted value is not less than or equal to the mid point, the algorithm searchs for above the midpoint and recursively calls the function again ranging from the right to above the midpoint
return search(arr, mid + 1, r, x);
}
// finally returns -1 if none of the other if statements work meaning that the value in not in the array
return -1;
}
// print function for the array
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[]) {
BinarySearch sort = new BinarySearch();
int arr[] = { 5, 6, 3, 1, 8, 9, 4, 7, 2 };
// length of the array and prints
int n = arr.length;
System.out.println("Original Array:");
printArray(arr);
sort.sort(arr, 0, n - 1);
System.out.println("Sorted Array:");
printArray(arr);
System.out.println();
// element the function is looking for
int x = 7;
System.out.println("Searching for " + x);
// calling the method
int result = sort.search(arr, 0, n - 1, x);
// element is not present
if (result == -1)
// Print statement
System.out.println("Element not present");
// element is present
else
// Print statement
System.out.println("Element found at index "
+ result);
}
}
BinarySearch.main(null);