Bubblesort
Bubblesort (also sorting through upgrades ) is an algorithm that sorts a list of items based comparison. This sorting algorithm works in-place, sorted stable and has a term of at worst ( worst-case ) as well as in average case ( average-case ). Thus, the running time is asymptotically optimal. In practice, bubblesort is hardly used because other methods have a better runtime behavior. However, the algorithm plays a role in teaching, as it applies to explain as simply or to demonstrate. Furthermore, the algorithm to techniques such as stepwise optimization, run-time and complexity and accuracy analysis is introduced.
- 5.1 hares and tortoises
Principle
In the bubble phase, the input list is traversed from left to right. In this case, in each step the current element with the right neighbor is compared. If the two elements violate the sorting criteria, they will be replaced. At the end of the phase is the largest or smallest element of the input end of the list in ascending or descending order on.
The bubble phase is repeated until the input list is completely sorted. In this case, the last element of the previous run must no longer be regarded as the residual to be sorted input does not contain larger or smaller elements more.
Depending on whether is sorted in ascending or descending, ( hence the name ) grow larger or smaller items such as bubbles in the water ever upward, that is, at the end of the list. Also, two numbers are always interchanged in "Bubbles".
Algorithm
In order not to complicate the synthetic representation of the algorithm as a comparative ratio is used ( larger than ) below. Like in any other comparison-based sorting process may be replaced by another relation that defines a total order.
The algorithm in its simplest form as a pseudo-code:
Bubblesort (array A) for ( n = A.SIZE, n > 1, n = n-1) { for (i = 0; i < n-1, i = i 1 ) { if ( A [i] > A [i 1 ]) { A.swap (i, i 1) } / / End if } / / End inner for loop } / / End outer for loop The entry is stored in an array. The outer loop gradually decreased the right boundary of the bubble phase, since after each Bubblen the largest element of each unsorted input is at the rightmost position. In the inner loop of the not yet sorted part of the array is traversed. Two adjacent data are swapped (ie the sorting criterion hurt ) if they are in the wrong order.
However, this simplest version does not utilize the property that after an iteration in which took place no interchanges take place no more substitutions in the remaining iterations. The following pseudo code takes this into account:
BubbleSort2 (Array A) n = A.SIZE do { swapped = false for (i = 0; i < n-1, i) { if ( A [i] > A [i 1 ]) { A.swap (i, i 1) swapped = true } / / End if } / / End for n = n -1 } While ( swapped == true) The outer loop iterates through the data to be sorted, until no more permutations are required.
A further optimization is to exploit the property that at the end of an outer iteration already have all elements to the right of the last exchange position to its final position:
BubbleSort3 (Array A) n = A.SIZE do { NEWN = 1 for (i = 0; i < n-1, i) { if ( A [i] > A [i 1 ]) { A.swap (i, i 1) NEWN = i 1 } / / End if } / / End for n = NEWN } While ( n> 1) example
A series of five numbers to be sorted in ascending order.
The bold numbers are compared in each case. If the left larger than the right, both are reversed; the pair of numbers is then highlighted in blue. In the first pass, the largest number thus moves to the extreme right. The second pass thus takes the last and penultimate position can not be compared. → Third Pass: no compare last / penultimate / antepenultimate ....
55 07 78 12 42 1st run 07 55 78 12 42 07 55 78 12 42 07 55 12 78 42 Last comparison 07 55 12 42 78 2nd Pass 07 55 12 42 78 07 12 55 42 78 Last comparison 07 12 42 55 78 3 Pass 07 12 42 55 78 Last comparison 07 12 42 55 78 4 Pass Last comparison 07 12 42 55 78 Finish sorted.
Complexity
Worst case
Bubblesort has requested the Runtime for lists of length. In the case of reversed sorted list (n, n- 1, ..., 2,1) be a maximum of many permutations performed: for the first (and largest ) element to move to the far right, exchanges are made. General: The movement of the th element of the site is carried out by permutations. Summing over all permutations gives a whole. Since only pairs are interchanged, the comparison was made before, the algorithm also requires at least the same number of comparisons. Looking at the pseudo code of the algorithm, one is easy to see that none of the instructions can be executed more than once, so this is the best possible lower bound.
Best case
If the list is already sorted, Bubblesort will go through the list only once to determine that the list is already sorted, because no adjacent elements had to be reversed. Therefore Bubblesort required steps to edit an already sorted list.
If the elements of the list are already close to the places that they should get after sorting, the running time is significantly better than.
Average case
The expected number of comparisons for a random permutation of the list ( 1,2, ..., n)
,
The Euler - Mascheroni constant referred to; is the expected number of permutations.
Demarcation
Even if Bubblesort is not asymptotically optimal, an insert for small inputs can come into question because dominate for small the constant maturity factors of a sorting algorithm, which are small in Bubblesort. A use case is for example the use of Bubblesort in a base case of a recursive working sorting process.
If the input is to be sorted ( up to a certain length) has sorted with a high probability to Bubblesort is, since this is the best case, in which the algorithm is a linear term. In contrast, other efficient sorting algorithms, such as Quicksort, or asymptotically optimal method, such as mergesort, a best-case of.
In these aspects Bubblesort competes with insertion sort, whose best-case is also already sorted input and the same complexity as Bubblesort has (as well as in average and worst- case). In addition, insertion site, as well as bubblesort, stable and works well in-place. Depending on the implementation of insertion has a lower constant maturity factors as bubblesort.
Hare and tortoise
The positions of the elements before sorting decisive factors in the sort of effort Bubblesort. Large elements at the beginning affect not serious, since they are quickly swapped back, but small elements at the end move rather slowly forward. Therefore, these elements are also referred to as rabbit or turtles.
Cocktailsort bubbelt alternating elements of the left and the right side, that is, the local bubble phase avoids the problem of forward slowly migrating elements. Because of the alternation used this algorithm is also called Bidirectional Bubblesort. In the worst case is its duration, like those of bubblesort, in.
Combsort is related to Bubblesort. How Bubblesort compares and he exchanged elements, but unlike bubblesort also widely spaced elements, to avoid slowly migrating elements, compared and exchanged. His life is also in the worst case. In the best case it is in ( Bubblesort: ). Thus, the worst- and best-case of quicksort Combsort and have the same complexity.