QuickSort in C++ using Recursion

Quicksort in C++ is divide and conquer method used to sort an array.

QuickSort Alogorithm

To understand how quicksort works? You must know what is Pivot element.

Basically, in quicksort,

  1. we choose a pivot element. Usally we assume pivot element = array[startIndex].
  2. Now we shift all the elements to the left of pivot element whiich is less than pivot element (i.e element < Pivot Element).
  3. Again shift all the elements to the right of pivot element which is greater than pivot element (i.e element > Pivot element)
  4. Here the final index of the pivot element is the divide point of the array. Hence, now we have two sub-arrays.
  5. Repeat the process (again from step 1) for the subarrays until sub array has one element.

Note: On starting we assumed pivot element = array[startIndex]. Here startIndex is the first index of the array or sub-array.

Code

Online Compiler

Here findPivot(…) function is sorting the array as stated in the algorithm. And quickSort(…) function is dividing the array into sub-arrays at index being returned by findPivot(…) function.

Output

Quick Sort Overview:

  • In-place Algorithm (No need of extra arrays).
  • O(nlogn)-base 2. Array is repeatedly partitioning the array into two halves.
  • Unstable algorithm (Interchanging duplicate values, which is useless).

Also check Shell Sort Program Code in C++.

admin

I am a B.tech IT Student from India. Technology and programming is the most enthusiastic thing for me in this world. I like learning new techniques and use them for real-world application because I feel tech is future. Let's learn and grow TOGETHER.