Bubble sort: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
Bubble sort is the simplest exchange sorting algorithm. | Bubble sort is the simplest exchange sorting algorithm. | ||
Each element of the array is compared | Each element of the array is compared with its subsequent element of the array and swapped if bigger until the end of the array. As after the first pass, the maximum element of the array is in the end, the comparison process can stop one element before the end of the array. | ||
The worst-case and average complexity is O(n<sup>2</sup>). | The worst-case and average complexity is O(n<sup>2</sup>). | ||
Latest revision as of 02:38, 4 June 2018
Bubble sort is the simplest exchange sorting algorithm.
Each element of the array is compared with its subsequent element of the array and swapped if bigger until the end of the array. As after the first pass, the maximum element of the array is in the end, the comparison process can stop one element before the end of the array.
The worst-case and average complexity is O(n2).
This algorithm should only be used on almost sorted array (that implies few permutations).
This algorithm has one advantage in its ability to tell if an array is already sorted in O(n).
Resources
| https://en.wikipedia.org/wiki/Bubble_sort |