I need help modifying the method quicksort. Modify quicksort so that each time y

Question

 I need help modifying the method quicksort. Modify quicksort so that each time you call quicksort recursively, if the subarray size is smaller than the threshold, sort it with insertion sort (you have been given an insertionsort method). Test 4 different thresholds: 8, 32, 64, 512. This does not mean that all these thresholds need to be accessed all at once, but instead that the threshold can be manually changed to each of these individually. The purpose of this is for me to be able to check their individual runtimes to see which works best.   // Sorts the elements in the range a[low..high].    private static void insertionsort(int[] a, int low, int high) {       for (int i = low+1; i <= high; ++i) {          int temp = a[i], j = i-1;          // Save the current element          while (j >= low && a[j] > temp) {  // Shift all elements greater than it to the right             a[j+1] = a[j];             --j;          }          a[j+1] = temp;                     // Insert the current element into the correct spot       }    }     public static void quicksort(int[] a) {       quicksort(a, 0, a.length-1);    }     // ***Modify this method to use insertion sort for small subarrays***    // Sorts the elements in the range a[low..high].    private static void quicksort(int[] a, int low, int high) {       if (low >= high)          return;       int pivot = partition(a, low, high); // Partition the array into two halves       quicksort(a, low, pivot-1);          // Sort the left half       quicksort(a, pivot+1, high);         // Sort the right half    }

Explanation / Answer

Actually its a research problem to find out at which threshold value of number of elements the insertion sort performs better than quicksort.
So if you want to know the accurate value of threshold,you need to perform the experiment for different threhold values.As there are many variations of quicksort it may vary.

I am assuming the threshold value to be 12 for answering your question.

You just need a slight modification in the quicksort function. An extra condition statement will do the job.

private static void quicksort(int[] a, int low, int high) {
      if (low >= high)
         return;

      //length of the subarray to be sorted in this call L = (high-low+1)
      int L = high-low+1;

      //if the L value is less than threshold value we call insertion sort else we call the quicksort recursively
      if(L < 12)
             insertionsort(a , low , high);
      else
      {
      int pivot = partition(a, low, high); // Partition the array into two halves
          quicksort(a, low, pivot-1);          // Sort the left half
          quicksort(a, pivot+1, high);         // Sort the right half
      }    
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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