Bubble sort

Animated representation of ordination of a set of numbers through the bubble algorithm. Starting from the beginning of the arrangement, each pair of adjacent elements is compared. If both are not ordained (the second is less than the first), their positions are exchanged. In each iteration, a lesser element needs to be evaluated (the last one), since there are no more items on your right that need to be compared, since they are already sorted.

The bubble sort (Bubble Sort) is a simple sorting algorithm. It works by checking each item in the list to be sorted with the next, swapping them if they're in the wrong order. It is necessary to go through the entire list several times until no more exchanges are needed, which means the list is sorted. This algorithm gets its name from the way items move up the list during exchanges, like little "bubbles." It is also known as the direct exchange method. Since it only uses comparisons to operate elements, it is considered a comparison algorithm, being one of the simplest to implement.

Description

A simple way to express the bubble sort in pseudocode is as follows:

This algorithm performs the ordering or reordering of a list a of n values, in this case of n numbered terms of the 0 to n-1; consists of two nested loops, one with index i, which makes the bubble path smaller in reverse from 2 to n, and a second loop with index j, traversing from 0 to n-i, for each iteration of the first loop, indicating the location of the bubble

The bubble is two terms of the list followed, j and j+1, which are compared: if the first is greater than the second, their values are exchanged.

This comparison is repeated in the middle of the two loops, resulting in an ordered list. It can be seen that the number of repetitions only depends on n and not on the order of the terms, that is, if we pass an already ordered list to the algorithm, it will perform all the comparisons exactly the same as for an unordered list.. This is a feature of this algorithm. Later we will see a variant that avoids this inconvenience.

To understand how it works, let's look at a simple example:

We have a list of numbers to be ordered:

${displaystyle a={55,86,48,16,82},}$

${displaystyle {begin{array}{r}a_{4}=82a_{3=}=16a_{2}=48a_{1}=86a_{0}=55end{array}}}}}}$

We can see that the list that has five terms, then:

${displaystyle n=5,}$

Index i will traverse from 2 to n:

