Flutter Benchmark Tuesday: The King of Bubble Sort Falls
*** Spoiler Alert — Insertion Sort wins, but there’s a catch ***
We continue our regular series “Testing the Obvious Things on Tuesdays”. This time, following up on cycles (link to my previous article 👈), we will test the efficiency of different sorting algorithms in Flutter.
I’ll spare you the tedious introduction describing each algorithm since it will all become clear to you at the end of the article, okay? So, for today’s test subjects, we have:
- Bubble Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Quick Sort with Random Pivot Selection
- Built-in method sort
You’ve probably written half of these algorithms yourself in high school, and some of them even in kindergarten. Nevertheless, a foundation is a foundation.
C’mon, let’s go
As usual, we’ll start by creating a _test file in test folder, but instead of unit tests, we’ll have benchmarks (I’m such a visionary):
Useful tip: from the code above, you can take the bubble sort or selection sort for your laboratory work instead of googling or asking questions on Stack Overflow. Completely free of charge. Thank you.
At the beginning of the code snippet, 7 arrays are created — one for each of the sorting algorithms and an additional one for the built-in sorting method in Dart.
Then, each sorting algorithm is called, and the time it takes to execute is measured using the syncBenchmark() function from the benchmarking library. The results of the measurements are output to the console using the report() method.
We define functions for implementing each of the sorting algorithms: bubbleSort(), insertionSort(), selectionSort(), mergeSort(), quickSort(), and quickSortRandomPivot(). Each function takes an array of integers and sorts it according to the corresponding sorting algorithm.
merge() is a helper function for merge sort (mergeSort()). It merges two sorted subarrays into one sorted array.
Each function takes optional parameters left and right, which define the boundaries of the array that should be sorted. If these parameters are not specified, the function sorts the entire array.
Phew, that’s a lot of lines of code. Let’s run the test and see the result:
Oh my god, what do I see. Insertion sort crushed all competitors, it’s 20–200 times faster, Carl. I’ll review all of my code while drinking lavender latte 🤙.
Don’t forget to subscribe, like, and leave comments…
Wait, what?
TL;DR
Unfortunately, many developers sometimes forget about something as crucial as the time complexity of algorithms, which can lead to creating slow or inefficient code, or false conclusions about how their code works, as we can see in our case.
Time complexity of an algorithm is a measure of the amount of time required for an algorithm to run as a function of the size of the input. It evaluates how quickly an algorithm will work with an increase in the size of the input data, such as the number of elements in a list or the length of a string.
Okay, I understand. I’ll google this thing and choose an algorithm based on it. Is that okay?
Not quite. There’s one more thing that cannot be forgotten — the best and worst-case scenarios, meaning the configurations of input data in which an algorithm works either worse or better than in other cases.
Yes, these things are heterogeneous.
The best case for an algorithm is when it works most efficiently, i.e., when its time complexity is minimal. For example, for an algorithm for searching in a sorted array, the best case occurs when the desired element is in the middle of the array, and the time complexity in this case is O(1).
The worst case for an algorithm is when it works least efficiently, i.e., when its time complexity is maximum. For example, for an algorithm for searching in an unsorted array, the worst case occurs when the desired element is at the end of the array, and the algorithm will have to check each element of the array, leading to a time complexity of O(n).
Understanding the best and worst-case scenarios is essential when choosing an algorithm to solve a particular problem. An algorithm with a worst-case time complexity of O(n²) may be applicable to solving a problem if the worst-case scenario almost never occurs in real life but can be inefficient if it is used to process large volumes of data.
So, what do we have with our algorithms?
- Bubble Sort: time complexity — O(n²). Better to use for small arrays when high performance is not required or when the array is already nearly sorted.
- Insertion Sort: time complexity — O(n²), best case — O(n). Works well for small and partially sorted arrays.
- Selection Sort: time complexity — O(n²). Rarely used, mostly for teaching or on very small arrays.
- Merge Sort: time complexity — O(n log n). Works well for large arrays but requires additional memory to store temporary arrays.
- Quick Sort: average time complexity — O(n log n), worst case — O(n²). One of the most widely used sorting algorithms as it works well on large arrays and is usually faster than Merge Sort. However, on worst-case input data (e.g., already sorted arrays), performance can significantly degrade.
- Quick Sort with Random Pivot Selection: average time complexity — O(n log n), worst case — O(n²). Suitable for large arrays, similar to Quick Sort, but usually shows more stable performance on different input data due to the random selection of pivot elements.
- Built-in sort method: usually uses Quick Sort or Merge Sort depending on the implementation. Performance may vary depending on the specific implementation, but in general, it’s better to use it when special sorting configuration is not required and maximum performance needs to be achieved.
We can observe the implementation of the built-in sort method in Dart, which includes the following comment regarding the sorting algorithm:
/**
* Dual-Pivot Quicksort algorithm.
*
* This class implements the dual-pivot quicksort algorithm as presented in
* Vladimir Yaroslavskiy's paper.
*
* Some improvements have been copied from Android's implementation.
*/Quicksort? I’m not impressed.
Instead of Conclusion
Well, Insertion Sort has the best time complexity in the best case scenario when the array is already sorted. If the array is partially sorted or already sorted, Insertion Sort can work significantly faster than Bubble Sort, Selection Sort, Merge Sort, and even Quick Sort. In this case, random number generation likely resulted in a partially sorted array, which is why Insertion Sort performs much faster than the other algorithms.
However, in the worst-case scenario when the array is already sorted in reverse order, Insertion Sort will have a quadratic time complexity and will be slower than the other algorithms. Therefore, for general use, it’s better to choose other algorithms such as Quick Sort or Merge Sort, which have a more uniform time complexity in all cases.
Yes, using the built-in sorting method is usually the best option since it’s already optimized for performance and handles different input cases. In Dart, the sort method is a good choice for sorting arrays.
And now, please do subscribe to not miss any new articles!
You might also be interested in my other benchmarks:
Investing staff:
Tech staff:
Or a whole series of articles about working with REST API (it’s a real shit like Santa Barbara):
