Bubble Sort / Sinking Sort

           (Comparing and Swapping algorithm)

It is one of the easiest sorting algorithm that over and over strides through the list, compares adjacent pairs and swaps them in the event that they are in the wrong order. The go through the list is repeated until the list is sorted. The algorithm, which is a comparison sort, is naming convention for the way smaller or larger elements “bubble” highest priority to the top of the list.

Same process of comparison and swapping repeated again and again until it get sorted completely.

Implementation of bubble sort in Python.

alist = [54,26,93,17,77,31,44,55,20]

def bubbleSort(list):

   for passnum in range(len(alist)-1,0,-1):

       for i in range(passnum):

           if alist[i]>alist[i+1]:

               temp = alist[i]

               alist[i] = alist[i+1]

               alist[i+1] = temp

alist = [54,26,93,17,77,31,44,55,20]

bubbleSort(alist)

print(alist)

Result : [17, 20, 26, 31, 44, 54, 55, 77, 93]

Implementation without any extra temp variable :

# Python3 Optimized implementation

# of Bubble sort

# An optimized version of Bubble Sort

def bubbleSort(arr):

   n = len(arr)

      # Traverse through all array elements

   for i in range(n):

       swapped = False
      # Last i elements are already

       # in place

       for j in range(0, n-i-1):

           # traverse the array from 0 to

           # n-i-1. Swap if the element

           # found is greater than the

           # next element

           if arr[j] > arr[j+1] :

               arr[j], arr[j+1] = arr[j+1], arr[j]

               swapped = True

 

       # IF no two elements were swapped

       # by inner loop, then break

       if swapped == False:

           break

          

# Driver code to test above

arr = [64, 34, 25, 12, 22, 11, 90]

  bubbleSort(arr)

  print (“Sorted array :”)

for i in range(len(arr)):

   print (“%d” %arr[i],end=” “)

Result : Sorted array:
11 12 22 25 34 64 90

Time Complexity :

Worst-case  : O(n^2) comparisons,

O(n^2) swaps

Worst case occurs when array is reverse sorted.

Best-case performance : O(n) comparisons,

O(1) swaps

Best case occurs when array is already sorted.

Average performance : O(n^2) comparisons

 O(n^2) swaps

Space Complexity

worst-case  space complexity :   auxiliary (1)