Question

HW60.1. Array Quicksort You've done partition so now it's time to finish Quicksort. Create a public non-final class named Quicksort that extends Partitioner. Implement a public static method void quicksort (int] values) that sorts the input array of ints in ascending order. You will want this method to be recursive, with the base case being an array with zero or one value. You should sort the array in place, which is why your function is declared to return void. If the passed array is null you should just return. Your solution should also not make copies of the array as it runs. To help you your parent class Partitioner provides a useful class method: 1. int partition(int[] values, int start, int end): this partitions values starting at start (inclusive) and ending at end (exclusive). It returns the position of the pivot value. Note that the test code will test that you call partition an appropriate number of times, so you should not call it on empty or single-item arrays. Also keep in mind that each partition does place the pivot value in the correct location. So if you start with ( 2, 3, e, 1 ) and it is partitioned to f e, 1, 3, 2 only 3, 2 still needs to be partitioned, since 1 is the pivot and in the right place and e is a single-element array. Quicksort.java

Answer 1

class QuickSort
{

   int partition(int arr[], int low, int high)
   {
       int pivot = arr[high];
       int i = (low-1);
       for (int j=low; j<high; j++)
       {
      
           if (arr[j] <= pivot)
           {
               i++;
               int temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
           }
       }
       int temp = arr[i+1];
       arr[i+1] = arr[high];
       arr[high] = temp;

       return i+1;
   }

   void sort(int arr[], int low, int high)
   {
       if (low < high)
       {

           int pi = partition(arr, low, high);
           sort(arr, low, pi-1);
           sort(arr, pi+1, high);
       }
   }

   static void printArray(int arr[])
   {
       int n = arr.length;
       for (int i=0; i<n; ++i)
           System.out.print(arr[i]+" ");
       System.out.println();
   }

   public static void main(String args[])
   {
       int arr[] = {10, 7, 8, 9, 1, 5,4,11};
       int n = arr.length;

       QuickSort ob = new QuickSort();
       ob.sort(arr, 0, n-1);

       System.out.println("sorted array");
       printArray(arr);
   }
}