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)

### Like this:

Like Loading...