Bubble Sort Cutaway

Bubble sort at your pace

January 31, 2023

781 words/4 min read

What is bubble sort?

Bubble sort is a relatively easy to understand and easy to implement algorithm. It was one of the earliest ones to be discovered. It has an average and worst- case complexity of \(O(n^2)\) and a space complexity of \(O(n)\).

The algorithm itself is intuitive and involves swapping elements, that are not in the correct order, by repeatedly traversing the array until all the elements are in the correct order i.e., the array has been sorted.

Owing to its high complexity, it is rarely used in practice. However, it is interesting to observe it at work. A basic bubble sort implementation is shown below:

1
2
3
4
5
6


def basic_bubble_sort(arr):
    for i in range(len(arr)-1):
        for j in range(len(arr)-1-i):
            if(arr[j] > arr[j+1]): #is a swap needed?
                arr[j],arr[j+1] = arr[j+1],arr[j]
    return arr

Our cutaway implementation

Our implementation adds some features to the code that helps us observe the working of the algorithm as it goes about its business. The highlighted lines in the code below help us with the ‘animation’. You will also note the early exit from the loop, as soon as one traversal happens without any swaps, indicating that the array is already sorted.

As the run progresses, pairs of numbers are highlighted in cyan color if they are already in order and in yellow if they need to be swapped. The array then updates to show the post swap status if applicable. You can tweak the highlighting characters if the colors do not show up on your terminal. The sleep amount on line 53 can also be suitably changed.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87


from time import sleep

class style:
   PURPLE = '\033[95m'
   CYAN = '\033[96m'
   DARKCYAN = '\033[36m'
   BLUE = '\033[94m'
   GREEN = '\033[92m'
   YELLOW = '\033[93m'
   RED = '\033[91m'
   BOLD = '\033[1m'
   UNDERLINE = '\033[4m'
   END = '\033[0m'
   
'''
A function to help animate bubble sort.  Composes a pre-formatted string
highlighting the two array elements to be swapped (or not). Printing
the embellished string in place, 'animates' it.
'''
   
def decorate_array(arr, idx1, idx2, plain_mark=(style.CYAN,style.END), 
                        emph_mark=(style.YELLOW,style.END),emph=False):
	'''
	Returns a decorated string from array arr. The decoration goes
	around the elements with indices idx1 and idx2. The plain deco
	is used when deco is False and the emph deco is used when
	deco is True. deco is True when elements have to swapped in the sort.	
	'''
	deco_str = ''
	for idx,elem in enumerate(arr):
		if idx in [idx1,idx2]:
			mark = [plain_mark,emph_mark][emph] # assigns plain or emph mark based on emph flag
		else:
			mark = ('','')
		
		deco_elem = f'{mark[0]}'+f'{elem:^4}'+f'{mark[1]}' # control deco position
		deco_str += f'{deco_elem:^6}' # print centered
			
	return deco_str


#Bubble sort algorithm with cutaway implentation

def bubble_sort(arr,animation=False):
    '''Bubble sort an array with optional animation.'''
    cmp = 0   # Number of comparisons
    n_swaps = 0  # Number of swaps
    _idx = len(arr)-1
    for i in range(_idx):
        sorted = True # set to False if there is a swap
        for j in range(_idx-i):
            cmp += 1
            swap = False # needed only for highlighting elements to swap
            if(arr[j] > arr[j+1]): #is a swap needed?
                swap = True
            if(animation): # if animation is True, print deco based on swap flag
                print(' '*80,'\r',decorate_array(arr,j,j+1,emph=[False,True][swap]), 'cmp:',cmp,'swaps:',n_swaps,end='\r')
                sleep(0.7)
            if(swap):
                arr[j],arr[j+1] = arr[j+1],arr[j]
                n_swaps += 1
                sorted = False # we need at least one more pass to check
            
        if (sorted): 
            break # there was no swap, array is already sorted
    
    return arr
    
# Basic bubble sort for comparison

def basic_bubble_sort(arr):
    for i in range(len(arr)-1):
        for j in range(len(arr)-1-i):
            if(arr[j] > arr[j+1]): #is a swap needed?
                arr[j],arr[j+1] = arr[j+1],arr[j]
    return arr

if __name__ == "__main__":
             
    arr = [95,96]+list(range(11))+[97,98]
    arr = list(range(11,0,-1))
    # suggestion: numbers 0 and 99 to avoid the format messing up.
    
    print(*arr)

    print('\n',*bubble_sort(arr,animation=True))
    #print('\n',*basic_bubble_sort(arr))

Playing around with the code

Here are some things you can try out to understand the algorithm better.

Try sorting an array with a large number like 99 followed by other smaller numbers and watch the large number drift to the end of the array.
Try sorting an already sorted array. What do you observe? Would you get the same behaviour without the swap flag?
In the comparison statement on line 49, try changing the > to <. What happens to array sorting behaviour?