File SelectionSort.h

↰ Parent directory (ADS/sort)

Selection Sort (section 2.7.1): the minimum of the part still to sort A[ i .

Definition (ADS/sort/SelectionSort.h)

• Program Listing for File SelectionSort.h

Detailed Description

. n - 1 ] is swapped with A[ i ], extending the sorted prefix; :math:` sum_{i=0}^{n-2} ( n - i - 1 ) = n ( n - 1 ) / 2 ` comparisons whatever the order of the input, :math:` Theta( n^2 ) ` time, O( 1 ) space, not stable.

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

1. Montresor, Algoritmi e Strutture Dati, 2025, section 2.7.1, https://algoritmicamente.it/materiali/libro/capitoli/cap02.pdf

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

• ADS/Contract.h (File Contract.h)

• ADS/search/Minimum.h (File Minimum.h)

• ADS/sort/Sorted.h (File Sorted.h)

• ADS/sort/impl/SelectionSort.tpp

• algorithm (File AkraBazzi.h)

• cstddef

• functional

• utility

• vector

Namespaces

• Namespace ADS

Functions

• Template Function ADS::selectionSort