Teaching Kids Programming – Bubble Sort Implementation in Python (Simple Sorting Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

We have talked about the Quick Sort and Merge Sort which aims for O(NLogN) time complexity. The Bubble sorting is one of the simple sorting algorithm.

Bubble Sorting Algorithm

When we perform one round of bubble sorting, we swap the current number with next one if current number is bigger. So one round will bubble the largest element to the end of the un-sorted subarray. The largest elements are bubbled to the right which forms a sorted subarray. After N rounds we have a sorted list.

1
2
3
4
5
6
7
8

def bubbleSorting(arr):
    n = len(arr)  
    for i in range(n):
        # Last i elements are sorted
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

def bubbleSorting(arr):
    n = len(arr)  
    for i in range(n):
        # Last i elements are sorted
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

The time complexity is O(N^2).

Optimized Bubble Sorting Algorithm

If the array is already sorted, the above bubble sorting algorithm still takes O(N^2). But we can optimise this. If no swapping is performed in the inner loop – which means the remaining elements are already in order – thus we can terminate the sorting.

1
2
3
4
5
6
7
8
9
10
11
12
13

def bubbleSorting(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        # Last i elements are sorted
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # we haven't swapped so it is already in order
        if not swapped:
            break
    return arr

def bubbleSorting(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        # Last i elements are sorted
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # we haven't swapped so it is already in order
        if not swapped:
            break
    return arr

The best case time complexity is O(N). Bubble sorting algorithm uses O(1) constant space complexity.

Bubble sorting algorithm is stable – it maintains the relative order of the equal keys.

Sorting Algorithms (Teaching Kids Programming Tutorials)

• Teaching Kids Programming – Bubble Sorting (Simple Sorting Algorithm)
• Teaching Kids Programming – MergeSort Simply Explained
• Teaching Kids Programming – QuickSort Algorithm Simply Explained
• Teaching Kids Programming – Selection Sorting (Simple Sorting Algorithm)
• Teaching Kids Programming – Insertion Sort in Python (Simple Sorting Algorithm)
• Teaching Kids Programming – Counting Sort Algorithm in Python

–EOF (The Ultimate Computing & Technology Blog) —