Question: ackage csc205; import java.awt.List; public class Sorting { // Helper methods // These operations will occur multiple times in our sorting methods, // so we
ackage csc205;
import java.awt.List;
public class Sorting {
// Helper methods
// These operations will occur multiple times in our sorting methods,
// so we add methods for them here
private static
return (a.compareTo(b)
}
private static
return (a.compareTo(b)
}
private static
return (a.compareTo(b) > 0);
}
private static void swap(Object[] a, int ii, int jj) {
Object swap = a[ii];
a[ii] = a[jj];
a[jj] = swap;
}
public static
boolean isSorted(T[]data){
return isSorted(data, 0, data.length-1);
}
public static
boolean isSorted(T[]data, int min, int max){
for (int ii=min+1; ii
if (less_than(data[ii], data[ii-1]))
return false;
}
return true;
}
// Selection Sort
public static
void selectionSort (T[] data) {
selectionSort (data, 0, data.length-1);
}
public static
void selectionSort (T[] data, int min, int max) {
int indexOfSmallest; // Smallest element found this pass
min = Math.max(min, 0);
max = Math.min(max, data.length-1);
// ii is the starting point for each pass
for(int ii=min; ii
indexOfSmallest = ii;
for (int scan=ii+1; scan
if (less_than(data[scan], data[indexOfSmallest])) {
indexOfSmallest = scan;
}
}
swap(data, indexOfSmallest, ii);
}
}
public static
void insertionSort(T[] data) {
insertionSort(data, 0, data.length-1);
}
public static
void insertionSort(T[] data, int min, int max)
{
int start = Math.max(min, 1);
int end = Math.min(max, data.length-1);
for (int index = start; index
{
int position = index;
// shift larger values to the right
while (position > 0 && greater_than(data[position-1],data[position]))
{
swap(data, position, position-1);
position--;
}
}
}
public static
void bubbleSort(T[] data) {
bubbleSort(data, 0, data.length-1);
}
public static
void bubbleSort(T[] data, int min, int max) {
int position, scan;
min = Math.max(min, 0);
max = Math.min(max, data.length-1);
// position is the "stopping point" for each pass
for (position = max; position >= min; position--)
{
for (scan = 0; scan
{
if (greater_than(data[scan],data[scan+1]))
swap(data, scan, scan + 1);
}
}
}
public static
void mergeSort(T[] data) {
mergeSort(data, 0, data.length-1);
}
private static
void mergeSort(T[] data, int min, int max) {
if (min
{
int mid = min + ((max - min) / 2);
mergeSort(data, min, mid);
mergeSort(data, mid+1, max);
merge(data, min, mid, max);
}
}
private static
void merge(T[] data, int first, int mid, int last) {
T[] temp = (T[])(new Comparable[data.length]); // temp array
// The two subarrays have already been sorted
int first1 = first, last1 = mid; // endpoints of first subarray
int first2 = mid+1, last2 = last; // endpoints of second subarray
int index = first1; // next index open in temp array
// Copy smaller item from each subarray into temp until one
// of the subarrays is exhausted
// while both sub arrays have items left
while (first1
{
if (less_than(data[first1],data[first2]))
{
temp[index] = data[first1];
first1++;
}
else
{
temp[index] = data[first2];
first2++;
}
index++;
}
// Only one of the while loops below will execute
// Copy remaining elements from first subarray, if any
while (first1
{
temp[index] = data[first1];
first1++;
index++;
}
// Copy remaining elements from second subarray, if any
while (first2
{
temp[index] = data[first2];
first2++;
index++;
}
// Copy merged data into original array
for (index = first; index
data[index] = temp[index];
}
public static
void quickSort(T[] data) {
quickSort(data, 0, data.length-1);
}
private static
void quickSort(T[] data, int min, int max) {
if (min
{
// create partitions
int indexofpartition = partition(data, min, max);
// sort the left partition (lower values)
quickSort(data, min, indexofpartition - 1);
// sort the right partition (higher values)
quickSort(data, indexofpartition + 1, max);
}
}
private static
int partition(T[] data, int min, int max) {
T partitionelement;
int left, right;
int middle = min + ((max - min) / 2);
// use the middle data value as the partition element
partitionelement = data[middle];
// move it out of the way for now
swap(data, middle, min);
left = min;
right = max;
while (left
{
// search for an element that is > the partition element
while (left
left++;
// search for an element that is
while (greater_than(data[right], partitionelement))
right--;
// swap the elements
if (left
swap(data, left, right);
}
// move the partition element into place
swap(data, min, right);
return right;
}
// Project 7
public static
void sort(T[] data)
{
insertionSort (data, 0, data.length - 1);
}
public static
void cutoff_qsort(T[] data) {
cutoff_qsort(data,0,data.length - 1, 10);
{
}
}
public
void cutoff_qsort(T[] data, int cutoff) {
cutoff_qsort(data,0,data.length - 1, cutoff);
}
private static
void cutoff_qsort(T[] data, int min, int max, int cutoff) {
if (max
quickSort(data);
}
else insertionSort(data);
}
public static
void median(T[] data) {
}
public static
List first_n(T[] data, int n) {
return null;
}
}
median (array) that efficiently finds the median element in an array. You should not assume the array is sorted and your method should be quicker than simply sorting the array and returning the nth element. (Note: there are multiple ways to implement this. The most efficient way is to modify one of the sort methods we discussed.) first_n(array, n) that returns an ArrayList of the n smallest elements of the array. You should not assume the array is sorted and your method should be efficient
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help