// Programm: quicksort.C
// Sortieren eines Vektors von Zahlen mittels Quicksort.
#include
#include
#include
#include
#include
typedef std::vector Vec;
typedef Vec::iterator It;
typedef Vec::const_iterator Cit;
namespace ifet {
It split(It b, It e)
// PRE: [b,e) ist ein nichtleerer gueltiger range.
// POST: Die Elemente in [b,e) wurden permutiert.
// Rueckgabewert ist ein s aus [b,e), so dass
// fuer alle i in [b,s): v[i] <= pivot,
// v[s] == pivot sowie
// fuer alle i in (s,e): v[i] > pivot,
// wobei pivot == *b beim Aufruf der Funktion.
{
assert(b != e);
It i = b;
for (It j = ++i; j != e; ++j)
// Invariante: *[b,i) <= *b && *[i,j) > *b.
if (*j <= *b) std::swap(*(i++), *j);
// Tausche das Pivot-Element in die richtige Position
// (am Ende des ersten Blocks)
std::swap(*b, *--i);
return i;
} // split(b, e)
void quicksort(It b, It e)
// PRE: [b,e) ist ein gueltiger range.
// POST: Die Elemente in [b,e) sind aufsteigend sortiert.
{
if (b == e) return;
It mid = ifet::split(b, e);
ifet::quicksort(b, mid);
ifet::quicksort(++mid, e);
} // quicksort(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
ifet::quicksort(v.begin(), v.end());
for (It i = v.begin(); i != v.end(); ++i)
std::cout << *i << " ";
std::cout << std::endl;
return 0;
}
