Advertisement
Guest User

merge

a guest
Jan 23rd, 2018
272
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.49 KB | None | 0 0
  1. package sort;
  2.  
  3. //Programmer: John Chapin email: john.chapin@lcps.org
  4. //Programmer: Chris Schroeder email: chris@4schroeders.com - Modified to use the ISortPanel
  5.  
  6. public class MergeSort implements Runnable {
  7. int[] sortArray;
  8. ISortPanel panel;
  9.  
  10. public MergeSort(int[] anArray, ISortPanel aPanel) {
  11. sortArray = anArray;
  12. panel = aPanel;
  13. }
  14. public void pa (int[] arr) {
  15. System.out.print("helper: ");
  16. for (int i: arr)
  17. System.out.print(i + " ");
  18. System.out.println();
  19. System.out.print("real: ");
  20. for (int i: sortArray)
  21. System.out.print(i + " ");
  22. System.out.println();
  23. }
  24. public void merge(int begIndex, int middleIndex, int endIndex) {
  25. int helperSize = endIndex - begIndex + 1;
  26. int leftIndex = begIndex;
  27. int rightIndex = middleIndex + 1;
  28. int[] helperArr = new int[helperSize];
  29. // ***** WRITE CODE HERE **************
  30. // Fill helper array with values from the two halves
  31. // of the sorted array
  32. //
  33. int count = 0;
  34. while (leftIndex <= middleIndex && rightIndex <= endIndex) {
  35. if (sortArray[leftIndex] <= sortArray[rightIndex]) {
  36. helperArr[count] = sortArray[leftIndex];
  37. leftIndex++;
  38. count++;
  39. }
  40.  
  41. if (sortArray[rightIndex] <= sortArray[leftIndex]) {
  42. helperArr[count] = sortArray[rightIndex];
  43. rightIndex++;
  44. count++;
  45. }
  46.  
  47. }
  48. for (int i = leftIndex; i <= middleIndex; i++) {
  49. helperArr[count] = sortArray[i];
  50. count++;
  51. }
  52.  
  53. for (int i = rightIndex; i <= endIndex; i++) {
  54. helperArr[count] = sortArray[i];
  55. count++;
  56. }
  57.  
  58. /* ******* This is written for you already
  59. * - Set values in sortArray to the values that were merged merged into the
  60. * helperArray - Display after each move from one element of the helper array to
  61. * the sortArray using panel.updateArray
  62. */
  63. int helperArrayIndex = 0;
  64. for (int index = begIndex; index <= endIndex; index++) {
  65. sortArray[index] = helperArr[helperArrayIndex];
  66. helperArrayIndex++;
  67. panel.updateArray(sortArray);//Display the array
  68. }
  69. }
  70.  
  71. public void mergeSort(int low, int high) {
  72.  
  73. if (low < high) {
  74. int middle = low + (high - low) / 2;
  75. //System.out.println(low + " " + middle + " " + high);
  76. mergeSort(low, middle);
  77. mergeSort(middle + 1, high);
  78. merge(low, middle, high);
  79. }
  80.  
  81. }
  82.  
  83. // This is the sort routine on sortArray
  84. public void run() {
  85.  
  86. mergeSort(0, sortArray.length - 1);
  87.  
  88. }//
  89.  
  90. }// MergeSort class
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement