Bubblesort is a simple sorting algorithm for sorting lists and arrays. Bubbble Sort has a quadratic runtime complexity. The algorithm was named Bubble Sort because the movement of the largest elements to the end of the unsorted part of the array resembles bubbles rising to the surface.
How it works
Basic idea:
The array consists of an unsorted part followed by a sorted part. At the beginning, all elements are still in the unsorted part. In each iteration, all elements of the unsorted subarray are passed through and the largest element found so far in the iteration is passed to the right until, at the end of the iteration, the last element of the unsorted subarray contains the largest element from this unsorted area.
Pseudocode:
Procedure:
At the beginning i is the index of the last element in the array. Before each iteration of the outer loop the subarray running from index 0 to index i is unsorted, the subarray from index i+1 to the end is sorted and all elements in the sorted part are at their final position. After each iteration, the largest element from the unsorted part shall have been moved to the field with index i. Since the elements behind the element with index i are not changed and the element at position i is greater than or equal to any element with a smaller index, all elements from index i on are at their final position at the end of the iteration.
The inner loop starts with the first element of the array and runs to the element before the element with index i. Before each iteration of the inner loop, the array with index j contains the largest element from the sub-array from 0 to j. If the element at position j is larger than the element at position j+1, the two elements are swapped. Thus, at the end of the iteration, the element with index j+1 contains the largest element in the range from 0 to j+1. In particular, at the end of the iteration with j = i-1, the field with index i contains the largest value of the range from index 0 to i.
Example:
Iteration 1:
As an example, the following array is to be sorted:
First i is set to the index of the last element and j starts with the first element of the array. Since the 1 is not greater than the 5, the two numbers are not swapped.
Then j is moved one field to the right and the 5 and the 2 are compared. Since 5 is larger, the two numbers must be swapped.
5 is also greater than 4, so these two numbers must be swapped as well.
After that, the 5 and the 3 still need to be swapped.
At the end of the first iteration, the last element, i.e. the 5, is at the final position.
Iteration 2:
i is moved 1 field further to the left and j starts again at 0.
Since 1 is not greater than 2, the two elements do not have to be swapped.
Likewise in the following iteration step:
The 4 and the 3 must be swapped.
At the end of the second iteration, the last two elements are in their final position.
Iteration 3:
1 is not greater than 2 and 2 is not greater than 3. Thus, nothing needs to be swapped in iteration 3 and the 3 is at the final position.
Iteration 4:
1 is not greater than 2 and therefore the 2 is already in the correct position.
Result:
There is only 1 element left to be sorted. Since a partial array with only one element is automatically sorted, the first element is also in the correct position and the entire array is sorted.
Reverse sorting order
The bubblesort algorithm can be very easily adapted to sort the elements in descending order. To achieve this, the elements must be swapped if A[j+1] is greater than A[j].