E
// siehe http://sattas.homeunix.net/zeugs/quicksort.pdf
#include <iostream>
#include <ctime>
#include <conio.h>
using namespace std;
const int MAX = 10000000;
int daten[MAX];
void quicksort( int von, int bis )
{
int links = von, rechts = bis, mitte, zwischen;
mitte = ( von + bis ) / 2;
do{
for(;daten[links] < daten[mitte]; links++);
for(;daten[mitte] < daten[rechts]; rechts--);
if(links <= rechts)
{
//Tausch durchfuehren
zwischen = daten[links];
daten[links] = daten[rechts];
daten[rechts] = zwischen;
links++;
rechts--;
}
}
while (links <= rechts);
if(von < rechts) quicksort(von, rechts);
if(links < bis) quicksort(links, bis);
}
int main()
{
clock_t t1,t2;
double ts;
srand(time(NULL));
for(int i=0;i<(MAX);i++)
{
daten[i] = rand()%MAX;
}
t1=clock();
quicksort(0,MAX-1);
t2=clock();
ts=(t2-t1)/static_cast<float>(CLOCKS_PER_SEC);
cout << "\tZeit: " << ts << " QuickSort Test" << endl;
cout<<endl;
getch();
}
Die STL bietet bereits einen fertigen Algorithmus sort(begin,end) an, der auf Quicksort beruht, z.B. für vector, deque. list hat eine eigene Funktion sort().
Wenn du "sehen" willst, wie sort(begin,end) arbeitet:
#include <algorithm>
#include <iostream>
#include <conio.h>
#include "Xint_Sonde.h"
/*
Klasse Xint findet man z.B. hier:
http://www.c-plusplus.net/forum/viewtopic.php?t=85532&postdays=0&postorder=asc&start=10
*/
using namespace std;
int main ()
{
const int N = 5;
Xint x[N];
for(int i=0;i<N;++i)
{
x[i].setNum(N-i);
}
for(int i=0;i<N;++i)
{
cout << x[i].getNum() << endl;
}
cout << endl << endl;
sort(&x[0],&x[N]);
for(int i=0;i<N;++i)
{
cout << x[i].getNum() << endl;
}
Xint::statistik(cout);
getch();
}
