Sorting and Searching Given the following code, implement a recursive BinarySear
ID: 3601476 • Letter: S
Question
Sorting and Searching
Given the following code, implement a recursive BinarySearcher method as a helper
to find the “indexOf” a particular element. (It should return -1 if the element is
not found):
import java.util.List;
import java.lang.Comparable;
import java.util.ArrayList;
public class Sorter {
public static <T extends Comparable<T> > void bubbleSort(List<T> theList) {
int lastToConsider = theList.size();
while (lastToConsider > 1) {
for (int j=0; j<lastToConsider-1; j++) {
if (theList.get(j).compareTo(theList.get(j+1)) > 0 ) {
swap(theList,j,j+1);
}
}
lastToConsider--;
}
} // End method bubbleSort
private static <T extends Comparable<T> > void swap(List<T> theList, int i1, int i2) {
T temp = theList.get(i1);
theList.set(i1,theList.get(i2));
theList.set(i2,temp);
} // End method swap
public static <T extends Comparable<T> > void selectionSort(List<T> theList) {
// Loop over theList.size() - 1
for (int index = 0; index < theList.size() - 1; index++) {
int min = index; // First index
// Loop to find minimum
for (int scan = index + 1; scan < theList.size(); scan++)
if (theList.get(scan).compareTo(theList.get(min)) < 0)
min = scan;
swap(theList, min, index); // Swap the values
}
} // End method selectionSort
public static <T extends Comparable<T> > void mergeSort(List<T> theList) {
recursiveMergeSortHelper(theList,0,theList.size());
} // End method mergeSort
private static <T extends Comparable<T> > void recursiveMergeSortHelper(List<T> theList, int first, int last) {
// Test base case
int size = last - first;
if (size <= 1)
return;
int mid = first + size/2;
recursiveMergeSortHelper(theList, first, mid);
recursiveMergeSortHelper(theList, mid, last);
List<T> temp = new ArrayList<>();
int i = first, j = mid;
for (int k = 0; k < size; k++) {
if (i == mid)
temp.add(theList.get(j++));
else if (j == last)
temp.add(theList.get(i++));
else if (theList.get(j).compareTo(theList.get(i)) < 0)
temp.add(theList.get(j++));
else
temp.add(theList.get(i++));
}
for (int k = 0; k < size; k++)
theList.set(first + k, temp.get(k));
} // End method recursiveMergeSortHelper
public static <T extends Comparable<T> > int indexOf(T searchItem, List<T> theList) {
return recursiveBinarySearcher(searchItem, theList, 0, theList.size());
} // End method indexOf
private static <T extends Comparable<T> > int recursiveBinarySearcher(T searchItem, List<T> theList, int first, int last) {
// stubbed
} // End method recursiveBinarySearcher
} // End class Sorter
Explanation / Answer
Please find my implementation.
import java.util.List;
import java.lang.Comparable;
import java.util.ArrayList;
public class Sorter {
public static <T extends Comparable<T> > void bubbleSort(List<T> theList) {
int lastToConsider = theList.size();
while (lastToConsider > 1) {
for (int j=0; j<lastToConsider-1; j++) {
if (theList.get(j).compareTo(theList.get(j+1)) > 0 ) {
swap(theList,j,j+1);
}
}
lastToConsider--;
}
} // End method bubbleSort
private static <T extends Comparable<T> > void swap(List<T> theList, int i1, int i2) {
T temp = theList.get(i1);
theList.set(i1,theList.get(i2));
theList.set(i2,temp);
} // End method swap
public static <T extends Comparable<T> > void selectionSort(List<T> theList) {
// Loop over theList.size() - 1
for (int index = 0; index < theList.size() - 1; index++) {
int min = index; // First index
// Loop to find minimum
for (int scan = index + 1; scan < theList.size(); scan++)
if (theList.get(scan).compareTo(theList.get(min)) < 0)
min = scan;
swap(theList, min, index); // Swap the values
}
} // End method selectionSort
public static <T extends Comparable<T> > void mergeSort(List<T> theList) {
recursiveMergeSortHelper(theList,0,theList.size());
} // End method mergeSort
private static <T extends Comparable<T> > void recursiveMergeSortHelper(List<T> theList, int first, int last) {
// Test base case
int size = last - first;
if (size <= 1)
return;
int mid = first + size/2;
recursiveMergeSortHelper(theList, first, mid);
recursiveMergeSortHelper(theList, mid, last);
List<T> temp = new ArrayList<>();
int i = first, j = mid;
for (int k = 0; k < size; k++) {
if (i == mid)
temp.add(theList.get(j++));
else if (j == last)
temp.add(theList.get(i++));
else if (theList.get(j).compareTo(theList.get(i)) < 0)
temp.add(theList.get(j++));
else
temp.add(theList.get(i++));
}
for (int k = 0; k < size; k++)
theList.set(first + k, temp.get(k));
} // End method recursiveMergeSortHelper
public static <T extends Comparable<T> > int indexOf(T searchItem, List<T> theList) {
return recursiveBinarySearcher(searchItem, theList, 0, theList.size());
} // End method indexOf
private static <T extends Comparable<T> > int recursiveBinarySearcher(T searchItem, List<T> theList,
int first, int last) {
// stubbed
if(first >= last)
return -1;
int middle = first + (last - first)/2;
if(theList.get(middle).compareTo(searchItem) == 0)
return middle;
if(theList.get(middle).compareTo(searchItem) < 0)
return recursiveBinarySearcher(searchItem, theList, middle+1, theList.size());
else
return recursiveBinarySearcher(searchItem, theList, 0, middle);
} // End method recursiveBinarySearcher
} // End class Sorter
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.