3. Was ist an meiner Quicksort implementierung falsch?

Was ist an meiner Quicksort implementierung falsch?

  • N

    Ich weiß, dass es Quicksort in der Standardbibliothek gibt, aber trotzdem, was ist hier falsch?

    template<class Iter, class Ftor>
struct partition
{
Iter operator()(Iter b,Iter e,Ftor f)
{
	Iter i=b-1;	//Suchzeiger
	Iter j=e;	//dito
	typename std::iterator_traits<Iter>::value_type v=*(e-1);
	for(;;)
	{
		while(++i!=e&&f(*i,v));
		while(--j>i&&f(v,*j));
		if(i>=j)    //<--- darauf bezieht sich die 2. Frage
			break;
		std::iter_swap(i,j);
	};
	std::iter_swap(i,e-1);
	return i;
};
};

template<class Iter,class Ftor,class Ftor2>
void quicksort(Iter begin,Iter end,Ftor f,Ftor2 p)
{
	if((end-begin)<2)
		return;
	Iter i=p(begin,end,f);
	quicksort(begin,i-1,f,p);
	quicksort(i+1,end,f,p);
};

    btw, ist es möglich die if-Abfrage rauszumachen? Ich meine, es dürfte kaum Unterschied machen, aber wenn die Schleife darüber aussteigt ist sowieso schluss...

    0
  • E
     

    while(++i!=e&&f(*i,v));  <<--  :warning: Das Semikolon :warning: 
        while(--j>i&&f(v,*j)); <<--  :warning: und gleich noch mal das Semikolon :warning: 
        if(i>=j)    
....

    // Edit:
    Falls es net klar sein sollte. die Semikola sollten sicherlich nicht da sein.

    0
  • N

    Hä? Natürlich müssen die da hin. Wie stellst du dir denn den Ablauf vor? Es hätte doch gar keinen Sinn die Schleife so oft zu durchlaufen...
    /edit: Mal ganz abgesehen davon, dass das Fehlen der Abfrage unweigerlich zu einem Speicherzugriffsfehler füren muss...

    0
  • E

    Sry

    Hab mir das net so genau angschaut.

    0
  • N

    Kann jedem mal passieren...
    Das hilft mir aber net wirklich weiter...

    0
  • W

    Was passiert denn, bzw. was macht er falsch? Das könnte zumindest helfen den Fehler einzugrenzen. Spontan würde ich sagen, dass du deine Partition-Funktion nochmal überarbeiten solltest.

    0
  • N

    Naja, er sortiert falsch...
    Beispiel:

    Wie viele Elemente?
25 
Max. Groesse?
35 
Erzeuge Elemente!
Benoetigte Zeit (in Sekunden): 0
Ausgabe in ungeordneter Reihenfolge:
[24][12][9][23][31][21][27][13][5][9][34][34][7][11][24][15][11][18][18][17][8][16][1][12][18]
Beginne Sortiervorgang!
Ausgabe in geordneter Reihenfolge:
[8][5][9][1][15][9][11][12][13][12][7][18][16][17][18][18][11][24][23][24][21][34][27][31][34]
Benoetigte Zeit (in Sekunden): 0

    Die Partitionierungsfunktion... Naja, woanders kann der Fehler ja kaum sein, aber ich find ihn halt nicht...

    0
  • P

    Wie wäre es mit einem kompletten Programm. Man hat immer so wenig Lust den Code selbst zu komplettieren.

    0
  • N

    Nun, das komplette Programm sieht in etwa so aus:

    #include <algorithm>
#include <iterator>
#include <utility>
#include <ctime>
#include <cstdlib>
#include <iostream>