${displaystyle {color {Sepia}{mathit {para}}}{mathit {Black}{mathit {i}}}{;{color {BlueViolet}{mathit {gets}}{gets}}{;{Black}{mathit {2}{cH00FF}{cH00}{cH00}{cH00}{cH00}{cH00FF}{cH00FF}{cH00FF}{cH00FF}{cH00FF}{cH00FF}{cH00FF}{cH00FF}{cH00FF}{cH00FF}{cH00FF}{cH00FF}{cH00FF}{cH00FF}{cH00FF}{cH00}{cH00FF}{cH00FF}{cH00FF}{cH$

which in this case will be from 2 to 5. For each of the values of i, j will successively take on the values of 0 up to n-i:

${displaystyle {color {sepia}{mathit {para}}{mathit}{blueViolet}{mathit {Black}{blueViolet}{blueviolet}{mathit}{gets}}}{bready}{Blackit}{blue$

For each value of j, obtained in that order, the value of index j is compared with the following:

${displaystyle {color {Sepia}{mathit {si}}}{;{color {Black}a_{(j)}}}}}{color {BlueViolet}{pos(s)}{;{color {Black}a_{(j+1)}{;{color {Sepia}{mathit {thennces}}}}}}}}}}}}}}}}{$

If the j term is greater than the j+1 term, the values are swapped, otherwise the iteration continues.

${displaystyle {begin{array}{r responsible for the knowledge of whether or not) exposes aj=0 fakej=1 fakej=2 exposes a_{4}{hline a_{4}{82}{82} 82}{86}{3}{3}{16}{16}{16}{16}{16}{16}{16} 8616 age 16 age 86to 86# 86to 86# 86to 86to 86to 86# 86to 86to 86# 86# 86# 86to 86to 86# 86# 86# 86# 86# 86# 86 # 86# 86# 86# # 86# # 86# # 86# # 86# ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##$

For the case of the example, we have to:

${displaystyle n=5,}$

For the first iteration of the first loop:

${displaystyle i=2,}$

and j will take values from 0 to 3:

${displaystyle {color {Sepia}{mathit {para}}{;{color {Black}{mathit {j}}}{;{color {BlueViolet}{mathit {gets}}{gets}}{blue {Black}{blue violet}{bread}{bright}{bright}{bright}{bright}{bright}{bright}{bright}{bright}{bright}{blue }{blue }{blue }{blue$

When j Okay. 0, compared ${displaystyle a_{0};a_{1}}}$, 55 and 86, since 55 ≤ 86, the order is not permuted.

Now j Okay. 1 and compared ${displaystyle a_{1};a_{2}}}$ 86 and 48. Like 86  48, they are permuted, giving rise to a new list.

The process is repeated until j is equal to 3, resulting in a partially ordered list. We can see that the term with the highest value is in the highest place.

${displaystyle {begin{array}{r ultimate exposer hadr hadr figuredr} fakej=1 fakej=1 fakes\hline a_{4}{86} fake86 fake86a_{3}}{8}{82}{to 82 strangera_{2}{2}{2}{4}{4}{4}{to 55ray}{to 55{55}{to die}{48}{a}{48}{48}{a}{4}{4}{4}{48}{4}{a}{4}{4}{48}{4}{48}{48}{4}{48}{a}{a}{4}{a}{48}{4}{4}{48}{a}{a}{a}{48}{48}{a}{a}{48}{48}{48}{a}{a}{48}{48}{48}{48}{a}{$

Now i is equal to 3, and j will go from 0 to 2.

First j Okay. 0, compared ${displaystyle a_{0};a_{1}}}$55 and 48. As 55  48 are permuted to the new list.

For j = 1, 55 is compared with 16 and the order is changed.

For j = 2, 55 and 82 are compared and left as they are, ending the loop with a better-ordered list. It can be seen that the two highest values already take their place. No comparison has been made with the fourth term, since it is already known that after the first cycle it is the largest in the list.

The algorithm consists of successive comparisons of two consecutive terms ascending from bottom to top in each iteration, like the ascent of air bubbles in water, hence the name of the procedure. In the first iteration the path has been complete, in the second the last term has been left, as it already has the highest of the values, in the successive iterations it will stop making the last comparisons, as can be seen.

${displaystyle {begin{array}{r presumption}{r responsible for organising} absurdj=0 exposej=1 fake[hline a_{4}{4}{86}{86}{86}{86}{a_{3}{82}{a}{82}{2}{2 supposed}{555a_{1}{1}{1}{1}{1}{1}{1}{1}{to 16{to end}{to}{to}{to}{to}{to}{1}{to}{to}{4}{4}{4}{4}{to}{4}{to}{to}{to}{4}{4}{4}{4}{4}{to}{to}{to}{to}{to}{to}{4}{to}{to}{to}{to}{to}{to}{to}{to$

Now i is equal to 4 and j will cycle through the values from 0 to 1.

When j 0, compared ${displaystyle a_{0};a_{1}}}$That's 48 and 16. Since 48 is greater than 16 the values are permuted, giving rise to a somewhat more orderly list than the previous one. Since this new management, j happens to be worth 1, compared to the terms ${displaystyle a_{1};a_{2}}}$ 48 and 55 remaining in the same order.

In this case, the bubble has ascended less than in the previous cases, and the list is already sorted, but the algorithm will have to complete itself, performing one last iteration.

Keep in mind that the loop performs a fixed number of repetitions and to finish they will have to be completed, even in the extreme case, if the list was previously ordered.

Finally i 5 and j can only be worth 0, so only a comparison will be made ${displaystyle a_{0};a_{1}}}$ 16 and 48, which are already ordained and leave the same.

${displaystyle {begin{array}{r presumption}{sexorbitr}{a_{3}{3}{6}{6}{3}{3}{2}{82}{2}{2}{a_{2}{5}{a_{1}{4}{48a_{0}{0}{0}{1}{1}{1}{1}{1}{1}}}{1}{1}}{1}{1}{a}}{1}{1}}{1}}}}}{1}{1}{1}}{1}}}}}{1}}}{1}{1}}}{1}{1}{1}{1}{1}}}}}}}}}}}}}{1}}}{1}}}}}}}{4}{1}{4}}{1}{1}}{1}{4}}}{4}}{a_}}{a '$

The loops end and so does the procedure, leaving the list sorted.

A variant that terminates in case the list is ordered, could be the following: as in the previous example, using a ordered sentinel, which detects that the list has not been modified in a path of the bubble, and therefore the list is already sorted, ending immediately.

Analysis

Algorithm performance

The bubble algorithm, to sort an array of n terms, always has to perform the same number of comparisons:

${displaystyle c(n)={cfrac {n^{2}-n}{2}}{2}}}$

