Bubble Sort

Sorting is when we rearrange the elements in such a way that all elements are in ascending or descending order.

For example:

arr = [2, 5, 1, 8, 3, 6, 3]

sortedArr1 = [1, 2, 3, 3, 5, 6, 8] (ascending)

sortedArr2 = [8, 6, 5, 3, 3, 2, 1] (descending)

Sorting algorithms play a crucial role in Computer Science due to a large number of use cases such as databases, process scheduling, etc.

There are many sorting algorithms, this week I'm going to discuss some of the common sorting algorithms that have worst case time complexity O(N²).

Bubble Sort:

It is one of the simplest sorting algorithms. 

1. It repeatedly checks for a pair of two elements whether the element before in sequence [(i-1)^th element] is smaller than the next element adjacent [i^th element] to it or not. 

2. If the (i-1)^th element is greater than the i^th element, then the element positions are swapped and move to the next adjacent element i.e. comparing i^th element with (i+1)^th element.

3. If the (i-1)^th element is smaller than the i^th element, then we simply skip and go to the next adjacent element (i+1)^th element.

4. This process is repeated until the end of the array is not reached.

5. If there are N elements then steps 1 to 4 have to be repeated N times for sorting the complete array.

Example:

Let the array = [5, 2, 1, 3, 4]

Iteration 1.

(5, 2, 1, 3, 4) -> (2, 5, 1, 3, 4) -> swap(5, 2) as 5 > 2

(2, 5, 1, 3, 4) -> (2, 1, 5, 3, 4) -> swap(5, 1) as 5 > 1

(2, 1, 5, 3, 4) -> (2, 1, 3, 5, 4) -> swap(5, 3) as 5 > 3

(2, 1, 3, 5, 4) -> (2, 1, 3, 4, 5) -> swap(5, 4) as 5 > 4

After each i^th iteration, the (N-i+1)^th largest element in the array comes at its correct position. For example, 5 came at last index after 1^st iteration.

Iteration 2.

(2, 1, 3, 4, 5) -> (1, 2, 3, 4, 5) -> swap(2, 1) as 2 > 1

(1, 2, 3, 4, 5) -> (1, 2, 3, 4, 5) -> skip as 2 < 3

(1, 2, 3, 4, 5) -> (1, 2, 3, 4, 5) -> skip as 3 < 4

.

.

.

It is obvious to our eyes that the array is sorted after the 2^nd iteration but the algorithm will check 3 more times as it doesn't know that the array is sorted unless it gets all the elements at the right location after each iteration.

To optimize this approach we can check that if in the inner loop execution there are no swaps, then we could simply stop any further execution.

Code in Python:

# bubble sort function
def bubble_sort(arr):
    n = len(arr)
    
    # Repeat loop N times
    # equivalent to: for(i = 0; i < n-1; i++)
    for i in range(0, n-1):
        # Repeat internal loop for (N-i)th largest element
        for j in range(0, n-i-1):
          
            # if jth value is greater than (j+1) value
            if arr[j] > arr[j+1]:
                # swap the values at j and j+1 index
                # Pythonic way to swap 2 variable values -> x, y = y, x
                arr[j], arr[j+1] = arr[j+1], arr[j]
              

arr = [64, 34, 25, 12, 22, 11, 90]
print('Before sorting:', arr)

# call bubble sort function on the array
bubble_sort(arr)

print('After sorting:', arr)

"""
Output:
Before sorting: [64, 34, 25, 12, 22, 11, 90]
After sorting: [11, 12, 22, 25, 34, 64, 90]
"""

Optimised Code:

Using a condition to check if there were any more swaps in the inner loop will help us return out from the loop quickly many times.

# bubble sort function
def bubble_sort(arr):
    n = len(arr)

    for i in range(0, n-1):
        # variable for checking if any valued were swapped
        swapped = False
    
        for j in range(0, n-i-1):
          
            # if jth value is greater than (j+1) value
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                # if values swapped then set swapped = True
                swapped = True

        # if none of the values were swapped implies that the array is sorted
        # return
        if swapped is False:
            return


arr = [64, 34, 25, 12, 22, 11, 90]
print('Before sorting:', arr)

# call bubble sort function on the array
bubble_sort(arr)

print('After sorting:', arr)

Time Complexity:

Bubble sort works in O(N²) time complexity in worst case which is when the array is sorted in descending order.

ex. arr = [5, 4, 3, 2, 1]

Best case is when the array is sorted in ascending order, in which the array elements won't be swapped and hence loop will finish after first iteration itself, hence O(N).

Google Search: Bubble Sort

Here is the code in C language: Bubble Sort in C

p.s.I use a trick to remember what bubble sort does by the name itself "BUBBLE". Imagine a soap bubble in which only 2 elements can be kept at once. We compare those 2 elements, remove the smaller one and add the next element in the bubble by moving the bubble one step ahead.

--
Have any questions or suggestions? Post in the comments below!!

By,

Anubhav Shrimal