int main()
{
	std::cout<<"Wie viele Elemente?"<<std::endl;
	unsigned c;
	std::cin>>c;
	std::vector<int> vec;
	std::cout<<"Max. Groesse?"<<std::endl;
	int a;
	std::cin>>a;
	std::cout<<"Erzeuge Elemente!"<<std::endl;
	std::time_t b;
	std::time(&b);
	std::srand(std::time(0));
	for(unsigned i=0;i<c;++i)
		vec.push_back(std::rand()%a+1);
	std::time_t e;
	std::time(&e);
	std::cout<<"Benoetigte Zeit (in Sekunden): "<<std::difftime(e,b)<<std::endl;
	std::cout<<"Ausgabe in ungeordneter Reihenfolge:"<<std::endl;
	for(unsigned i=0;i<vec.size();++i)
		std::cout<<"["<<vec[i]<<"]";

	std::cout<<std::endl<<"Beginne Sortiervorgang!"<<std::endl;
	std::time(&b);
	quicksort(vec.begin(),vec.end(),std::less<int>(),partition());
	std::time(&e);
	std::cout<<"Ausgabe in geordneter Reihenfolge:"<<std::endl;

	for(unsigned i=0;i<vec.size();++i)
		std::cout<<"["<<vec[i]<<"]";

	std::cout<<std::endl;
	std::cout<<"Benoetigte Zeit (in Sekunden): "<<std::difftime(e,b)<<std::endl;
	return 0;
}

    Das war halt einfach ein "session-Mitschnitt". Eigentlich ist das Programm übersichtlicher, hab jetzt halt zusammenkopiert...
    Aber wie gesagt, der Fehler muss im Algorithmus liegen, das andere Sortierverfahren Funkionieren...
    /edit: Ich hoffe jetzt stimmts...

    0
  • P

    Wenn ich beide Teile zusammenfüge kompiliert es nicht, einerseits fehlen die Header und andererseits ist der Aufruf von Quicksort fehlerhaft.

    0
  • P

    Als erstes würde ich sagen:

    Iter j = e - 1;

    anstatt

    Iter j = e;

    0
  • N

    Weil?
    Wenn du gründlich guckst, wird dir nochwas auffallen: Iter i=b-1;
    Aber kurz darunter:

    for(;;)
{
	while(++i!=e&&f(*i,v));
	while(--j>i&&f(v,*j));
                    //...

    Wie du siehst, werden die Variablen erst inkrementiert...

    0
  • P

    Du willst nicht das j auf das Pivotelement zeigt, nachdem es einmal dekrementiert wurde.

    Die beiden anderen Fehler sind:

    quicksort(begin,i,f,p);

    ist besser als:

    quicksort(begin,i-1,f,p);

    und

    while( (--j>i) && !f(*j, v) );

    ist besser als:
    while(--j>i&&f(v,*j));

    0
  • P

    Zuletzt würde ich b als das Pivotelement nehmen, da ich mir gar nicht sicher bin ob man b-1 überhaupt bilden darf.

    0
  • N

    Danke! Die Fehler sind so offensichtlich... Naja, hinterher ist man immer klüger... Nur Das letzte verstehe ich nicht.
    Nehmen wir mal an, es geht um std::less:

    while( (--j>i) && !f(*j, v) );
//ist besser als:
while(--j>i&&f(v,*j));
//umformen (damits gleich aussieht)
while(--j>i&&!f(*j,v));
while(--j>i&&f(v,*j));
//durch relationszeichen ersetzen:
while(--j>i&&!(*j<v));
while(--j>i&&v<*j);
//vereinfachen:
while(--j>i&&*j>=v);
while(--j>i&&v<*j);
//ein letztes mal umformen:
while(--j>i&&*j>=v);
while(--j>i&&*j>v);

    Macht das einen Unterschied? Ach, jetzt seh ichs, dass sind weniger Vertauschungen, oder?

    0
  • P

    Ja, es sollten weniger Vertauschungen sein.

    0
  • P

    Die Fehler hättest du auch mit Papier und Bleistift selber finden können. 🙂

    0
  • ?

    is zwar keine wirkliche Hilfe, aber versuch doch mal ne
    vernünftige Benennung zu finden ..

    template<
         class Iterator, 
         class CompareFunctor
        >
struct Partition {
    Iterator operator()(Iter begin, Iter end, CompareFunctor compare)
    {
        typedef typename std::iterator_traits<Iter>::value_type Value;
            // das ist zwar wirklich unnötig, ich finds irgendwie schöner so ..

        Iterator i = begin - 1;
        Iterator j = end;

        Value pivot = *(end - 1);

        while(i < j) {
            while(++i != j && compare(*i, pivot) < 0)
                ;

            while(--j != i && compare(pivot, *j) > 0)
                ;

            if(i != j) {
                std::iter_swap(i, j);
            }
        }

        std::iter_swap(i, e - 1);
        return i;
    }
};

template<
         class Iterator, 
         class PartitionFunctor, 
         class CompareFunctor
        >
void quicksort(Iterator begin, Iterator end,
               PartitionFunctor partition, CompareFunctor compare)
{
    if(end - begin < 2) {
        return;
    }

    Iterator pivot = partition(begin, end, compare);
    quicksort(begin, pivot - 1, partition, compare);
    quicksort(pivot + 1, end  , partition, compare);
}

    Übrigens seit wann is es so verdammt 31337 kein using namespace ...; zu
    verwenden? Ich kann ja verstehen, wenns heißt man will sich den gobalen
    Namespace nicht verschmutzen, aber da gibts doch immer noch die Möglichkeit
    ein etwas lokaleres using zu benutzen ...

    0
Anmelden zum Antworten