Editing Sorting algorithm (section)

=== Bubble sort and variants ===
Bubble sort, and variants such as the [[Comb sort]] and [[cocktail sort]], are simple, highly inefficient sorting algorithms. They are frequently seen in introductory texts due to ease of analysis, but they are rarely used in practice.

==== Bubble sort ====
[[File:Bubblesort-edited-color.svg|thumb|right|A bubble sort, a sorting algorithm that continuously steps through a list, [[Swap (computer science)|swapping]] items until they appear in the correct order.]]
{{Main|Bubble sort}}

''Bubble sort'' is a simple sorting algorithm. The algorithm starts at the beginning of the data set. It compares the first two elements, and if the first is greater than the second, it swaps them. It continues doing this for each pair of adjacent elements to the end of the data set. It then starts again with the first two elements, repeating until no swaps have occurred on the last pass.<ref>{{harvnb|Wirth|1986|pp=81–82}}</ref> This algorithm's average time and worst-case performance is O(''n''<sup>2</sup>), so it is rarely used to sort large, unordered data sets. Bubble sort can be used to sort a small number of items (where its asymptotic inefficiency is not a high penalty). Bubble sort can also be used efficiently on a list of any length that is nearly sorted (that is, the elements are not significantly out of place). For example, if any number of elements are out of place by only one position (e.g. 0123546789 and 1032547698), bubble sort's exchange will get them in order on the first pass, the second pass will find all elements in order, so the sort will take only 2''n'' time.

==== Comb sort ====
{{Main|Comb sort}}
''Comb sort'' is a relatively simple sorting algorithm based on [[bubble sort]] and originally designed by Włodzimierz Dobosiewicz in 1980.<ref name=BB>{{Cite journal | doi = 10.1016/S0020-0190(00)00223-4| title = Analyzing variants of Shellsort| journal = [[Inf. Process. Lett.]]| volume = 79| issue = 5| pages = 223–227
| date = 15 September 2001| last1 = Brejová | first1 = B. }}</ref> It was later rediscovered and popularized by Stephen Lacey and Richard Box with a [[Byte Magazine|''Byte'' Magazine]] article published in April 1991. The basic idea is to eliminate ''turtles'', or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously. (''Rabbits'', large values around the beginning of the list, do not pose a problem in bubble sort) It accomplishes this by initially swapping elements that are a certain distance from one another in the array, rather than only swapping elements if they are adjacent to one another, and then shrinking the chosen distance until it is operating as a normal bubble sort. Thus, if Shellsort can be thought of as a generalized version of insertion sort that swaps elements spaced a certain distance away from one another, comb sort can be thought of as the same generalization applied to bubble sort.

==== Exchange sort ====
''Exchange sort'' is sometimes confused with bubble sort, although the algorithms are in fact distinct.<ref>{{Cite web|url=https://www.codingunit.com/exchange-sort-algorithm|title=Exchange Sort Algorithm|website=CodingUnit Programming Tutorials|access-date=2021-07-10|archive-date=2021-07-10|archive-url=https://web.archive.org/web/20210710111758/https://www.codingunit.com/exchange-sort-algorithm|url-status=live}}</ref><ref>{{Cite web|url=https://mathbits.com/MathBits/Java/arrays/Exchange.htm|title=Exchange Sort|website=JavaBitsNotebook.com|access-date=2021-07-10|archive-date=2021-07-10|archive-url=https://web.archive.org/web/20210710111757/https://mathbits.com/MathBits/Java/arrays/Exchange.htm|url-status=live}}</ref> Exchange sort works by comparing the first element with all elements above it, swapping where needed, thereby guaranteeing that the first element is correct for the final sort order; it then proceeds to do the same for the second element, and so on. It lacks the advantage that bubble sort has of detecting in one pass if the list is already sorted, but it can be faster than bubble sort by a constant factor (one less pass over the data to be sorted; half as many total comparisons) in worst-case situations. Like any simple O(''n''<sup>2</sup>) sort it can be reasonably fast over very small data sets, though in general [[insertion sort]] will be faster.