Sorting algorithms can be evaluated in various ways, so there isn’t a single "best" algorithm. Instead, different sorting algorithms excel in different scenarios, depending on factors such as the size of the data, the order of the data, and the available memory.
For example, consider the trade-off between swaps and comparisons. When sorting large, heavy containers, swaps are more costly than comparisons, so minimizing swaps becomes crucial. On the other hand, if you're sorting berries based on their nutritional content, comparisons (e.g., running lab tests) are far more expensive than simply switching their positions by hand, making it essential to minimize comparisons instead.
Plus, we must remember that all algorithms have best-case and worst-case scenarios, and the time-complexity of an algorithm is always measured by the worst-case.
https://www.youtube.com/watch?v=xli_FI7CuzA
def swap(arr, a, b):
temp = arr[a]
arr[a] = arr[b]
arr[b] = temp
def bubble_sort(arr):
for i in range(len(arr)):
for j in range(len(arr) - 1 - i):
if arr[j] > arr[j + 1]: swap(arr, j, j + 1)
Number of comparisons: O(n^2) in all cases
$$ \sum_{i=1}^n (n-i)=\sum_{i=0}^ni=\frac{n(n-1)}{2}\in O(n^2) $$
Number of swaps:
Best Case: 0 swaps (if already sorted)
Worst Case: O(n^2) swaps (inversely sorted)
$$ \frac{n(n-1)}{2} \in O(n^2) $$
Average Case: O(n^2) swaps
$$ \frac{n(n-1)}{4} \in O(n^2) $$