D2L Bright space Instructor: Rongxing Lu The marking scheme is shown in the left

Question

D2L Bright space Instructor: Rongxing Lu The marking scheme is shown in the left margin and [100] constitutes full marks. [60] I. Given an integer array A {3, 6, 10, 18, 8,7,25,40), [20] (a) Write your own Java source code named Mergesort. ava to implement Merge Sort algorithm on the array A. Please finish your code in the following template, where "XXXSort" is replaced with "MergeSort". [20] (b) Write your own Java source code named HeapSort. j ava to implement Heap Sort algorithm on the array A. Please also finish your code in the following template, where "XXXSort" is replaced with "HeapSort". [20] (c) Write your own Java source code named Quicksort. ava to implement Quick Sort algorithm on the array A. Please also finish your code in the following template. where "XXXSort" is re- placed with "QuickSort". public class XXXSort

Explanation / Answer

1. MergeSort.java :

public class MergeSort {
  
   public static void main(String[] args) {
       int[] a = { 3, 6, 10, 18, 8, 7, 25, 40 }; // create test array
       sort(a);
       show(a);
      
          
   }
  
   public static void sort(int[] a){
       int len = a.length;
       MergeSort.recursiveMergeMeth(a, 0, len - 1); // call recursive method
      
      
   }
  
   public static void show(int[] a){
       int len = a.length;
       for (int i = 0; i < len; i++)
           System.out.println(a[i]); // output
      
   }
  
   static public void mergeHere(int[] numbers, int left, int mid, int right) {
       int[] temp = new int[25];
       int i, leftEnd, numElements, tmpPos;

       leftEnd = (mid - 1);
       tmpPos = left;
       numElements = (right - left + 1);

       while ((left <= leftEnd) && (mid <= right)) {
           if (numbers[left] <= numbers[mid])
               temp[tmpPos++] = numbers[left++];
           else
               temp[tmpPos++] = numbers[mid++];
       }

       while (left <= leftEnd)
           temp[tmpPos++] = numbers[left++];

       while (mid <= right)
           temp[tmpPos++] = numbers[mid++];

       for (i = 0; i < numElements; i++) {
           numbers[right] = temp[right];
           right--;
       }
   }

  
   // The Recursive Method for Merge Sort
   static public void recursiveMergeMeth(int[] numbers, int left, int right) {
       int mid;
       if (right > left) {
           mid = (right + left) / 2; // find mid
           recursiveMergeMeth(numbers, left, mid); //recursive call
           recursiveMergeMeth(numbers, (mid + 1), right); //recursive call
           // Merge call
           mergeHere(numbers, left, (mid + 1), right);
       }
   }

}

2. HeapSort.java :

public class HeapSort {

   public static void main(String[] args) {
      
       int[] a = { 3, 6, 10, 18, 8, 7, 25, 40 }; // create test array
       sort(a);
       show(a);
          
   }
  
   public static void sort(int[] a){
       for (int i = a.length; i > 1; i--) {
           heapSort(a, i - 1);
       }
      
   }
  
   public static void show(int[] a){
       for (int i = 0; i < a.length; i++)
           System.out.println(a[i]);
      
   }

   public static void heapSort(int array[], int arrayUpperbound) {
       int leftChild, rightChild, middleChild, root, temp;
       root = (arrayUpperbound - 1) / 2;

       for (int o = root; o >= 0; o--) {
           for (int i = root; i >= 0; i--) {
               leftChild = (2 * i) + 1;
               rightChild = (2 * i) + 2;
               if ((leftChild <= arrayUpperbound) && (rightChild <= arrayUpperbound)) {
                   if (array[rightChild] >= array[leftChild])
                       middleChild = rightChild;
                   else
                       middleChild = leftChild;
               } else {
                   if (rightChild > arrayUpperbound)
                       middleChild = leftChild;
                   else
                       middleChild = rightChild;
               }

               if (array[i] < array[middleChild]) {
                   temp = array[i];
                   array[i] = array[middleChild];
                   array[middleChild] = temp;
               }
           }
       }
       temp = array[0];
       array[0] = array[arrayUpperbound];
       array[arrayUpperbound] = temp;
       return;
   }
}

3. QuickSort.java :

public class QuickSort {
  
   public static void main(String[] args) {
       int[] a = { 3, 6, 10, 18, 8, 7, 25, 40 }; // create test array
       sort(a);
       show(a);      
   }
  
   public static void sort(int[] a){
       int len = a.length;
       QuickSort.quickSortMethod(a, 0, len - 1);
      
   }
  
   public static void show(int[] a){
       int len = a.length;
       for (int i = 0; i < len; i++)
           System.out.println(a[i]); // output
      
   }
  
   public static void swap(int A[], int x, int y) {
       int temp = A[x];
       A[x] = A[y];
       A[y] = temp;
   }

   public static int partition(int A[], int f, int l) {
       int pivot = A[f];
       while (f < l) {
           while (A[f] < pivot)
               f++;
           while (A[l] > pivot)
               l--;
           swap(A, f, l);
       }
       return f;
   }
  
   public static void quickSortMethod(int A[], int f, int l) {
       if (f >= l)
           return;
       int pivot_index = partition(A, f, l);
       quickSortMethod(A, f, pivot_index);
       quickSortMethod(A, pivot_index + 1, l);
   }

}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.