Implement a method to sort a given array using the basic Qui

Implement a method to sort a given array using the basic Quick sort algorithm. Use the algorithm from the textbook (sec below). Write a driver program to test the Quick sort algorithm for the file uploaded in the canvas.

Solution

// QuickSortImplementation.java
class QuickSortImplementation
{
  
   int partition(int A[], int p, int r)
   {
       int x = A[r];
       int i = (p-1);
       for (int j=p; j<=r-1; j++)
       {
           if (A[j] <= x)
           {
               i++;
               // exchange A[i] with A[j]
               int temp = A[i];
               A[i] = A[j];
               A[j] = temp;
           }
       }
       // exchange A[i+1] with A[r]
       int temp = A[i+1];
       A[i+1] = A[r];
       A[r] = temp;

       return i+1;
   }

   void QUICKSORT(int A[], int p, int r)
   {
       if (p < r)
       {
           int q = partition(A, p, r);
           QUICKSORT(A, p, q-1);
           QUICKSORT(A, q+1, r);
       }
   }

   public static void main(String args[])
   {
       int A[] = {34, 76, 11, 35, 89, 51};
       int length = A.length;

       System.out.print(\"UnSorted Array: \");
       for (int i=0; i<length; ++i)
           System.out.print(A[i]+\" \");
       System.out.println();

       QuickSortImplementation sorting = new QuickSortImplementation();
       sorting.QUICKSORT(A, 0, length-1);

       System.out.print(\"Sorted Array: \");
       for (int i=0; i<length; ++i)
           System.out.print(A[i]+\" \");
       System.out.println();
   }
}

/*
output:

UnSorted Array: 34 76 11 35 89 51
Sorted Array: 11 34 35 51 76 89

*/