That is, the number of comparisons c(n) does not depend on the order of the terms, but on the number of terms:

${displaystyle Theta (c(n))=n^{2};}$

Therefore the asymptotic fitted bound of the number of comparisons belongs to the order of n squared.

The number of exchanges i(n), that must be carried out, depends on the order of the terms and we can differentiate, the best case, if the array is previously ordered, and the worst case, if the array is sorted in reverse order:

${displaystyle Theta (i(n))=?;}$

Therefore, an asymptotic fitted bound of the number of exchanges cannot be determined, since this will depend on the order of the array in question.

Worst Case Performance

If we pass the algorithm an array sorted in reverse order it will perform a number of comparisons:

${displaystyle c(n)={cfrac {n^{2}-n}{2}}{2}}}$

As we said before, and you will have to make an equal number of swaps between the terms of the array, since in each comparison the terms will be unordered, and the swap will be done.

${displaystyle i(n)={cfrac {n^{2}-n}{2}}{2}}}$

Therefore in the worst case both the number of comparisons and the number of exchanges coincide:

${displaystyle O(c(n))=O(i))=n^{2};}$

The number of worst-case comparisons or swaps is on the order of n squared.

Performance in optimal cases

In the optimal case, the most favourable, is the sorting of an already sorted array. In this case the number of comparisons will be the same as in any other case:

${displaystyle Omega (c(n)))=n^{2};}$

The asymptotic lower bound of the number of comparisons belongs to the order of n squared, as in the other cases, but in all the comparisons the order is correct and therefore no exchange is made:

${displaystyle i(n)=0;}$

Therefore the cost of exchanges does not depend on n, and is constant:

${displaystyle Omega (i(n))=1;}$

Bubble sort has a complexity Ω(n²) the same as selection sort. When a list is already sorted, unlike insertion sort which will go through the list once and find that there is no need to swap the positions of the elements, the bubble sort method is forced to go through such comparisons, which makes its complexity quadratic at best. This makes it one of the most inefficient sorting algorithms out there, although for many programmers it is the easiest to implement.

Rabbits and turtles

The position of the elements in the bubble sort plays a very important role in determining performance. Larger items at the top of the list are quickly moved to the bottom, while smaller items at the bottom of the list move to the top very slowly. This led to naming these elements rabbits and turtles, respectively.

Various efforts have been made to remove turtles and improve the speed of the bubble sort, which will be rounder than ever. Shake Sort is a good example, although it still maintains, at worst, O (n²) complexity. Combination sort compares items first in large chunks of the list, moving turtles extremely quickly, before proceeding to smaller and smaller chunks to smooth the list. Its average speed is comparable to fast (and complex) algorithms like quicksort.

In practice

Although bubble sort is one of the simpler algorithms to implement, its O (n²) order makes it very inefficient to use for lists that have more than a small number of elements. Even among O (n²) order sorting algorithms, other procedures such as insertion sort are considered more efficient.

