# 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 –

- Division Phase – Divide the array(list) into 2 halves by finding the pivot point to perform the partition of the array(list).
- The in-place sorting happens in this partition process itself.

- Recursion Phase –
- Call Quick Sort on the left partition (sub-list)
- Call Quick Sort on the right partition (sub-list)

**Quick Sort Algorithm(Pseudo Code) –**

**Quick Sort Partition Function(Pseudo Code) –**

**C++ Program to Implement Quick Sort –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | # include <iostream> using namespace std; // quick sort sorting algorithm int Partition(int arr[], int s, int e) { int pivot = arr[e]; int pIndex = s; for(int i = s;i<e;i++) { if(arr[i]<pivot) { int temp = arr[i]; arr[i] = arr[pIndex]; arr[pIndex] = temp; pIndex++; } } int temp = arr[e]; arr[e] = arr[pIndex]; arr[pIndex] = temp; return pIndex; } void QuickSort(int arr[], int s, int e) { if(s<e) { int p = Partition(arr,s, e); QuickSort(arr, s, (p-1)); // recursive QS call for left partition QuickSort(arr, (p+1), e); // recursive QS call for right partition } } int main() { int size=0; cout<<"Enter Size of array: "<<endl; cin>>size; int myarray[size]; cout<<"Enter "<<size<<" integers in any order: "<<endl; for(int i=0;i<size;i++) { cin>>myarray[i]; } cout<<"Before Sorting"<<endl; for(int i=0;i<size;i++) { cout<<myarray[i]<<" "; } cout<<endl; QuickSort(myarray,0,(size-1)); // quick sort called cout<<"After Sorting"<<endl; for(int i=0;i<size;i++) { cout<<myarray[i]<<" "; } return 0; } |