Two-way bubble ordering

The bidirectional bubble sort is an ordering algorithm that comes up as an enhancement to the bubble sorting algorithm.

The way to work of this algorithm is to be ordering at the same time by the two ends of the vector. So that after the first iteration, both the smallest and the largest element will be in their final positions. In this way the number of comparisons is reduced although the complexity of the algorithm remains O (n²).

We make an ascending route (from the first element to the last), we take the first element and compare it with the next one, if the next one is smaller we move it to the previous position, so at the end of the list we have the largest. Once the ascending series is finished, we make a descending route (from the last element to the first) but this time we stay with the minors to which we are advancing positions instead of delaying them as we did in the ascending series. Repeat the series alternately but reducing the scope at its ends because we will have there the lowest and highest values ​​in the list, until there are no elements in the series; in the example pseudocode: To (left & right).

The algorithm pseudo-code is shown below: Procedure Saturation Order (v: vector, size: integer) Variables i, j, izq, der, last: tipoposicion; to: tipoelemento; Start // Upper and lower boundaries of ordered elements izq <- 2 the & lt; -tam last & lt; - tam Repeat // Bubble to the left} // Minor values ​​go left // der decreases by 1 until you reach left To go all the way to the left Si v (i-1) & gt; v (i) entonces to & lt; - v (i) v(i) <- v(i-1) v (i-1) & lt; - to last <- i End_si End_to left & lt; - last + 1 // Bubble to the right // Major values ​​go to the right For j & lt; - left to do If v (j-1) & gt; v (j) entonces to & lt; - v (j) v(j) <- v(j-1) v (j-1) & lt; - to last <- j End_si End_to der <- last-1 Hasta (izq & gt; the) End

wiki