Question

How to write a quick sort using just one recursive call in Java?

Answer 1

Please go through screenshots for better understanding.Any doubts comment below.Thank you.

JAVA CODE:

public class QuickSort
{
   int partition(int arr[], int low, int high)
   {
       int pivot = arr[high]; //taking last element as pivot
       int i = (low-1); // index of smaller element
      
       for (int j=low; j<high; j++)
       {
           // If current element is smaller than the pivot
           if (arr[j] < pivot)
           {
               i++;
               // swap arr[i] and arr[j]
               int temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
           }
       }

       // swap arr[i+1] and arr[high] (or pivot)
       int temp = arr[i+1];
       arr[i+1] = arr[high];
       arr[high] = temp;

       return i+1;
   }

   void sort(int arr[], int low, int high) //Method for sorting array
   {
       if (low < high) // low for starting index and high for ending index
       {
           int pi = partition(arr, low, high);
           // Recursively sort elements before
           // partition and after partition
           sort(arr, low, pi-1);
           sort(arr, pi+1, high);
       }
   }

   static void printArray(int arr[]) //Method for printing array elements
   {
       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[] = {22,1,13,6,3,11,44}; //Array for sorting
       int n = arr.length; // finding length of the array

       QuickSort ob = new QuickSort(); //Creating object ob for class QuickSort
       ob.sort(arr, 0, n-1); //Passing array to method sort

       System.out.println("sorted array");
       printArray(arr); // Passing array to printArray method
   }
}