Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package sort;
- //Programmer: John Chapin email: john.chapin@lcps.org
- //Programmer: Chris Schroeder email: chris@4schroeders.com - Modified to use the ISortPanel
- public class MergeSort implements Runnable {
- int[] sortArray;
- ISortPanel panel;
- public MergeSort(int[] anArray, ISortPanel aPanel) {
- sortArray = anArray;
- panel = aPanel;
- }
- public void pa (int[] arr) {
- System.out.print("helper: ");
- for (int i: arr)
- System.out.print(i + " ");
- System.out.println();
- System.out.print("real: ");
- for (int i: sortArray)
- System.out.print(i + " ");
- System.out.println();
- }
- public void merge(int begIndex, int middleIndex, int endIndex) {
- int helperSize = endIndex - begIndex + 1;
- int leftIndex = begIndex;
- int rightIndex = middleIndex + 1;
- int[] helperArr = new int[helperSize];
- // ***** WRITE CODE HERE **************
- // Fill helper array with values from the two halves
- // of the sorted array
- //
- int count = 0;
- while (leftIndex <= middleIndex && rightIndex <= endIndex) {
- if (sortArray[leftIndex] <= sortArray[rightIndex]) {
- helperArr[count] = sortArray[leftIndex];
- leftIndex++;
- count++;
- }
- if (sortArray[rightIndex] <= sortArray[leftIndex]) {
- helperArr[count] = sortArray[rightIndex];
- rightIndex++;
- count++;
- }
- }
- for (int i = leftIndex; i <= middleIndex; i++) {
- helperArr[count] = sortArray[i];
- count++;
- }
- for (int i = rightIndex; i <= endIndex; i++) {
- helperArr[count] = sortArray[i];
- count++;
- }
- /* ******* This is written for you already
- * - Set values in sortArray to the values that were merged merged into the
- * helperArray - Display after each move from one element of the helper array to
- * the sortArray using panel.updateArray
- */
- int helperArrayIndex = 0;
- for (int index = begIndex; index <= endIndex; index++) {
- sortArray[index] = helperArr[helperArrayIndex];
- helperArrayIndex++;
- panel.updateArray(sortArray);//Display the array
- }
- }
- public void mergeSort(int low, int high) {
- if (low < high) {
- int middle = low + (high - low) / 2;
- //System.out.println(low + " " + middle + " " + high);
- mergeSort(low, middle);
- mergeSort(middle + 1, high);
- merge(low, middle, high);
- }
- }
- // This is the sort routine on sortArray
- public void run() {
- mergeSort(0, sortArray.length - 1);
- }//
- }// MergeSort class
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement