Quick Sort Algorithm (with Example) with C++ Code | Sorting Algorithms | Data Structures & Algorithms

> Quick Sort Algorithm is a Divide & Conquer algorithm. It divides input array in two partitions, calls itself for the two partitions(recursively) and performs in-place sorting while doing so. A separate partition() function is used for performing this in-place sorting at every iteration. Quick sort is one of the most efficient sorting algorithms.
  • >> Time Complexity: θ(nlog(n))
  • >> Space Complexity: O(log(n))
Working –
There are 2 Phases (3 major steps) in the Quick Sort Algorithm –
  1. Division Phase – Divide the array(list) into 2 halves by finding the pivot point to perform the partition of the array(list).
    1. The in-place sorting happens in thispartition process itself.
  2. Recursion Phase –
    1. Call Quick Sort on the left partition (sub-list)
    2. Call Quick Sort on the right partition (sub-list)
Quick Sort Algorithm(Pseudo Code) –
quick sort algorithm
Quick Sort Partition Function(Pseudo Code) –
partition function in quick sort algorithm
C++ Program to Implement Quick Sort –
YouTube video tutorials –

Leave a Reply

Your email address will not be published. Required fields are marked *