Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

// Prog: minimum_sort.cpp // implements and tests minimum-sort on random input #include #include // PRE: [first, last) is a valid range // POST: the elements *p, p in [first, last) are in ascending order void minimum_sort (int* first, int* last) { for (int* p = first; p != last; ++p) { // find minimum in nonempty range described by [p, last) int* p_min = p; // pointer to current minimum int* q = p; // pointer to current element while (++q != last) if (*q < *p_min) p_min = q; // interchange *p with *p_min std::iter_swap (p, p_min); } } int main() { // input of number of values to be sorted unsigned int n; std::cin >> n; int* const a = new int[n]; std::cout << "Sorting " << n << " integers...\n"; // create random sequence for (int i=0; i