mergesort implementierung



  • hallo

    meine implementierung des mergesort-algorithmus (nicht natürlich) sieht so aus:

    template<class IterType>
    void Mergesort(IterType Begin, IterType End)
    {
        std::size_t Lenght = End - Begin;
        if(Lenght <= 1)
            return;
        std::deque<typename IterType::value_type> Lhs(Begin, Begin + Lenght / 2);
        std::deque<typename IterType::value_type> Rhs(Begin + Lenght / 2, End);
        Mergesort(Lhs.begin(), Lhs.end());
        Mergesort(Rhs.begin(), Rhs.end());
        for(; !Lhs.empty() && !Rhs.empty(); Begin++)
            if(Lhs.front() <= Rhs.front())
            {
                *Begin = Lhs.front();
                Lhs.pop_front();
            }
            else
            {
                *Begin = Rhs.front();
                Rhs.pop_front();
            }
        for(; !Lhs.empty(); Begin++)
        {
            *Begin = Lhs.front();
            Lhs.pop_front();
        }
        for(; !Rhs.empty(); Begin++)
        {
            *Begin = Rhs.front();
            Rhs.pop_front();
        }
    }
    

    ich hab die funktion bereits zwei mal neu implementiert weil mir die art der speicherhandhabung nicht gefallen hat. es ist jedoch in jedem fall so ein speicherwirr-warr rausgekommen (wie auch oben). sieht jemand auf anhieb eine möglichkeit diese funktion "weniger speicherlastig" zu implementieren?

    gruss



  • Ich bin mir nicht sicher, ob ich Mergesort richtig verstanden habe, aber ich versuche es mal: Müsste es nicht möglich sein, die "Liste" nicht wirklich aufzuteilen, sondern nur jeweils Iteratoren auf Anfang und Ende der Aufteilung weiterreichen?



  • probier es mal so:

    template<class Iter1, class Iter2>
    void mergesort_impl(Iter1 b, Iter1 e, Iter2 b, Iter2 e)
    {
      ...
    }
    
    template<class Iter>
    void mergesort(Iter b, Iter e)
    {
      typedef typename iterator_traits<Iter>::value_type T;
      std::vector<T> temp (b,e);
      mergesort_impl(b,e,temp.begin(),temp.end());
    };
    

    und dann in mergesort_impl keine neuen container erzeugen und auch kein new verwenden.



  • Mergesort war doch eben NICHT inplace, meine ich mich zu erinnern?



  • Skym0sh0 schrieb:

    Mergesort war doch eben NICHT inplace, meine ich mich zu erinnern?

    Laut Wikipedia lässt sich Mergesort in-place implementieren, was aber etwas trickreich ist.



  • Skym0sh0 schrieb:

    Mergesort war doch eben NICHT inplace, meine ich mich zu erinnern?

    Wenn man nicht gerade verkettete Listen hat, benötigt man extra Speicher. Aber den kann man sich ganz am Anfang einmal organisieren und muss das nicht zwischendurch andauernd machen.



  • flabahz schrieb:

    sieht jemand auf anhieb eine möglichkeit diese funktion "weniger speicherlastig" zu implementieren?

    Eine schöne Gelegenheit sich mal std::list::splice() anzuschauen.

    Und dann auch noch std::list::merge() . Aber das ist dann schon fast wie von Beginn an std::sort() zu nehmen. 🙂


Log in to reply