Sorting Algorithms: Bubble Sort
Sorting Algorithms: Bubble Sort
So you're in the market for a good sorting algorithm, huh? If you love making comparisons and don't mind waiting around for the answer, BubbleSort's a great option.
The algorithm looks like this:
BUBBLESORT(List L): LET n equal the length of L: FOR i from 0 to n: FOR j from 0 to n – i: IF L[j] > L[j + 1]: SWAP L[j] and L[j + 1]
Whoa, wait, where are you going? Come back: we'll show you what it means.
Take the following list, where the first row tells the index and the second row tells the value:
0 | 1 | 2 | 3 | 4 |
5 | 4 | 7 | 2 | 1 |
The sort starts by looking at the first two numbers. If the one on the left is bigger than the one on the right (spoiler alert: it is), then they swap places:
![The first two indices, 5 and 4, are highlighted.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms1.png)
Then it moves one place to the right, and compares index 1 with index 2.
![Now indices 1 and 2 are highlighted (which are values 5 and 7).](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms2.png)
Since 5 is less than 7, nothing happens. Now it compares index 2 with index 3.
![Indices 2 and 3 are highlighted, which are 7 and 2.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms3.png)
You know the deal. 2 is less than seven, so:
![Indices 3 and 4 are highlighted with the values 7 and 1.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms4.png)
The result?
![A marginally more sorted list with the greatest value at the end.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms5.png)
An unsorted list. But we've found the largest number in the list and moved it to the end.
#NotAsUnsortedAsItCouldBe
If we continue this for another round, the list looks like this:
![A list with Index 4 and the value 7 in it greyed out.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms6.png)
Which means we've found the second largest element. See what we did there?
![Now index 3 is also greyed out with the value 5.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms7.png)
Every time we go through the list, we find the next largest element, so that by the time we've made 4 – 1 rounds of comparisons, the list is sorted.
![Now index 2 is greyed out with the value 4.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms8.png)
Every round of sorting makes the next largest element "bubble" to the end. It's almost like they named the sort with that metaphor in mind.
Because we have two nested for loops, this sort takes O(n2) time, making it less-than-efficient in sorting terms. It isn't bad, but we can do better. That might not matter for a list of size five, but if we have a list of size 1,000 it's huge. There really isn't any reason to use Bubble Sort except for the fact that bubbles are awesome.