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)

Bubble Sort in Moderation

Bubble sort is one of the lousy kinds of sorting approach available. But still it can perform very decent in moderation. The basic kind of bubble sort is:

def bubbleSort(A, n):
    for i in range(0, n-1):
        for j in range(0, n-1):
            if(A[j] > A[j+1]):
                temp = A[j]
                A[j] = A[j+1]
                A[j+1] = temp
    return A

If we look at the algorithm above we find that the second loop lapping over the iterated part of sorted elements, which increases the time complexity, so we can reduce the time complexity by reducing the iteration.

def bubbleSort(A, n):
    for i in range(0, n-1):
        for j in range(0, n-i-1):
            if(A[j] > A[j+1]):
                temp = A[j]
                A[j] = A[j+1]
                A[j+1] = temp
    return A

Comb Sort

In each run “gap” based sorting takes place in the algorithm. In each run, the sorting goes through the list over a distance of (0 to gap/shrink) on two elements at a time. To note, shrink value is a gap factor, which defines the gap between two elements in each iteration. And the gap between two elements will never be < 1, or we can say the list, or array becomes sorted when the gap value is equal to 1.

import math

def combsort(A):
    gap = len(A)
    shrink = 1.3 // most ideal gap shrink factor
    _sorted = False

    while(_sorted is False):
        gap = math.floor(gap/shrink)
        if(gap>1):
            _sorted = False
        else:
            gap = 1
            _sorted = True 
        i = 0
        while(i + gap < len(A)):             if(A[i]>A[i+1]):
                temp = A[i]
                A[i] = A[i+1]
                A[i+1] = temp
                _sorted = False
            i = i + 1
    return A

Graphical Demonstration of the Comb sort:

Shell Sort:

Shell Sort is almost the same as the comb sort except the shrink value, which is 2 instead of 1.3.