Bubble Sort Algorithm: Steps, Working, and Efficiency
The bubble sort is similar to the selection sort, but more than one value is exchanged on each pass through the array. At the end of each pass, we end up with the largest value at the upper end of the array (highest array index), instead of the smallest value at the beginning as with the selection sort.
We also have a termination condition so that once the array is sorted, we can stop instead of making all the passes that would be needed with a fully unsorted array. This can be more efficient than the selection sort, which always continues to the bitter end, even if it is sorted to begin with.
This figure illustrates the steps in one pass of the bubble-sort algorithm. Starting at the left hand side of the array (lowest index), compare the first two elements. If the first is bigger than the second, exchange (swap) them. Then compare the 2nd with the third. If the 2nd is bigger than the 3rd, swap them. Continue doing this until the last two elements in the array get compared, and swapped if needed.
At the end of this iteration, the largest element in the array has “bubbled” up to the top of the array. For the 2nd pass, we do exactly the same thing, but ignore the last element. For the 3rd pass, we’ll ignore the last two elements, etc.
After completing all the passes, the array will be sorted. One advantage to the bubble-sort is the ability to check and see if any swaps are made during any specific pass. If we make a pass through the array, and don’t have to make any swaps, that means that the array is sorted, and we can quit. Thus, if the array is sorted to begin with, one pass of the bubble-sort will be made, no swaps will happen, and we will know to quit.
This is much more efficient than the selection sort, where all of it’s passes will be made, no matter the original state of the array. So in the best case (array already sorted), bubble sort is much more efficient than selection sort. In the worst case (array anti-sorted), both algorithms are approximately N2 and cost about the same.
Dear Aspirants,
Your preparation for GATE, ESE, PSUs, and AE/JE is now smarter than ever — thanks to the MADE EASY YouTube channel.
This is not just a channel, but a complete strategy for success, where you get toppers strategies, PYQ–GTQ discussions, current affairs updates, and important job-related information, all delivered by the country’s best teachers and industry experts.
If you also want to stay one step ahead in the race to success, subscribe to MADE EASY on YouTube and stay connected with us on social media.
MADE EASY — where preparation happens with confidence.
MADE EASY is a well-organized institute, complete in all aspects, and provides quality guidance for both written and personality tests. MADE EASY has produced top-ranked students in ESE, GATE, and various public sector exams. The publishing team regularly writes exam-related blogs based on conversations with the faculty, helping students prepare effectively for their exams.
