The QuickSort Algorithm – Implementation in C, Java, Python

Quicksort Algorithm

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:

  1. 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,
  2. Sort the sub-arrays,
  3. 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.

Fig123
Quicksort Algorithm

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.

Fig456 1
Quicksort Algorithm

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.

Fig789
Quicksort Algorithm

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.

Fig101112
Quicksort Algorithm

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.

Fig13
Quicksort Algorithm

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:

Quicksort In C
Quicksort In C

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

Quicksort In Java
Quicksort In Java

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:

Quicksort In Python
Quicksort In Python

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

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages