C++ Program To Quick Sort Using Dynamic Array

In this tutorial, we will be learning about quicksort that takes O(nlogn) time complexity in its best case, and in its worst case, it takes O(n^2) time. The basic idea of the quicksort is to choose the pivot element and on the left side of the pivot, all the elements less than that will be placed whereas on the right-hand side all the elements greater than the pivot will be placed. Similarly, we can apply this algorithm on the left and right sides respectively using recursion.

Now the question arises that how to choose the pivot element in the given array, so you can choose any element as a pivot, here, we will be choosing the first element i.e. at the index zero as the pivot element while writing the algorithm.

Let us consider some inputs to understand what should be the required output:

Input:

array: {2 3 9 7 1}

Output:

array: {1 2 3 7 9}

Input:

array: {56 9 11 7 60}

Output:

array: {7 9 11 56 60}

Quicksort Algorithm

1. Create a function partition()
2. Pass three parameters arr, low, high
3. Select rightmost element as pivot
4. declare pointer for greater element
5. traverse through all elements and compare them with pivot
6. If the smaller element is found swap them with pivot
7. Return the index position
8. Create a function QuickSort()
9. Pass three parameters arr, low, high
10. Find the pivot element
11. Do Recursive call on the left pivot and right pivot
12. The array is now sorted
13. Print the sorted array

C++ Program For The Quick Sort

#include<iostream>
using namespace std;

int partition(int array[],int lb,int ub){
    int pivot=array[lb];
    int start=lb;
    int end=ub;
    while(start<end){
        while(array[start]<=pivot){
            start++;
        }
        while(array[end]>pivot){
            end--;
        }
        if(start<end){
            int temp=array[start];
            array[start]=array[end];
            array[end]=temp;
        }
    }
    int temp=array[end];
    array[end]=array[lb];
    array[lb]=temp;
    return end;
}

int quick_sort(int array[],int lb,int ub){
    while(lb<ub){
        int loc=partition(array,lb,ub);
        quick_sort(array,loc+1,ub);
        quick_sort(array,lb,loc-1);
    }
    return 0;
}

int main(){
    int arr[]={9,6,11,10,2,5};
    int n=sizeof(arr)/sizeof(arr[0]);
    quick_sort(arr,0,n-1);
    cout<<"Elements of the array after sorting are:-"<<endl;
    for(int i=0;i<n;i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}

Elements of the array after sorting are:-
2 5 6 9 10 11

Conclusion

We have seen the implementation and the basic principle behind the working of quicksort. Also, we have learned the working algorithm by taking an example.