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.

## References

- https://en.wikipedia.org/wiki/Quicksort
- https://www.journaldev.com/31541/merge-sort-algorithm-java-c-python
- https://www.journaldev.com/784/sort-array-java