Because of its simplicity, bubble sort is used to introduce the concept of a sort algorithm to computer science students. Despite this, some researchers such as Owen Astrachan have criticized its popularity in teaching computer science, going so far as to recommend its removal from curricula.

In addition to this, the Jargon File, a widely cited book in hacker culture, calls it "the generic bad algorithm," and Donald Knuth, one of the foremost experts in computer science, claims that bubble sort " it doesn't seem to have anything to recommend its use, except for a catchy name and the fact that it leads to interesting theoretical problems."

Bubble sort is asymptotically equivalent in runtime to insertion sort in the worst case, but both algorithms differ mainly in the number of swaps that are required. Experimental results such as those discovered by Astrachan have shown that insertion sort works considerably better even with random lists. For this reason, many modern algorithm books avoid using bubble sort, replacing it with insertion sort.

Bubble sort loosely interfaces with the hardware of modern CPUs. It requires at least twice as many writes as insertion sort, twice as many cache misses, and asymptotically more branch prediction. Several Java string sort experiments by Astrachan show that bubble sort is 5 times slower than insertion sort, and 40% slower than selection sort.

Algorithm

.

Step-by-step example

Let's take as an example the numbers: "9 6 5 8 2 1", which will be ordered from lowest to highest value using the bubble method. The following highlighted items are being compared.

First round: (9 6 5 8 2 (1) ${displaystyle to }$ (6 9 5 8 2 1), the algorithm compares the first two elements and changes them because 9 한 6 9 5 8 (2) ${displaystyle to }$ (6) 5 9 8 2 (1) (6 5 9 8 2(1) ${displaystyle to }$ (6 5) 8 9 2(1) (6 5 8 9 2 (1) ${displaystyle to }$ (6 5 8 2 9 (1) (6 5 8 2 9 1) ${displaystyle to }$ (6 5 8 2 1 9)

Round two: (6 5 8 2 1 9) ${displaystyle to }$ (5 6 8 2 1 9) (5 6 8 2 1 9) ${displaystyle to }$ (5) 6 8 2 1 9), as these elements are already in order, the algorithm does not make changes. 5 6 8 2 1 9) ${displaystyle to }$ 5 6 2 8 1 9) (5 6 2 8 1 9) ${displaystyle to }$ (5 6 2) 1 8 9) (5 6 2 1 8 9) ${displaystyle to }$ (5 6 2 1 8 9)

Round three: (5 6 2 1 8 9) ${displaystyle to }$ (5 6 2 1 8 9) (5 6 2 1 8 9) ${displaystyle to }$ (5) 2 6 1 8 9) (5 2 6 1 8 9) ${displaystyle to }$ (52) 1 6 8 9) (5 2 1 6 8 9) ${displaystyle to }$ (5 2 1 6 8 9) (5 2 1 6 8 9) ${displaystyle to }$ (5 2 1 6) 8 9)

Fourth round: (5 2 1 6 8 9) ${displaystyle to }$ (2 5 1 6 8 9) (2 5 1 6 8 9) ${displaystyle to }$ (22) 1 5 6 8 9) (2 1 5 6 8 9) ${displaystyle to }$ 2 1 5 6 8 9) (2 1 5 6 8 9) ${displaystyle to }$ (2 1 5 6 8 9) (2 1 5 6 8 9) ${displaystyle to }$ (2 1 5 6 8 9)

Fifth round: (2 1 5 6 8 9) ${displaystyle to }$ (1 2 5 6 8 9) (1 2 5 6 8 9) ${displaystyle to }$ 1 2 5 6 8 9) (1 2 5 6 8 9) ${displaystyle to }$ (1-2) 5 6 8 9) (1 2 5 6 8 9) ${displaystyle to }$ (1 2 5) 6 8 9) (1 2 5 6 8 9) ${displaystyle to }$ (1 2 5 6) 8 9)