9.4 Quicksort-Indexsortierung
Der Quicksort-Algorithmus steht in C++ zur Verfügung.
In der untigen Umsetzung wird ein struct definiert, der sowohl die x-Werte, als auch den Index enthält. Wenn die sort-Methode einen Vektor von diesen structs ordnen soll, so muss man noch eine Vergleichsfunktion definieren, die true zurückliefert, wenn für zwei Elemente a,b gilt: a
#include <iostream>
#include <fstream>
#include <vector>
#include <time.h>
#include "vektordef.h"
#include "lesen.h"
using namespace std;
struct Xind
{
double x;
int index;
};
typedef vector<Xind> Xindvektor;
bool vergleich(const Xind &a,const Xind &b)
{
return a.x < b.x;
}
int main(int anzahl,char** eingabe)
{
if(anzahl!=3)
{
cout<<"Benutzung:"<<anzahl<<endl;
cout<<"bubbleindex <Filename in> <Filename out>"<<endl;
cout<<"In dem Input-File sollten Messwertpaare stehen."<<endl;
}
else
{
Doublevektor messungen = lesen(eingabe[1]);
int anzahl = messungen.size()/2;
Xindvektor xwerte;
Doublevektor ywerte;
for(int i=0;i<messungen.size()/2;i++)
{
Xind xind;
xind.x = messungen.at(i*2);
xind.index = i;
xwerte.push_back(xind);
ywerte.push_back(messungen.at(i*2+1));
}
clock_t t1,t2;
t1 = clock();
sort(xwerte.begin(),xwerte.end(),vergleich);
t2 = clock();
cout<<"Dauer der Berechnung:"<<(double)(t2-t1)/CLOCKS_PER_SEC<<" Sekunden"<<endl;
ofstream speichern(eingabe[2]);
for(int i=0;i<anzahl;i++)
speichern<<xwerte.at(i).x<<" "<<ywerte.at(xwerte.at(i).index)<<endl;
speichern.close();
}
return 0;
}
Code 9.4-1: C++ Programm "quicksortindex.cpp"
Programm quicksort, .cpp, .h und .exe - Dateien gepackt