**Quicksort **is a sorting algorithm based on the **divide and conquer**** paradigm**. In this algorithm the array is divided into two sub-lists, one sub-list will contain the smaller elements and another sub-list will contain the larger elements and then these sub-lists are sorted again using recursion.

**For that these techniques are followed:**

**1. **One element is picked from the list known as the pivot element.

**2. **The list is then reordered such that the smaller elements of the pivot go to its left sub-list and the greater elements of the pivot element go to its right sublist(the equal element can go either side) and after this reordering, the pivot element will be at its final sorted position.

**3. **The above two steps are recursively applied to the sublists in a similar way and thus the array gets sorted.

**There are various ways to select a pivot element-**

**1. **The first element can be chosen as the pivot element

**2. **The last element can be chosen as the pivot element

**3. **Any random element can be chosen as the pivot element

**4. **The median element can be chosen as the pivot element

Quicksort recursion algorithm is divided into two-part:

**1) ****PARTITION **** 2) ****Quicksort_Iterative **

```
PARTITION (A, low, high)
{ pivot = A[r] // x is pivot
i = low – 1
for (j = low to high – 1)
{ if(A[j] <= pivot)
{ i = i + 1
exchange A[i] with A[j]
}
}
exchange A[i + 1] with A[r]
return i + 1
}
```

```
QuickSort_Iterative (A,low,high)
{
// Create an auxiliary stack
int stack[ high - low + 1 ];
// initialize top of stack
int top = -1;
// push initial values of low and high to stack
stack[ ++top ] = low;
stack[ ++top ] = high;
// Keep popping from stack while is not empty
while ( top >= 0 )
{
// Pop h and l
high = stack[ top-- ];
low = stack[ top-- ];
/* Here we called partition function which give us the position from where
we partition the list into left and right sublist */
int part = partition( A, low, high );
// push all left elements of pivot to stack
if ( p-1 > low )
{
stack[ ++top ] = low;
stack[ ++top ] = part - 1;
}
// push all right elements of pivot to stack
if ( p+1 < h )
{
stack[ ++top ] = p + 1;
stack[ ++top ] = high;
}
}
}
```

**Illustrating this procedure by example: **

__Suppose there is ____an array of ____ ____7____ elements____. And the array of unsorted elements is:__

**low = ****0**, **high = ****6** now as per algorithm **i ****= low -1 = 0 – 1** = **-1** and **pivot **= **x** = **4**

For we travers the array we continue loop **j**** = low to high -1**.

**1)** So, for first loop **i**** = -1** and** ****j** **= 0**. Now **A[j]**** > ****x** i.e. **5 > 4** so, **no swapping required between i and j**.

**2) **Next (2nd) loop **i**** = -1** and **j** **= 1 below:**

But here again **A[j] > x** i.e. **7 > 4** so, **no swapping required between i and j**.

**3)** Next (3rd) loop **i**** = -1** and **j** **= 2** (Incremented by 1) **bellow**:

Here **A[j] > x** i.e. **6 > 4** so, **no swapping required between i and j**.

**4)** Next (4th) loop **i**** = -1** and **j** **= 3** (Incremented by 1) **bellow**:

Here **A[j] < x** i.e. **1 < 4** so, we **first increment ****i**** by 1** i.e. **i**** = ****i ****+ 1 = -1 + 1 = ****0**** and swap with ****j.**

**5)** Next (4th) loop **i**** = 0** and **j** **= 4** (Incremented by 1) **bellow:**

Here **A[j] < x** i.e. **3 < 4** so, we** first increment** **i** **by 1** i.e. **i**** = ****i ****+ 1 = 0 + 1 = ****1**** and swap with ****j.**

**6)** Next (4th) loop **i**** = 1** and** ****j** **= 5** (Incremented by 1) **bellow:**

Here **A[j] < x** i.e. **2 < 4** so, we** first increment ****i**** by 1** i.e. **i**** = ****i ****+ 1 = 1 + 1 = ****2**** and swap with ****j.**

Now **end of loop** because **j = ****5**** = high -****1**. So, **increment**** i**** by 1** i.e. **i = i + 1 = 2 +1 =** **3 **and **swap with Pivot** i.e. **x**.

Now the** left-hand side** of the **pivot** contains all **smaller elements** and the **right-hand side** of the pivot contains all **larger elements**.

So, after **getting the position** from where we **partition ****left sub-list** and **right sub-list** we use **stack** to compute each list separately **by push and pop** and continue it until the stack is empty.

**Illustration of Iterative quicksort algorithm:**

**(1)** Initially the entire list **(0, 6)** is pushed **into the stack**.

**(2)** The list **(0,6)** is **POPed **and **divided into sub-list ****L1(0,2)**** and ****L2(4,6) **using **PARTITION ****ALGORITHM** and **pushed into **the **stack**. Now we do the same PARTITION algorithm for the left and right sub-list.

**(3)** The **right sub-list** **(4,6)** is **POPed** and **divided **into two **sub-list** **L1(4,4)** and **L2(5,6)**.

**L1(4,4)** is **not required to push** because it is a single element, **no push operation needed as they are either empty or containing a** **single element.**

**(4)** **The list **(5,6)** is POPed and divided into **sub-list** ****L1(6,6)**** and ****L2(empty)**** using the Divided procedure. **No push operation needed as they are either empty or containing a single element**.**

The list **(0,2)** is **POPed** and divided into sub-list **L1(0,0)** and **L2(2,2)** using divided procedure. **No push operation needed as they are either empty or containing single element**.

**Now the sorted elements are:**

__CHARACTERISTICS:__

**1.** It is totally based on the **divide and conquer** paradigm.

**2.** The data can be sorted very fast using this algorithm.

**3.** It is **not a stable sort**.

__TIME COMPLEXITY ANALYSIS:__

The time complexity of **recursive** and **iterative quicksort** is the same:

**For more details please follow the** **time complexity of recursion quicksort: **

https://mycareerwise.com/programming/category/sorting/quick-sort-using-recursion

__SPACE COMPLEXITY:__

**The space complexity** of the **in-place quicksort** is **O(1)** as it does not require any extra space for sorting. **But for each recursive call**,** the algorithm needs to use or maintain the stack to store some amount of data**.

Now, what is **space complexity** behind it and it depends on what is the **depth of stack** use. Now the **depth of the stack is the height of the tree**.

So, if the **tree is a balanced tree** then we know **level of the tree is** **log n**.

So, **space complexity** **O(log n) is**** ****the**** ****best case**.

But **worst case tree** can look like that

__ADVANTAGES:__

**1.** It is one of the fastest sorting algorithms.

**2. **It does not need any additional space for sorting.

**3. **It **works efficiently for a large amount of data**.

**4. **The average **case complexity is better than ****bubble**** or ****selection sort**.

__DISADVANTAGES:__

__APPLICATIONS:__

**1. **It is used in commercial applications whereas it runs fast, no additional storage space is required.

**2. **It is not used in such applications where guaranteed response time is required.

Related

- Quick Sort using recursion
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort using recursion
- Merge Sort Iterative
- 3 way Merge Sort
- Heap Sort using recursion
- Heap Sort Iterative
- Radix Sort for positive integer
- Bucket Sort
- Counting Sort
- Cocktail Sort
- Intro Sort
- Minmax Sort
- List Sort
- Tree Sort
- Shell Sort
- Gnome sort
- Comb Sort
- Bitonic Sort
- Tim Sort

Contributed by