File Rearrangements.h

↰ Parent directory (ADS/sequence)

Rearrangements of a vector in place, by swaps or with a small buffer: the partition into three classes, the alternating order, the sort of a vector whose items are near their places, and the cost of sorting by swaps.

Definition (ADS/sequence/Rearrangements.h)

Detailed Description

  • dutchNationalFlag(): the items of colour 0, then those of colour 1, then those of colour 2, by Dijkstra’s invariant A[ 0 .. i ) of colour 0, A[ i .. j ) of colour 1, A[ j .. k ] not examined, A( k .. n ) of colour 2: each step examines A[ j ] and swaps it to its class, n colours read and at most n swaps, O( 1 ) space. It is the partition of quicksort with three ways, the keys smaller than, equal to and larger than the pivot [see File EngineeredQuickSorts.h for the partition of Bentley and McIlroy, which moves the equal keys fewer times];

  • wiggleSort(): A[ 0 ] <= A[ 1 ] >= A[ 2 ] <= A[ 3 ] >= …, by a pass of swaps of neighbours: when A[ 0 .. i ] alternates, a swap of A[ i ] and A[ i + 1 ] when they are in the wrong order keeps the order with A[ i - 1 ] by transitivity; n - 1 comparisons. With distinct items the order is strict; the strict order with repeated items, when it exists, needs the median and a partition into three ways about it, still in :math:` O( n ) ` time;

  • sortKSorted(): the sort of a vector each of whose items is at most k places away from its place in the sorted order: the item of the place i is the smallest of A[ i .. i + k ], hence a heap of k + 1 items gives each item in turn, :math:` O( n log k ) ` time and :math:` O( k ) ` space, against the :math:` O( n k ) ` of insertion sort [see File InsertionSort.h]; :math:` Omega( n log k ) ` comparisons are needed, since about :math:` ( k! )^{n / k} ` orders are k-sorted;

  • minimumSwapSort(): the sort of distinct items by swaps, the fewest swaps and the least total cost when a swap costs the sum of the two items swapped. Each cycle of the permutation that sorts A, of k > 1 items, needs k - 1 swaps, hence n minus the number of cycles in all; its items, of sum s and minimum m, are sorted at the least cost :math:` min( s + ( k - 2 ) m , s + m + ( k + 1 ) M ) , M the minimum of A: the minimum of the cycle swapped with each of the others in turn, or M brought into the cycle by a swap with m, used in the same way, and swapped back. The two optima may come from different sequences of swaps; :math: O( n log n ) ` for the sort that gives the permutation.

The contracts [see File Contract.h]: the colours must be 0, 1 or 2, and come out in order (an audit); wiggleSort() and sortKSorted() give a permutation of the items (an audit) alternating and sorted; sortKSorted() needs a vector k-sorted and minimumSwapSort() distinct items, audits. The functions are defined in Rearrangements.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, Esercizi Divide-et-impera, Raccolte da compiti scritti, and the collection of exercises on the analysis of algorithms

    1. Dijkstra, A Discipline of Programming, Prentice-Hall, 1976, chapter 14

    1. Knuth, The Art of Computer Programming, vol. 1, 3rd ed., Addison-Wesley, 1997, section 1.3.3

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions