JAVA 3 - FASTER SORTING a. Implement the recursive algorithm for merge sort. b.

Question

JAVA 3 - FASTER SORTING

a. Implement the recursive algorithm for merge sort. b. Complete the implementation of quick sort by implementing the method partition .

Implement the recursive algorithm for the merge sort. Complete the implementation of quick sort by implementing the method partition.

Requirements: You will submit the following with this lab:

b. Create a folder using your last name as the name of the folder

c. Develop the stack class and test class in that folder

d. When completed, ‘zip’ the contents, and

e. Submit the lab through the Canvas (online sections) or Dropbox (F2F sections) methanisms.

(Need answers ASAP please)*

Explanation / Answer

1. MergeSort.java

// Class for Recursive Merge Sort
public class MergeSort {

   // Merge method
   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. QuickSort.java

public class QuickSort {

   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);
   }

}

3. Test.java

//Test Class
public class Test {
  
   public static void main(String[] args) {
       int[] testArray = { 3, 8, 7, 5, 2, 1, 9, 6, 4 }; // create test array
       int len = 9; // size of test array
       MergeSort.recursiveMergeMeth(testArray, 0, len - 1); // call recursive method
       for (int i = 0; i < len; i++)
           System.out.println(testArray[i]); // output
      
      
       System.out.println("***********************"); // output
      
       int[] testArrayTwo = { 10, 8, 7, 5, 2, 1, 9, 6, 4, 3 }; // create test array
       int lenTwo = 10; // size of test array
       QuickSort.quickSortMethod(testArrayTwo, 0, lenTwo - 1);
       for (int i = 0; i < lenTwo; i++)
           System.out.println(testArrayTwo[i]); // output

   }

}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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