This tutorial explains Bubble Sort algorithm with an example showing multiple iterations of the algorithm. It then shows how to implement bubble sort in Java and explains the code.
What is Bubble Sort: Bubble Sort, considered by many to be the simplest of sorts, works by progressively in-place sorting(ie. not using up extra space while sorting) a list of items by moving the lowest valued item to the to the top or largest valued item to the bottom(for an ascending sort). It keeps lining bigger and bigger elements below the earlier smaller ones. In this way the whole array gets sorted.
You can see a whiteboard animation video explanation of how bubble sort works and get a code walk-through in this YouTube video
Bubble Sort’s working in detail -Lets say our list to be sorted is [1000, 1, 100, 101, 15].As per bubble sort, we will move progressively the largest valued items to the bottom/end of the list.
First Pass of Bubble Sort Algorithm
Lets start with the first pass from left to right in the list [1000, 1, 100, 101, 15]. The various comparisons that happen in the first pass are –
- 1000 is compared to 1. As 1000>1 it is swapped. The list is now [1,1000,100,101,15].
- 1000 is now compared with 100. As 1000 > 100 the two items are swapped. The list now is [1,100,1000,101,15]
- 1000 is now compared with 101. As 1000 > 101 they are swapped. The list now is [1,100,101,1000,15]
- 1000 is now compared wiuth 15. As 1000>15 they are swapped. The list now is [1,100,101,15,1000]
The first pass is now complete. Note that the largest element in the list(1000) has bubbled to the rightmost and correct place. List at the end of the first pass is [1,100,101,15,1000].
We again start from left and move to the right –
- 1 is compared with 100. As 1 < 100 nothing is done. List remains [1,100,101,15,1000]
- 100 is now compared with 101. As 100 < 101 nothing is done. List remains the same.
- 101 is now compared with 15. As 101 > 15 they are swapped. The list now is [1,100,15,101,1000].
The second pass ends at this point as the last element(1000) was already marked as greatest in the first pass. The second-last element(101) is the second largest at the end of the second pass now. List at the end of the second pass is [1,100,15,101,1000].
Similar to the first and second pass, passes keep bubbling up largest elements to the right while the size of the unsorted list keeps reducing.
After exactly n-1 passes the list is considered to be sorted as all the elements are now in their correct position.
doSort()method in the above java program holds the sorting logic.
- There are 2 loops. The loop with the counter
outerrepresents the passes and continues for 0 to length – 1 times. ie. 1 less than the number of items times.
- The loop with the counter
innerrepresents the sorted element being moved/bubbled forward. It continues from
length-outer-1times. This is because the size of the unsorted part of the array keeps reducing in exact correlation with the number of passes completed i.e number of elements sorted and put in their correct place.
main()method orchestrates the sorting.
- The instance element
intArrayholds the list to be sorted.