How to Bubble Sort in Python

Understanding Bubble Sort

Start with an array (or other data structure) that you wish to sort. This example will start with the array [3, 7, 2, 4, 9, 1].

Compare the first element with the second element. Swap them if first element is greater than the second. In the example, these are 3 and 7 respectively, which are already in order (ascending), so the array remains [3, 7, 2, 4, 9, 1].

Compare the second element with the third element. Again, swap if the second element is greater than the third. In the example, 7 > 2, which results in a swap to [3, 2, 7, 4, 9, 1].

Continue iterating across the entire array until you reach the end, comparing adjacent elements and swapping if the former is greater than the later. The example goes [3, 2, 7, 4, 9, 1] → [3, 2, 4, 7, 9, 1] → [3, 2, 4, 7, 9, 1] → [3, 2, 4, 7, 1, 9].

Iterate across the array and compare (and swap if necessary) adjacent elements again, but this time, stop at the second-to-last element since the largest element is in the last spot (this is guaranteed and is how bubble sort works). The example goes [3, 2, 4, 7, 1, 9] → [2, 3, 4, 1, 7, 9].

Keep iterating across the array, comparing and swapping as needed. End one index earlier each time. By iteration (not by comparison), the example goes [2, 3, 4, 1, 7, 9] → [2, 3, 1, 4, 7, 9] → [2, 1, 3, 4, 7, 9] → [1, 2, 3, 4, 7, 9].

Stop once the array (or other data structure) is completely sorted. Since each time, you stop one index earlier than the previous time, you will be done in at most n-1 passes, but you can optimize the process by stopping if an iteration results in no change since more passes will also cause no changes. The i-th pass puts the i-th largest element in its proper sorted position, which is why you stop one index earlier each time.

Implementing Bubble Sort in Python

Define a function for the bubble sort. In Python, this is done by writing the keyword def followed by a space, the function name, an open parenthesis, any parameters separated by commas, a closing parenthesis, and finally a colon. In this case, a function declaration could begin as def bubble_sort(arr): since it is intended to sort an array (arr). Afterwards, indent because that is how Python knows you are inside the function.

Create a for loop for the passes. This loop needs to run n-1 times as seen earlier. In Python, for loops are for in loops, so you specify a variable and range to make them run a specific number of times. Here, use for i in range(len(arr)-1):. Again, use a colon and indent the next line, which tells Python that you are inside the loop.

Create another for loop that will iterate over the array. Within this loop, you will compare adjacent elements and swap them if necessary. Since each pass there is one less element you need to check (as the greatest element in each pass is in its final position), you only need to go to the index len(arr)-i-1. The -1 is because you will check the element at the current index and the next index, so this index will never reach the end. Here, the for loop declaration will be for j in range(len(arr)-i-1):. Again, indent on the next line.

Write an if statement to compare the adjacent elements. You will compare the j th element and the (j+1) th element, so you can use if arr[j] > arr[j+1]:. Again, indent on the next line.

Write the code to swap if the if statement is satisfied. Thus, this portion will look like t = arr[j] arr[j] = arr[j+1] arr[j+1] = t t is a temporary variable to store the contents of arr[j] since we overwrite it.

Confirm that what you have is correct. At this point, your code should look like def bubble_sort(arr): for i in range(len(arr)-1): for j in range(len(arr)-i-1): if arr[j] > arr[j+1]: t = arr[j] arr[j] = arr[j+1] arr[j+1] = t What you have is now capable of performing a bubble sort! Try it out. Note that this mutates or modifies arr directly. Also, be sure to unindent all the way when doing anything else like declaring the input and calling the function, so that you are not inside the function. For example, we can do the following: def bubble_sort(arr): for i in range(len(arr)-1): for j in range(len(arr)-i-1): if arr[j] > arr[j+1]: t = arr[j] arr[j] = arr[j+1] arr[j+1] = t a = [3, 7, 2, 4, 9, 1] bubble_sort(a) print(a) [1, 2, 3, 4, 7, 9]

Optimize the loop by ending early if there is no change during a pass. While what you have will work perfectly find, you can improve the performance by ending the loop if no change happens during the loop. To do this, you can add a variable called done inside the pass loop but outside the iteration loop and initialize it to True (note the capitalization in Python). Then, there is a swap, set the value to False since the sorting is not done. Finally, you will need to check if done is True at the end of the pass, and if so, end the loop. This will look like def bubble_sort(arr): for i in range(len(arr)-1): done = True for j in range(len(arr)-i-1): if arr[j] > arr[j+1]: t = arr[j] arr[j] = arr[j+1] arr[j+1] = t done = False if done: break

Test your code to make sure it works. Though it should work at this point by following the steps, unexpected errors always come up. Make sure your indentation is correct, and make sure you typed everything correctly. Debugging is a fundamental part of programming, as painful as it can be at times.