3. Was ist an meiner Quicksort implementierung falsch?

Was ist an meiner Quicksort implementierung falsch?

  • 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