// Programm: quicksort.C
// Sortieren eines Vektors von Zahlen mittels Quicksort.
#include
#include
#include
#include
#include
typedef std::vector Vec;
typedef Vec::iterator It;
namespace ifm {
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 = ifm::split(b, e);
ifm::quicksort(b, mid);
ifm::quicksort(++mid, e);
} // quicksort(b, e)
void random_shuffle(It b, It e)
// POST: [b,e) ist zufaellig permutiert. (d.h. die (Multi-)Menge
// der Elemente ist unveraendert, aber die Reihenfolge ist
// zufaellig gleichverteilt unter allen moeglichen Reihenfolgen.)
{
double rand = ifm::random(0);
for (; b != e; ++b) {
std::iter_swap(b, b + int((e-b) * rand));
rand = ifm::random(rand);
}
}
} // namespace ifm
int main()
{
// Initialisierung
const unsigned int n = 128;
Vec v;
for (unsigned int i = 0; i < n; ++i)
v.push_back(i);
// Zufaellig permutieren
ifm::random_shuffle(v.begin(), v.end());
for (It i = v.begin(); i != v.end(); ++i)
std::cout << *i << " ";
std::cout << std::endl;
// Sortieren
ifm::quicksort(v.begin(), v.end());
for (It i = v.begin(); i != v.end(); ++i)
std::cout << *i << " ";
std::cout << std::endl;
return 0;
}
