Table of Contents
About Bubble Sort
Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted. It compares each pair of adjacent items and swaps them to be in the correct order.
Also known for its inefficiency and time complexity of O(n^2).
Bubble sort algorithm
Let's sort an array of numbers(integers) [5, 1, 4, 3].
To make the algorithm easier to explain, let's visualize the array where the height represents the value.
The algorithm involves looping and comparing two values. For example, in a 4-value array, we would loop a maximum of 3 times, as we compare j and j+1.
In our example (the script is below):
$i = value of outer loop
$j = value of inner loop
$a[$j] = value of an array at the position of $j
$a[$j+1] = value of an array at the position of $j+1
Comparison #1
We start at the beginning of the array and compare the first two elements, 5 and 1(before). Since 5 is greater than 1, we swap them(after).
Comparison #2
We increment the value of j in the loop and compare the next two elements, 5 and 4(before). Since 5 is greater than 4, we swap them(after).
Comparison #3
We increment the value of j in the loop and compare the next two elements, 5 and 3(before). Since 5 is greater than 3, we swap them(after).
NOTICE: It is important to note that the highest number, 5, is now in its correct sorted position and does not need to be compared again. In the next loop, we will only need to loop 2 times, as opposed to 3 times (the total number of elements in the array minus 1).
Comparison #4
Once our first loop is complete, we start again from the beginning of the array. We compare the first two elements, 1 and 4(before). Since 1 is not greater than 4, we continue in the loop without swapping them(after).
Comparison #5
We increment the value of j in the loop and compare the next two elements, 4 and 3(before). Since 4 is greater than 3, we swap them. We skip the number 5, as it is already in its sorted position(after).
Number 5 is already sorted so we skip it.
Comparison #6
In our last loop, we compare the first two elements, 1 and 3(before). Since 1 is not greater than 3, we continue in the loop without swapping them(after).
The final array looks like this(after): [1, 3, 4, 5].
Function
The loops
To compare two values in an array, we need a loop within a loop.
Instead of looping in the traditional way:
for ($i = 0; $i < count($a) - 1; $i++) { // outer loop
for ($j = $i + 1; $j < count($a); $j++) { // inner loop
// ...
}
}
we do it in the opposite direction, where we decrement in the outer loop, so we can skip the last sorted number.
for ($i = count($a) - 1; $i > 0; $i--) { // outer loop
for ($j = 0; $j < $i; $j++) { // inner loop
// ...
}
}
Swap
In the loop we check the two values and swap if $a[$j] > $a[$j + 1].
if ($a[$j] > $a[$j + 1]) {
$temp = $a[$j];
$a[$j] = $a[$j+1];
$a[$j+1] = $temp;
}
Bubble Sort Algorithm
function bubbleSort(array $a): array
{
for ($i = count($a) - 1; $i > 0; $i--) {
for ($j = 0; $j < $i; $j++) {
if ($a[$j] > $a[$j + 1]) {
$temp = $a[$j];
$a[$j] = $a[$j+1];
$a[$j+1] = $temp;
}
}
}
return $a;
}
// $bs = [5, 2, 8, 9, 1];
// bubbleSort($bs);
// [1, 2, 5, 8, 9]
Optimized version
But what if we have a situation where an array(on the left) is almost sorted and after an outer loop is finished we have all items sorted.
If we used the script above, we would have 15 comparisons for an array [6, 1, 2, 3, 4, 5]. However, it is clear that after the first loop, all numbers are sorted, meaning we do not have to loop through [1, 2, 3, 4, 5, 6] several more times.
We can optimize this by tracking whether any swaps were made during the outer loop. If there were no swaps, we can break the loop and return the array, as it is now sorted.
So we loop once more and if there is no swap, we can break the loop and return the array, because all is sorted.
Explanation:
- Let's define a variable
$swapwithin the outer loop. - We set
$swapto true if there is a swap in the condition. - If there is no swap in the outer loop, we don't need to check the rest, so we break the loop and return the sorted array.
The following optimization has only 9 comparisons for an array [6, 1, 2, 3, 4, 5]. It skips the loops where $i = 3, 2, and 1.
function bubbleSortOptimized(array $a): array
{
for ($i = count($a) - 1; $i > 0; $i--) {
$swap = false;
for ($j = 0; $j < $i; $j++) {
if ($a[$j] > $a[$j + 1]) {
$temp = $a[$j];
$a[$j] = $a[$j+1];
$a[$j+1] = $temp;
$swap = true;
}
}
if (!$swap) break;
}
return $a;
}
// $bs = [6, 1, 2, 3, 4, 5];
// bubbleSortOptimized($bs);
// [1, 2, 3, 4, 5, 6]
Scripts
Both scripts can be found here: https://gist.github.com/matusstafura/7b049a323624a99a9f0120492888621e
Time Complexity
The time complexity of bubble sort is O(n^2) in the worst and average cases, and O(n) in the best case (when the input is already sorted).
Top comments (0)