Bubble Sort
- Bubble sort is an algorithm that compares the adjacent elements and swaps their positions if they are not in the intended order.
- A list with n elements requires n-1 passes for sorting
- The order can be ascending or descending.
- It is known as bubble sort, because with every complete iteration the largest element in the given array, bubbles up towards the last place or the highest index, just like a water bubble rises up to the water surface.
Algorithm: Following are the steps involved in bubble sort(for sorting a given array in ascending order):
- Starting with the first element(index = 0), compare the current element with the next element of the array.
- If the current element is greater than the next element of the array, swap them.
- If the current element is less than the next element, move to the next element. Repeat Step 1.
Bubble sort starts with very first two elements, comparing them to check which one is greater.
In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we compare 33 with 27.
We find that 27 is smaller than 33 and these two values must be swapped.
The new array should look like this −
Next we compare 33 and 35. We find that both are in already sorted positions.
To be precise, we are now showing how an array should look like after each iteration. After the second iteration, it should look like this −
Advantages:
Easy to understand.
Easy to implement.
In-place, no external memory is needed.
Performs greatly when the array is almost sorted.
Disadvantages
Very expensive, O(n2)in worst case and average case.
The main disadvantage of the bubble sort is the fact that it does not deal well with a list containing a huge number of items.
No comments