This exercise will introduce you to sorting and specifically Bubble Sort. There are several methods for sorting and bubble sort is one of them.
Note: If you stumbled upon this post and are wondering what this is about, start here.
Bubble Sort makes multiple passes through the list, while comparing adjacent elements. It compares adjacent elements and swaps them if they are out of order.
Here is how it works:
Input list = [23, 4, 55, 12, 76, 3,41]
First pass:
[4,23,55,12,76,3,41] - Swap
[4,23,55,12,76,3,41] - No swap
[4,23,12,55,76,3,41] - Swap
[4,23,12,55,76,3,41] - No swap
[4,23,12,55,3,76,41] - Swap
[4,23,12,55,3,41,76] - Swap
Note that at the end of the first pass, the largest number is in its final place. It has 'bubbled' up to its final location.
For the second pass, we can ignore the last element and sort the rest. At the end of the second pass, the penultimate item will be in its final position. This way, we keep shrinking the list until there is nothing else to sort.
Here is the usecase:
- Program displays a list of randomly ordered integers
- Program sorts the list using bubble sort
- Program displays the sorted list
Programming constructs used:
- Comparison
- Looping
- Conditional statements
Here is what the output would look like:
Note that I am printing the list at the end of each pass, but you don't need to do that.
You will also note that the sorting algorithm continues with the passes even though there is nothing to sort after the 6th pass. This is because the algorithm is blindly running through the list once for every item in the list.
Bonus:
Improve the algorithm in such a way that it stops soon after the list is completely sorted. The output should look like this:
Happy coding!
Note: If you stumbled upon this post and are wondering what this is about, start here.
Bubble Sort makes multiple passes through the list, while comparing adjacent elements. It compares adjacent elements and swaps them if they are out of order.
Here is how it works:
Input list = [23, 4, 55, 12, 76, 3,41]
First pass:
[4,23,55,12,76,3,41] - Swap
[4,23,55,12,76,3,41] - No swap
[4,23,12,55,76,3,41] - Swap
[4,23,12,55,76,3,41] - No swap
[4,23,12,55,3,76,41] - Swap
[4,23,12,55,3,41,76] - Swap
Note that at the end of the first pass, the largest number is in its final place. It has 'bubbled' up to its final location.
For the second pass, we can ignore the last element and sort the rest. At the end of the second pass, the penultimate item will be in its final position. This way, we keep shrinking the list until there is nothing else to sort.
Here is the usecase:
- Program displays a list of randomly ordered integers
- Program sorts the list using bubble sort
- Program displays the sorted list
Programming constructs used:
- Comparison
- Looping
- Conditional statements
Here is what the output would look like:
Note that I am printing the list at the end of each pass, but you don't need to do that.
You will also note that the sorting algorithm continues with the passes even though there is nothing to sort after the 6th pass. This is because the algorithm is blindly running through the list once for every item in the list.
Bonus:
Improve the algorithm in such a way that it stops soon after the list is completely sorted. The output should look like this:
Happy coding!