Trusted answers to developer questions

Abel Lifaefi Mbula

As programmers, we’re likely to come up against data structure and algorithm questions when going for job interviews. This helps companies make sure they hire a systematic problem solver developer.

In this shot, we’ll learn about one of the simplest sorting algorithms, bubble sort. We’ll learn how it works, and how we can implement it in Python.

**Bubble sort** is used to repeatedly compare adjacent items in a list and exchange them if they are in the wrong order.

Let’s consider a list that needs to be sorted in ascending order. To do this with bubble sort, we’ll start by comparing the first list item with the second. If the first item is greater than the second, we swap both items and compare the second and the third, and so on.
So, for a list of size `n`

, we need to repeat this process `n - 1`

times.

Note:

- Bubble sort is also called comparison algorithm.
- In real life, we can observe bubble sort when people in a queue swap their positions among themselves until everyone is standing based on increasing order of heights.

Let’s visualize an example of bubble sort for a better understanding of bubble sort.

Let’s consider this list of integer values: 19, 1, 9, 3, 10, 13. We want to sort it in ascending order.

We start with the index 0 and 1: `19 > 1`

is *true*. We swap both items.

Below is what the sorted list will look like:

Next, we compare the index 1 and 2: `19 > 9`

is *true*. We’ll swap again.

Below is what the sorted list will look like:

We proceed with the index 2 and 3: `19 > 3`

is *true*. Again, we swap these items.

Below is what the sorted list will look like:

Let’s continue the comparison with the index 3 and 4: `19 > 10`

is *true*. We swap these items.

Below is what the sorted list will look like:

We proceed with the index 4 and 5: `9 > 13`

is *true*. We’ll swap.

Below is what the sorted list will look like:

This is the end of the first iteration. We can notice how the newly formed, sorted list is in ascending order. **1, 9, 0, 13, 19**.

In the second iteration, we do the same thing as we did in the first iteration.

We start with the index 0 and 1: **1 > 9** is *false*. We don’t need to swap.

Next, we proceed with the index 1 and 2: **9 > 3** is *true*. We swap.

Below is what the list will look like after swapping:

Finally, every item is in its right position. This marks the end of the process.

Note:If the list does not sort as expected, we continue with the sorting processes until we get a fully sorted list.

It’s always a good practice to use pseudocode before actual implementation. Below is a pseudocode for bubble sort.

```
function bubbleSort(array)
Set isSwapped to true
WHILE isSwapped = true
Reset isSwapped to false
FOR each item in the array
IF current-item > next-item
swap items
Reset isSwapped to true
ENDIF
ENDFOR
ENDWHILE
RETURN array
```

Now, we’ll implement the bubble sort algorithm in Python. Let’s get started.

def bubbleSort(list): for i in range(len(list) - 1): if(list[i] > list[i + 1]): temp = list[curr_index] list[curr_index] = list[curr_index + 1] list[curr_index + 1] = temp

Initial bubbleSort()

Our method of implementation is not that complicated. We’ll go through a list of integers by comparing adjacent items to see if they need to be swapped. If so, we swap them.

- First, we keep the left item in a temporary variable,
`temp`

. - Next, we assign the value of the right item to the left one.
- Lastly, we assign the right item,
`temp`

.

To make our code clearer and more readable, let’s use the `swap()`

method.

```
def swap(list, curr_index):
temp = list[curr_index];
list[curr_index] = list[curr_index + 1]
list[curr_index + 1] = temp
```

Our code works fine, but only for one iteration, which is not enough to sort the list as expected.

Let’s modify the code so that it can loop over and over until we get a fully sorted list.

# Bubble sort: Python implementation by Abel def bubbleSort(list): isSwapped = True while(isSwapped): isSwapped = False for i in range(len(list) - 1): if(list[i] > list[i + 1]): isSwapped = True swap(list, i)

Use while loop to go through the list over and over

We’ve create a boolean variable, `isSwapped`

, and initialize it to `true`

. By doing so, it allows us to use it in a `while`

loop. Inside the `while`

loop, we first assume that we need swapping, so we set `isSwapped`

to `false`

. If we swap, we reset it back to `true`

.

Let’s put it all together and run our code.

# Bubble sort: Python implementation by Abel def bubbleSort(list): isSwapped = True while(isSwapped): isSwapped = False for i in range(len(list) - 1): if(list[i] > list[i + 1]): isSwapped = True swap(list, i) def swap(list, curr_index): temp = list[curr_index]; list[curr_index] = list[curr_index + 1]; list[curr_index + 1] = temp; # Test bubble sort list = [ 19, 1, 9, 3, 10, 13 ] bubbleSort(list) print('Sorted array in ascending order:') print(list)

Test our implementation

Congratulations! Our implementation of the bubble sort algorithm in Python is successful.

If you want to change the sorting order from ascending to descending, all you have to do is change the

`>`

operator atline 9with the`<`

operator; the rest of the code will remain the same.

On a final note, let’s look at one last anecdote on the performance of this algorithm.

Bubble sort is a straightforward sorting algorithm and a prolonged one. Due to that, we’ll rarely find or use it in the real world. It is used primarily for educational purposes.

Time Complexity: $O(n^2)$Worst Case If the array is not sorted. Time Complexity: $O(n)$Best Case If the array is sorted. Time Complexity: $O(n^2)$Average Case If the array is partially sorted. - Space Complexity: $O(1)$

Happy coding!

RELATED TAGS

bubble

algorithm

python

sort

communitycreator

CONTRIBUTOR

Abel Lifaefi Mbula

RELATED COURSES

View all Courses

Keep Exploring

Related Courses