Python sorting Algorithms: Bubble Sort

Sometimes, data we store or retrieve in an application can have little or no order. We may have to rearrange the data to correctly process it or efficiently use it. Over the years, computer scientists have created many sorting algorithms to organize data.

In this article we'll have a look at popular sorting algorithms, understand how they work and code them in Python. We'll also compare how quickly they sort items in a list.

For simplicity, algorithm implementations would be sorting lists of numbers in ascending order. Of course, you're free to adapt them to your needs. For this tutorial, we gonna use a sorting algorithms call "Bubble Sort".Is the simplest sorting algorithm iterates over a list, comparing elements in pairs and swapping them until the larger elements "bubble up" to the end of the list, and the smaller elements stay at the "bottom".


Explanation


We begin by comparing the first two elements of the list. If the first element is larger than the second element, we swap them. If they are already in order we leave them as is. We then move to the next pair of elements, compare their values and swap as necessary. This process continues to the last pair of items in the list.


Upon reaching the end of the list, it repeats this process for every item. Though, this is highly inefficient. What if only a single swap needs to be made in the array? Why would we still iterate though it n^2 times, even though it's already sorted?

Obviously, to optimize the algorithm, we need to stop it when it's finished sorting, otherwise it'll reevaluate an already sorted array many times.

How would we know that we're finished sorting? If the items were in order then we would not have to swap any. So, whenever we swap values we set a flag to True to repeat sorting process. If no swaps occurred, the flag would remain False and the algorithm will stop.


Code:


In this example, we take number 5, 2, 1, 8 ans 4. So the output will be 1, 2, 4, 5 and 8.

Of course, you can change the number.

The source code is avalaible here, but I recommand you to write it by yourself :)