Anonymous user
Sorting algorithms/Bubble sort: Difference between revisions
→Algorithm: optimize noting that each pass finds the maximum item
(→{{header|C}}: small change to significantly reduce the number of comparisons required (avg 72 to max 45)) |
(→Algorithm: optimize noting that each pass finds the maximum item) |
||
Line 8:
The '''bubble sort''' is generally considered to be the simplest sorting algorithm. Because of its simplicity and ease of visualization, it is often taught in introductory computer science courses. Because of its abysmal performance, it is never used anywhere else.
The bubble sort works by passing sequentially over a list, comparing each value to the one immediately after it. If the first value is greater than the second, their positions are switched. Over a number of passes, at most equal to the number of elements in the list, all of the values drift into their correct positions. Because each pass finds the maximum item and puts it at the end, the portion of the list to be searched can be reduced at each pass. (Large values "bubble" rapidly toward the end, pushing others down around them.) A boolean variable is used to track whether any changes have been made in the current pass; when a pass completes without changing anything, the algorithm exits.
This can be expressed in pseudocode as follows (assuming 1-based indexing):
repeat
set hasChanged to false
repeat with index from 1 to itemCount
if (item at index) > (item at (index + 1))
swap (item at index) with (item at (index + 1))
set hasChanged to true
=Examples=
| |||