File ExchangeSorts.h

↰ Parent directory (ADS/sort)

The sorts by exchanges of items, beyond the book, all in place:

Definition (ADS/sort/ExchangeSorts.h)

Detailed Description

  • bubbleSort(), passes from left to right that swap the adjacent items out of order, each ending at the last swap of the previous one, since the items after it are already in their places: :math:` O( n^2 ) ` comparisons, n - 1 on a sorted vector, stable;

  • cocktailShakerSort(), the bubble sort with passes alternately to the right and to the left, so that a small item near the end (a turtle) moves to the front in one pass instead of n, stable;

  • oddEvenSort(), the odd-even transposition sort: the pairs ( 2 i , 2 i + 1 ) and then the pairs ( 2 i + 1 , 2 i + 2 ) compared and swapped in turns, n rounds at most, each of independent comparisons, which is why it is a sort for n processors on a line, stable;

  • combSort(), the bubble sort with a gap that shrinks by 1.3 at each pass, which moves the turtles far, ending as a bubble sort with gap 1: not stable, near :math:` O( n log n ) ` in practice, though :math:` O( n^2 ) ` in the worst case;

  • gnomeSort(), one position that moves right while the two items behind it are in order and swaps them and moves left otherwise: the insertion sort with swaps and no nested loop, :math:` O( n^2 ) `, stable.

The contracts [see File Contract.h]: each sort ends with the same items sorted, an audit. The functions are defined in ExchangeSorts.tpp.

    1. Knuth, The Art of Computer Programming, vol. 3, 2nd ed., Addison-Wesley, 1998, section 5.2.2 (sorting by exchanging)

    1. Habermann, Parallel neighbor-sort (or the glory of the induction principle), Technical Report AD-759 248, Carnegie Mellon University, 1972

  1. Dobosiewicz, An efficient variation of bubble sort, Information Processing Letters 11(1), 5-6, 1980, doi:10.1016/0020-0190(80)90022-8

  1. Sarbazi-Azad, Stupid sort: a new sorting algorithm, Newsletter 599, Department of Computing Science, University of Glasgow, 2000

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions