DSA#6 Bubble sort algorithm
The Bubble sort algorithm is the most straightforward sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.
Javascript implementation
Explanation:
The function receives two parameters, the array we have to sort and its length. The second parameter isn’t mandatory in case you use a language in which you can easily calculate the length of an array.
The first loop is for the array traversal since we have to compare each element of the array with all elements that are left, we have a nested loop. The condition l -1 -i can be avoided and used only linstead but it helps you to optimize the algorithm because it's unuseful to compare the element with they are already sorted.
In the second loop, we have a condition that compares if the adjacent elements are in the wrong order (if you are sorting in ascendent the left element should be less than the right and vice versa for a descendent sorting), if so they are swapped. This process is repeated until we reach the end of the array.
In line 2, there is a variable called flag. flaghelps us also to optimize the algorithm, for each lap in the first loop, flagis reset to false, and if we find elements that are in the wrong order flagis set to true. This approach helps us to know if it is useful to continue our traversal because if for one lap we don’t find any elements in the wrong order we can assume that the array is sorted.
Illustration:
Let’s me explain with illustrations:
We have to sort this array in ascendent:
The first pass:
8 is the first element, so we have to compare it with all the elements that are left. Each time 8 is greater than the element after it they are swapped and so on. We use the bubble sort algorithm, On the first pass, the highest value (or lowest, depending on the sort order) is moved to the top of the list, here 8 is at the top of the list.
The second pass:
The same process continues for the second lap and 7 will never be compared with 8 because 8 is already sorted and this condition l -1 -i in the nested loop avoids making unuseful comparisons.
Third pass:
Fourth pass:
Complexity analysis: The bubble sort has a time complexity of O(n²) because the algorithm uses two nested loops and since it doesn’t use any extra space the space complexity is O(1).
Conclusion:
We are at the end of our post, we can summarize that bubble sort is an algorithm that can help to sort an array in ascendent or descendent order, since its time complexity is O(n²), it common to use it when complexity does not matter or when short and simple code is preferred. I hope that you learn something new by reading this article.
The Nothing 🔺
