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.

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