Quicksort is the divide and conquer method used to sort an array.

QuickSort Algorithm

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

Basically, in quicksort,

  1. we choose a pivot element. Usually we assume pivot element = array[startIndex].
  2. Now we shift all the elements to the left of pivot element which 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 dividing 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.

QuickSort Code

C

C++

Java


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. The array is repeatedly partitioning the array into two halves.
  • Unstable algorithm (Interchanging duplicate values, which is useless).

It is advisable to use quick sort to get better efficiency in sorting array. If you have any doubts then comment below.

If you are having any difficulties then do comment below.

Leave a Reply

Close Menu