shakersort implementierung



  • ich habe das prinzip des shakersorts ansich verstanden: http://de.wikipedia.org/wiki/Shakersort

    was ich nicht verstehe ist, wie man das implementieren kann wenn man mit iteratoren arbeitet. man kann den end iterator nicht dekrementieren, so kommt man gar nie ans letze objekt ran...

    wenn man im vorbereitungsschritt die ganze liste von begin bis end durchgehen muss um das letzte objekt vor end zu finden, leidet die geschwindigkeit ...


  • Mod

    Dann ist die Voraussetzung für den Algorithmus wohl mindestens ein bidirektionaler Iterator.

    Iteratorkategorien



  • man kann den end iterator nicht dekrementieren

    Kommt drauf an, was für Iteratoren im Spiel sind. Sollten das nicht bidirektionale sein? Es heißt doch schließlich auch BiDirectional Bubblesort...
    Nur forward_list hätte das Problem.



  • es ist ein bidirektionaler iterator.
    aber der end-iterator eines containers zeigt laut definition doch hinter das letzte objekt...


  • Mod

    unterregistrierter schrieb:

    es ist ein bidirektionaler iterator.
    aber der end-iterator eines containers zeigt laut definition doch hinter das letzte objekt...

    Ja. Und?



  • soweit ich weiss darf man einen bidirektionalen zeiger hinter das letzte objekt (also ins nichts) nicht dekrementieren...



  • unterregistrierter schrieb:

    soweit ich weiss darf man einen bidirektionalen zeiger hinter das letzte objekt (also ins nichts) nicht dekrementieren...

    Dereferenzieren! Den operator* aufrufen! Nicht dekrementieren.


  • Mod

    Zu viel Freizeit 😉 :

    #include <functional>
    #include <iterator>
    #include <algorithm>
    
    template <typename BidirectionalIterator, class Compare>
    void sort(BidirectionalIterator begin, BidirectionalIterator end, Compare comp)
    {
      using std::swap;
      BidirectionalIterator first = begin;
      BidirectionalIterator last = end;
      --last;
      bool swapped = false;
      do
        {
          BidirectionalIterator next = first;
          ++next;
          for (BidirectionalIterator current = first++; current != last; ++next, ++current)
            {
              if (comp(*next, *current))
                {
                  swapped = true;
                  swap(*next, *current);
                }
            }
          if (!swapped)
            return;
          swapped = false;
          next = --last;
          --next;
          for (BidirectionalIterator current = last; current != first; --next, --current)
            {
              if (comp(*current, *next))
                {
                  swapped = true;
                  swap(*next, *current);
                }
            }      
        } while (swapped);
    }
    
    template <typename BidirectionalIterator>
    void sort(BidirectionalIterator begin, BidirectionalIterator end)
    {
      typedef std::iterator_traits<BidirectionalIterator> traits;
      ::sort(begin, end, std::less<typename traits::value_type>());
    }
    
    #include <iostream>
    
    int main()
    {
      int foo[] = {1,6,2,7,3,8,3,9,2};
      sort(foo, foo + (sizeof(foo)/sizeof(*foo)));
      for (unsigned i = 0; i < sizeof(foo)/sizeof(*foo); ++i)
        std::cout << foo[i] << '\n';
    }
    

    Irgendwie fühlt es sich so an, als könnte man das noch besser machen (außer der offensichtlichen Nicht-Benutzung von Cocktailsort), aber sooo lange braucht mein Code nun doch nicht zum compilieren 😃 . Daher: Freigabe für alle möglichen Verbesserungen.

    P.S.: Ja, ich bin mir der Ironie bewusst, dass ich algorithm einbinden musste, um meinen Sortieralgorithmus korrekt zu implementieren und sogar den Scopeoperator benutzen musst, um Verwechselungen mit std::sort auszuschließen.

    P.P.S.: Letzteres gibt mir auch direkt die erste Verbesserung: using std::swap, um ADL zu aktivieren. Hmm, sollte ich das auch für std::less tun? Wäre eher ungewöhnlich, less zu überladen, normalerweise überlädt man blos operator<.



  • SeppJ schrieb:

    Daher: Freigabe für alle möglichen Verbesserungen.

    template <bool Ascending, typename Iter, class Compare>
    bool bubble_pass(Iter begin, Iter end, Compare comp)
    {
      bool swapped = false;
    
      for (Iter next = begin; ++next != end; begin = next) {
        if (comp(*next, *begin) == Ascending) {
            swapped = true;
            std::iter_swap(next, begin); // adl-swap
        }
      }
    
      return swapped;
    }
    
    template <typename BIter, class Compare>
    void sort(BIter begin, BIter end, Compare comp)
    {
      if (begin == end) return;
    
      while (bubble_pass<true>(begin, end, comp) &&
             bubble_pass<false>(std::reverse_iterator<BIter>(end), std::reverse_iterator<BIter>(begin), comp))
        ;
    }
    
    template <typename BidirectionalIterator>
    void sort(BidirectionalIterator begin, BidirectionalIterator end)
    {
      typedef std::iterator_traits<BidirectionalIterator> traits;
      ::sort(begin, end, std::less<typename traits::value_type>());
    }
    

  • Mod

    Gefällt mir vom Stil her 👍

    Aber wenn ich das richtig sehe, fehlt da noch, dass man in den späteren Durchgängen nicht ganz bis zum Ende/Anfang laufen braucht.

    std::iter_swap(next, begin); // adl-swap
    

    Cool, kannte ich noch gar nicht.


Log in to reply