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
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 is almost the same as the comb sort except the shrink value, which is 2 instead of 1.3.