Quick Sort Using Divide and Conquer

Algorithm and Code of Quick Sort Using Divide and Conquer.

This pseudocode Algorithm represents the Quick Sort algorithm’s classic example of the divide and conquer strategy.

Divide and Conquer Breakdown

1. Divide:
   • The array is divided into two smaller sub-arrays based on a pivot element (in this case, the last element of the array).
   • The Partition function rearranges the elements so that those less than or equal to the pivot come before it, and those greater come after it.
2. Conquer:
   • The algorithm recursively sorts the two sub-arrays (the left and right sides of the pivot).
   • This is done by calling Quick_Sort on each sub-array.
3. Combine:
   • In Quick Sort, the combine step is implicitly handled because once the sub-arrays are sorted, the entire array will be sorted as well. There’s no need for a separate combine step, as the partitioning ensures the order.

Partition(A,p,r)
{
    x=A[r]
    i=p-1
    for(j=p to r-1)
       {
        if(A[j]<=x){
        exchange A[i] with A[j]
     }
    }exchange A[i+1] with A[r]
      return i+1
   }
 Quick_Sort(A,p,r)
  {
       if(p<r)
        {
             int q= partition(A,p,r)
             Quick_Sort(A,p,q-1)
             Quick_Sort(A,q+1,r)
        }
}

Full Code in C

The code consists of a class called quicksort, which contains the main method, a partitioning method, and the recursive quick sort method.

class quicksort{
    public static void main(String[] args) {
        int arr[]={3,2,1,5,8,1};
        quick_sort(arr,0,arr.length-1);
        for(int i:arr){
            System.out.print(i+" ");
        }
    }//r is the pivot
    static int partition(int arr[],int low,int r){
        int x=arr[r];
        int i=low-1;
        for(int j=low;j<r-1;j++){
            if(arr[j]<=x)
            {
                i++;
                int temp=arr[j];
                arr[j]=arr[i];
                arr[i]=temp;
            }
        }
        int temp=arr[r];
        arr[r]=arr[i+1];
        arr[i+1]=temp;
        return i+1;
    }
    static int[] quick_sort(int arr[],int low,int pivot)
    {
        if(low<pivot){
            int q=partition(arr, low, pivot);
            quick_sort(arr, low, q-1);
            quick_sort(arr,q+1,pivot);
        }
        return arr;
    }
}

Step wise Explanation of Quick Sort Using Divide and Conquer

Class declaration then inside the main method:

class quicksort {
public static void main(String[] args) {
    int arr[] = {3, 2, 1, 5, 8, 1};
    quick_sort(arr, 0, arr.length - 1);
    for (int i : arr) {
        System.out.print(i + " ");
    }
}

This is the entry point of the program.

An array arr is initialized with unsorted integers.

The quick_sort method is called, passing the array and the initial indices (0 for the start and arr.length - 1 for the end).

After sorting, it prints the sorted array.

Partition Method

static int partition(int arr[], int low, int r) {
    int x = arr[r];               // Select the pivot (last element)
    int i = low - 1;             // Initialize the index for the smaller element
    for (int j = low; j < r; j++) {
        if (arr[j] <= x) {       // Compare current element with pivot
            i++;                  // Move the index for the smaller element
            int temp = arr[j];   // Swap elements
            arr[j] = arr[i];
            arr[i] = temp;
        }
    }
    // Place the pivot in the correct position
    int temp = arr[r];
    arr[r] = arr[i + 1];
    arr[i + 1] = temp;
    return i + 1;               // Return the pivot index
}

The partition method rearranges elements based on the pivot.

The last element of the sub-array (arr[r]) is chosen as the pivot.

It iterates through the elements from low to r - 1, swapping elements smaller than or equal to the pivot to the front.

After the loop, it swaps the pivot into its correct position and returns its index.

Quick Sort Method:

static int[] quick_sort(int arr[], int low, int pivot) {
    if (low < pivot) {           // Check if there are at least two elements
        int q = partition(arr, low, pivot); // Partition the array
        quick_sort(arr, low, q - 1); // Recursively sort the left sub-array
        quick_sort(arr, q + 1, pivot); // Recursively sort the right sub-array
    }
    return arr;                 // Return the sorted array
}

The quick_sort method implements the recursive sorting.

It checks if there are two or more elements to sort (low < pivot).

It calls the partition method to rearrange elements and get the new pivot index q.

It then recursively sorts the sub-arrays to the left (low to q - 1) and to the right (q + 1 to pivot).

Execution Flow

The program starts by executing the main method.

The quick_sort method is called with the initial array and its bounds.

The first call to quick_sort leads to a call to partition, which organizes the array around a pivot.

The pivot index is used to recursively call quick_sort on the resulting sub-arrays.

This process continues until the base case is reached (where a sub-array has one or no elements), at which point the recursion unwinds.

Finally, the sorted array is printed to the console.

Output

1 1 2 3 5 8

Summary

This code implements the Quick Sort algorithm using a divide-and-conquer approach, efficiently sorting the given array. Each step is essential for properly organizing and recursively sorting the elements. If you have any further questions or need clarification on specific parts, feel free to ask!

Learn Binary Search Using Divide and Conquer along with pseudo code in C.

Learn Merge Sort Using Divide and Conquer with Pseudo code in C.