Sorting algorithms are used to arrange data in a specific order to make it more manageable and easily searchable. There are several sorting algorithms available, and one of the simplest and most common is bubble sort.
How it Works
it works by comparing adjacent elements in an array or list and swapping them if they are in the wrong order. The process is repeated until the list is sorted.
- Starting from the first element, compare the first two elements. If the first element is greater than the second element, swap them.
- Move to the next pair of adjacent elements and repeat step one until you reach the end of the list.
- Repeat steps one and two for each element in the list until the list is sorted.
For example, let’s say we have the following list: [5, 3, 8, 4, 2].
- Compare 5 and 3, swap them -> [3, 5, 8, 4, 2]
- Compare 5 and 8, do not swap -> [3, 5, 8, 4, 2]
- Compare 8 and 4, swap them -> [3, 5, 4, 8, 2]
- Compare 8 and 2, swap them -> [3, 5, 4, 2, 8]
The first iteration is complete, and the largest element (8) is in its correct position. We can continue with the second iteration:
- Compare 3 and 5, do not swap -> [3, 5, 4, 2, 8]
- Compare 5 and 4, swap them -> [3, 4, 5, 2, 8]
- Compare 5 and 2, swap them -> [3, 4, 2, 5, 8]
The second iteration is complete, and the second largest element (5) is in its correct position. We can continue with the third iteration:
- Compare 3 and 4, do not swap -> [3, 4, 2, 5, 8]
- Compare 4 and 2, swap them -> [3, 2, 4, 5, 8]
The third iteration is complete, and the third largest element (4) is in its correct position. We can continue with the fourth iteration:
- Compare 3 and 2, swap them -> [2, 3, 4, 5, 8]
The list is now sorted.
Time Complexity of Bubble Sort
Time complexity is the amount of time it takes for an algorithm to complete based on the size of the input data. The time complexity of bubble sort is O(n^2) in the worst case and O(n) in the best case. This means that the time taken by bubble sort to complete increases exponentially as the input size increases.
- Worst case: T(n) = n * (n – 1) / 2 = O(n^2)
- Best case: T(n) = n – 1 = O(n)
Space Complexity of Bubble Sort
Space complexity is the amount of memory an algorithm uses based on the size of the input data. The space complexity of bubble sort is O(1) because it only requires a constant amount of memory to swap two elements.
Improvements to Bubble Sort
- Short bubble sort: This variation of bubble sort stops iterating through the list once no swaps are made, which can significantly reduce the number of iterations required.
- Comb sort: This algorithm is similar to bubble sort but uses a different method to compare and swap elements, which can make it more efficient.
- Cocktail shaker sort: This algorithm is similar to bubble sort but iterates through the list in both directions, which can make it more efficient in some cases.
Conclusion
it is a simple and easy-to-understand sorting algorithm that can be useful for small datasets or for educational purposes. However, it is not efficient for large datasets and is generally not used in real-world applications.
Follow Us on
https://www.linkedin.com/company/scribblers-den/
https://www.facebook.com/scribblersden.blogs
Read More
https://scribblersden.com/samsung-galaxy-s23-5g/
Thank You
