Table of Contents

## Introduction

**Quicksort algorithm** is one of the fastest internal sorting algorithms and today we are going to discuss this topic.

It is mainly based on the following three main strategies:

**Split or Partition**: Select a random element called pivot from the given sequence of elements to be sorted. Suppose the element is X, where X is any number. Now split the list into two small arrays or lists Y and Z such that, all elements in Y are smaller than X whereas all elements in Z are larger than X,**Sort**the sub-arrays,**Merge**(join or concatenate) the sorted sub-arrays.

The split divides the arrays into two smaller arrays. When these sub-arrays are ultimately sorted recursively using quicksort these sub-arrays are called **conquered**. Therefore, quicksort is based on **divide and conquer algorithm.**

## The Quick Sort Algorithm

Suppose there are N elements as a[0], a[1], …, a[N-1]. The steps for using the quick sort algorithm are given below,

**#1:** Select any element as a **pivot**. For example, we select the first element here. It’ll help to split the array into two parts.

PIVOT = a[ FIRST ] //pivot selected,FIRST=0 here

#**2:** Initialize two pointers **i **and **j **as,

i = FIRST + 1 //First index of the array j = LAST //Last index of array

#**3**: Now we increase the value of** i **until we locate an element that is greater than the pivot element,

WHILE i<=j and a[i]<= PIVOT i=i+1

#**4: **We decrease the value of j until we find a value less than the pivot element,

WHILE j<=j and a[j]>= PIVOT j=j-1

**#5:** If **i<j** interchange a[i] and a[j].

#**6:** Repeat Steps 2 to 4 until** i>j**,

**#7:** Interchange the selected pivot and a[j],

#**8**: And finally recursively call this Quicksort for the two sub-arrays hence created at the two sides of the pivot element.

## Understanding the Algorithm with an Example

Now, let us understand how the algorithm works using a simple example.

We have considered an array having values **50, 30, 10, 90, 80, 20, 40, 60** as shown in **figure 1.** At first, we select a pivot element which in our case is the first element, **50**.

Then we initialize **i **and **j **pointers as shown in **figure 2** pointing on 30 and 60 respectively. Hence we move the i pointer towards the right until the element is greater than the pivot one. Which in our case we get at index 3, that is the value **90**.

Similarly, j is moved towards the left until it finds a value smaller than the pivot, which we get at index 6 that is a value of **40**. At this point in **figure 6**, we can see we have got both i and j values. Finally, we **swap **the corresponding values and get to a position shown in **figure 7**.

Then we again go through the i and j index searching and hence get to **figure 9**, where both our pointers, i and j stand at 4th and 5th index.

Similar to the previous case, we **swap **the corresponding values at ith and jth positions. So after this, we need to move the pointer i towards the right and j towards the left. Since 20<50, so we need to increase i by 1 towards the right. As 80>50, we stop moving i further. As shown in **figure 10 **and **11**.

Then we start moving j towards the left. As 20<50, j is decreased by 1 and now stands at the 4th index as shown in figure 12. From the above condition, it is clear that i crosses j. Thus we stop at the point where j<i. Therefore the position of j is the **split **point.

Hence we swap the pivot and the value at index j points at giving us the array as in **figure 13.**

After this, we have to apply the same method for the sub-arrays to the left and right of the pivot element, **50**. By this **divide and conquer** method, finally, we will get our sorted array.

## Implementing the QuickSort Algorithm

### 1. QuickSort Algorithm in C

#include<stdio.h> void quicksort(int a[25],int first,int last) { int i, j, pivot, temp; if(first<last){ pivot=first; i=first; j=last; while(i<j){ while(a[i]<=a[pivot] && i<last) i++; while(a[j]>a[pivot]) j--; if(i<j){ temp=a[i]; a[i]=a[j]; a[j]=temp; } } temp=a[pivot]; a[pivot]=a[j]; a[j]=temp; quicksort(a,first,j-1); quicksort(a,j+1,last); } } int main() { int i, n, a[25]; printf("Enter total no.of elements: "); scanf("%d",&n); printf("Enter the elements: "); for(i=0;i<n;i++) scanf("%d",&a[i]); quicksort(a,0,n-1); printf("Sorted Array: "); for(i=0;i<n;i++) printf(" %d",a[i]); return 0; }

**Output**:

### 2. QuickSort Algorithm in Java

public class Quicksort { int position(int a[], int first, int last) { int pivot = a[last]; int i = (first-1); for (int j=first; j<last; j++) { if (a[j] <= pivot) { i++; int temp = a[i]; a[i] = a[j]; a[j] = temp; } } int temp = a[i+1]; a[i+1] = a[last]; a[last] = temp; return i+1; } void Qsort(int a[], int first, int last) { if (first < last) { int p = position(a, first, last); Qsort(a, first, p-1); Qsort(a, p+1, last); } } public static void main(String args[]) { int a[] = { 50, 30, 10, 90, 80, 20, 40, 60}; int n = a.length; Quicksort ob = new Quicksort(); ob.Qsort(a, 0, n-1); System.out.println("sorted array:"); for (int i=0; i<n; i++) System.out.print(a[i]+" "); System.out.println(); } }

**Output**

### 3. QuickSort Algorithm in Python

def quicksort(Mylist): n=len(Mylist) Rec_quicksort(Mylist, 0, n-1) def Rec_quicksort(Mylist, first, last): if first<last: pos=position(Mylist, first, last) Rec_quicksort(Mylist, first, pos-1) Rec_quicksort(Mylist, pos+1, last) def position(Mylist, first, last): pivot=Mylist[first] i=first j=last while i<j: while i<=j and Mylist[i]<=pivot: i=i+1 while pivot<Mylist[j]: j=j-1 if i<j: temp=Mylist[i] Mylist[i]=Mylist[j] Mylist[j]=temp temp=Mylist[first] Mylist[first]=Mylist[j] Mylist[j]=temp return j Mylist=[ 50, 30, 10, 90, 80, 20, 40, 60 ] print("Given list:",Mylist) quicksort(Mylist) print("After sorting list is:",Mylist)

**Output**:

## Time and Space Complexity of QuickSort Algorithm

### Space complexity

The space complexity of Quicksort algorithm is given by **O(log(n)).**

### Time complexity

The time complexity of Quicksort algorithm is given by,

**O(n log(n))**for best case,**O(n log(n))**for the average case,- And
**O(n^2)**for the worst-case scenario.

## Conclusion

Finally, we hope you have a very good understanding of the **Quicksort algorithm**. We implemented the same in **C, Java, **and** Python** to help programmers comfortable with either of the languages understand this algorithm better. Let us know if you have any questions about this topic in the comments.