// Programm: minsort.C
// Sortieren durch Minimum-Suche.
#include
#include
#include
typedef std::vector Vec;
typedef Vec::iterator It;
typedef Vec::const_iterator Cit;
namespace ifet {
It min_element(It b, It e)
// PRE: [b,e) ist gueltiger range.
// POST: Rueckgabewert ist der erste Iterator i in [b,e),
// fuer den gilt: fuer alle j in [b,e) ist *i <= *j.
{
if (b == e) return e;
It m = b++;
for (; b != e; ++b)
if (*b < *m) m = b;
return m;
}
void min_sort(It b, It e)
// PRE: [b,e) ist gueltiger range.
// POST: [b,e) ist aufsteigend sortiert, d.h., fuer alle
// Paare i,j aus [b,e) mit j aus [i,e) gilt *i <= *j.
{
for (; b != e; ++b)
std::iter_swap(b, ifet::min_element(b, e));
}
} // namespace ifet
int main()
{
Vec v;
for (int i = 0; i < 5; ++i) {
v.push_back(2*i);
v.push_back(9-2*i);
}
// v == (0,9,2,7,4,5,6,3,8,1)
// Ausgabe von v
std::cout << "v = (";
for (Cit i = v.begin(); i != v.end(); ++i)
std::cout << *i << " ";
std::cout << ")" << std::endl;
// Sortieren von v
ifet::min_sort(v.begin(), v.end());
// Ausgabe von v
std::cout << "v = (";
for (Cit i = v.begin(); i != v.end(); ++i)
std::cout << *i << " ";
std::cout << ")" << std::endl;
return 0;
}