Bubble Sort

Implementation of the bubble sort algorithm.

Photo by Wengang Zhai on Unsplash

Introduction:

• Bubble sort is used to sort the elements from the given array.
• It generally used when the array size is small.
• It works well when the list is partially sorted.
• O(n²) is the time complexity of bubble sort.

How Bubble Sort works??

Let’s understand…

It compares adjacent values in each iteration if they are in the wrong (first value is larger than second value) order then it swaps them.

In each iteration, the larger value is placed at the end of the list, (len(list)-i).

here ‘i’ is the ith iteration.

Implementation:

def bubble_sort(arr):
    for j in range(len(arr)-1):
        swapped = False
        for i in range(len(arr)-1-j):
            if arr[i]>arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
                swapped=True
        if not swapped:
            break
if __name__ == '__main__':
    
    array = [3,5,2,7,8,4]
    bubble_sort(array)
    print(array)
Output:
[2,3,4,5,7,8]

• In the above python code, we use the ‘swapped’ variable to optimize the algorithm.
• If our algorithm is already sorted then swapped value is false and it breaks the loop.
• or in the nth iteration, the list is completely sorted then after that iteration swapped value is false and it breaks the loop.

Conclusion:

• We have understood how bubble sort works.
• We also see the implementation of bubble sort.