Bubble Sorting
The most basic sorting algorithm, bubble sort, continuously switches nearby elements that are out of order. It compares two neighboring elements and switches them until they are in the right order using its two pointers. Due to its high average and worst-case time complexity, this approach is not appropriate for huge data sets.
Working of Bubble sorting Algorithm
Assume that the elements will be arranged in ascending order:
1. Initial Iteration (Swap and Compare)
- We begin with the first component. Compare the first and second elements since Bubble Sort has two pointers.
- Switch them if the second element is greater than the first.
- Next, compare the second and third elements, and if they are out of order, switch them.
- Proceed until you reach the final component.
- Lock the last piece once the first iteration is complete. assuming that the final component is the biggest. Thus, the subsequent iteration does not include that piece.
2. The Second Iteration
- The subsequent iteration follows the same procedure as the initial one.
- The final element will be locked in the final location after one repetition. Until the element to be iterated runs out, the iteration will continue. There will be instances where the components are already sorted but the iteration is not yet complete.
- The array is already sorted at the second iteration, but the bubble sort algorithm is unaware of this. Instead, in order to determine if the list is sorted, it must go through the full list without changing any values.
Example of Bubble Sorting Algorithm
- The Bubble Sort algorithm would begin by comparing the first two numbers in a list like this: 5, 3, 8, 4, 2.
- The two numbers would be switched because 5 is bigger than 3.
- 3, 5, 8, 4, 2 would be the new order of the list.
- Until the entire list is in order, the program would keep comparing neighboring pairings and switching them if needed.
Bubble Sort algorithm Time Complexity
Best Case Bubble Sort Time Complexity
O(N) When the array is already sorted, it is the best situation. A total of N-1 comparisons and 0 swaps are therefore needed. Therefore, O(N) is the best case complexity.
Bubble Sort's Worst Case Time Complexity
O(N2) The array's elements being placed in decreasing order is the worst-case scenario for bubble sort. In the worst scenario, sorting a given array will require a total of (N-1) passes or iterations. where "N" is the array's total number of elements.
Advantages of Bubble sorting Algorithm
- Bubble sort is simple to comprehend and use.
- No more memory space is needed for it.
- Because it is a stable sorting algorithm, the sorted output retains the relative order of elements with the same key value.
Disadvantages of Bubble sorting Algorithm
- Bubble sort is extremely slow for large data sets due to its O(n2) time complexity.
- As a comparison-based sorting algorithm, bubble sort depends on a comparison operator to ascertain the relative order of the input data set's elements.
- In some situations, it may restrict the algorithm's efficiency.
