BubbleSort is a very popular sorting algorithms. In this article you will learn about the features of BubbleSort and how to implement the sorting algorithm in Dart. Of course, this code will also be explained.
If you want to follow me further in this series and are interested in other articles, then I recommend you to follow me.
Enjoy the read!
Introduction
BubbleSort is based on the idea that you always compare two adjacent elements and swap them if necessary. If this is done all the way to the end, the large numbers slip to the end of the list.
So far so good… but how does the name BubbleSort come about? Well, you can imagine the numbers like water bubbles. Larger bubbles (i.e. bigger numbers) move up faster than smaller ones.
How it works
Now let’s explain BubbleSort again with a card example and go a bit deeper into the concept.
We have a stack of cards where each card has a number from 1–10. This stack is not sorted. First we take the first two cards and compare them to each other. Then we sort them to each other. So if the first card has a greater value than the second, the two cards are swapped. Now we compare the second card with the third card and swap them again. A complete comparison with possible swapping is called a compare and swap operation.
When the last two cards in a round have been compared, the highest number is now at the end. Such a round is also called a bubble phase. After each further bubble phase, the next highest number is at the end.
Properties
Let’s start with your properties with runtime complexity. In the best case scenario, the numbers in the array are already sorted. No swap operation needs to be performed and the algorithm only goes over the entire array once. If the number of elements in the input array is n, then our time complexity is O(n).
Let us now turn to the worst case. Since BubbleSort runs in two loops in the programming code (we will get to this in the implementation in Dart) and in the worst case the outer loop runs n times, we get a runtime of O(n x n ) = O(n²).
The runtime of the average case is the same as that of the best case, but this time it is calculated a bit differently. n/2 passes are made and n comparisons, resulting in the following calculation: O(n/2 x n) = O(n²).
Another property of BubbleSort is the stability of the algorithm. Since two elements are always compared and they are only swapped if the left one is larger, the algorithm is stable.
BubbleSort does not need an auxiliary array and only needs a fixed size of memory, so the space complexity is O(n).
Implementation in Dart
In this section I want to show you how to implement BubbleSort in Dart. Therefore every step in the code is commented:
Conclusion
Today you have learned what BubbleSort is, what properties this sorting algorithm has and how to implement it in Dart.
I hope you were able to learn something and enjoyed it! If so, I’d be very happy if you give this post some claps.
Oh, and before I forget to mention it: I’ll be introducing some more sorting algorithms in Dart in the near future. If you don’t want to miss that, you should definitely follow me!
Have a nice day!