Quicksort with Lomuto partition scheme

An efficient sorting Algorithm, which follows the divide-and-conquer strategy. Partitioning is the center of attention in this algorithm. Partitioning is the process of dividing, and sorting a list of data. It is done through a selection of pivot. A pivot is the key value, using which the list of data is divided into two major sections in each iteration. But in Quicksort, data is sorted based on the pivot value.

Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation. – quicksort

Lomuto partitioning scheme is one of the two well partitioning scheme. Another one is Haore partitioning scheme. In this article we will see how the quicksort can be implemented using the Lomuto partitioning scheme.

def quicksort(A, lo, hi):
 if(lo < hi):
       p = partition(A, lo, hi)
       quicksort(A, lo, p-1)
       quicksort(A, p+1, hi)
 return A
 

def partition(A, lo, hi):
 pivot = A[hi]
 i = lo
 for j in range(lo, hi):
       if(A[i]<pivot):
              temp = A[j]
              A[j] = A[i]
              A[i] = temp
              i = i+1
 temp = A[hi]
 A[hi] = A[i]
 A[i] = temp
 return i 

A = [0,32,11,0,67,34]
print(quicksort(A, 0, len(A)-1))
output:
[0, 0, 11, 32, 34, 67]       

Time complexity :

Worst-case : O(n^2); Average-case: O(nlogn); Best-case: O(nlogn)

Author: ashiquechowdhury

A software developer, and a data science enthusiast

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s