JAVA - Searching and Sorting

Please help modify/complete the methods below to get each sort to work. Do not change/add/remove any method header/parameter

a. in ArrayModule, quickSort and mergeSort algorithms needs to be done recursively

b. swap can be done recursively

c. everything else iteratively

d. all in recModule needs to be recursive

So far this is my code, I have completed some methods. testing with JUnit, my output is not sorted for some reason

ArrayModule.java:

package modules;

public class ArrayModule { public static int binarySearch(int[] list, int target) { int min = 0; int max = list.length - 1; int mid; while (min <= max) { mid = (min + max) / 2; if (list[mid] == target ) { return mid; } else if (list[mid] < target) { min = mid + 1; } else { max = mid - 1; } } return -1; }

public static void bubbleSort(int[] list) { int temp = 0; for (int i = 0; i < list.length; i++) { for(int j = 1; j < list.length - i; j++) { if (list[j] < list[j - 1]) { temp = list[j]; list[j]= list[j-1]; list[j - 1] = temp; } } } } public static boolean contains(int[] list, int target) { return false; } public static int indexOf(int[] list, int target) { for(int i = 0; i < list.length; i++) { //linear search if (list[i]== target) { return i; } } return -1; } public static void insertionSort(int[] list) { int current; int j; for(int i = 1; i < list.length; i++) { current = list[i]; for(j = 1; j > 0 && current < list[j-1]; j--) { list[j]= list[j-1]; } list[j] = current; } }

private static void merge(int[] list, int[] firstHalf, int[] secondHalf) { int index = 0; int leftIndex = 0; int rightIndex = 0; while(leftIndex < firstHalf.length && rightIndex < secondHalf.length) { if (firstHalf[leftIndex] < secondHalf[rightIndex] ) { list[index++] = firstHalf[leftIndex++]; } else { if (firstHalf[leftIndex] < secondHalf[rightIndex]) ; list[index++] = secondHalf[rightIndex++]; } while(leftIndex < firstHalf.length) { list[index++] = firstHalf[leftIndex++]; } while(rightIndex < secondHalf.length) { list[index++] = secondHalf[rightIndex++]; } } } public static void mergeSort(int[] list) { if (list.length>1) { int[] left = splitFirstHalf(list); int[] right = splitSecondHalf(list); mergeSort(left); mergeSort(right); merge(list, left, right); } } private static int partition(int[] list, int low, int high) { int l; int h; int midpoint; int pivot; int temp; boolean done;

/* Pick middle element as pivot */ midpoint = low + (low - high) / 2; pivot = list[midpoint];

done = false; l = low; h = high;

while (!done) { /* Increment l while numbers[l] < pivot */ while (list[l] < pivot) { ++l; }

/* Decrement h while pivot < numbers[h] */ while (pivot < list[h]) { --h; }

/* If there are zero or one items remaining, all numbers are partitioned. Return h */ if (l >= h) { done = true; } else { /* Swap numbers[l] and numbers[h], update l and h */ temp = list[l]; list[l] = list[h]; list[h] = temp;

++l; --h; } }

return h; }

public static void quickSort(int[] list) { quickSort(list, 0, list.length - 1); } private static void quickSort(int[] list, int left, int right) { int j;

/* Base case: If there are 1 or zero entries to sort, partition is already sorted */ if (left >= right) { return; }

/* Partition the data within the array. Value j returned from partitioning is location of last item in low partition. */ j = partition(list, left, right);

/* Recursively sort low partition (i to j) and high partition (j + 1 to k) */ quickSort(list, left, j); quickSort(list, j + 1, right); }

public static void selectionSort(int[] list) { int minIndex; for (int i = 0; i < list.length - 1; i++) { minIndex = i; for (int j = i +1; j < list.length; j++) { if (list[j]< list[minIndex] ) { minIndex = j; } } if (minIndex != i) { int min = list[minIndex]; list[minIndex] = list[i]; list[i] = min; } } } private static int[] splitFirstHalf(int[] list) { //sort first half return null; } private static int[] splitSecondHalf(int[] list) { //sort second half return null; } public static void swap(int[] list, int first, int second) { final int temp = list[first]; list[first] = list[second]; list[second] = temp; } }

--------------------------------------------

RecModule.java:

package modules;

public class RecModule {

public static int binarySearch(int[] list, int target) { return binarySearch(list, target, 0, list.length - 1); }

private static int binarySearch(int[] list, int target, int min, int max) { if (min > max) {return -1; } else { int mid = (min + max) / 2; if (list[mid] < target) { return binarySearch(list, target, mid + 1, max); } else if (list[mid] > target) { return binarySearch(list, target, min, mid - 1); } else { return mid; } } }

public static void selectionSort(int[] list) { selectionSort(list, 0); //sort entire data }

private static void selectionSort(int[] list, int start) {

}

public static void swap(int[] list, int first, int second) {

}

}