Sortieralgorithmus



  • Was ist der schnellste Sortieralgorithmus der keinen RandomAccess iterator braucht. Sprich einen Bidirectional. Würd mich ma interressieren da ich grade meine eigene list-Klasse implementiere.



  • Radix Exchange?



  • hast du ein Link dazu?



  • Leider hab ich das grade nicht in der Hand 🙄



  • Ne. Aber ein Buch: Algorithmen in C/C++/Pascal.



  • Original erstellt von Mr. N:
    Radix Exchange?

    hmm aber auch nur wenn die list kein template ist...
    afaik dürfte da quicksort am schnellsten sein...



  • Radix Exchange Sort sollte aber auch gut zu googlen sein. Ka, ob die Implementation die du dann finden wirst auch nicht Random ist. Und hier mal eine meiner dreckigsten Implementationen 😃 (WPC Speed eben):

    // We sort via radix exchange sort
    
    // The first sorting routine
    void wpc37a(int x1[], int x2[], int l, int r, int b, unsigned ones, unsigned zeros)
    {
    #define radixexchange wpc37a
    #define bits(x, k, j) (((x) >> (k)) & ~(~0 << j))
        while (r > l && b >= 0) {
            if (((1 << b) & ones) == 1) continue;
            if (((1 << b) | zeros) == 0) continue;
            int i = l, j = r;
            do {
                while (bits(x1[i], b, 1) == 0 && i < j) i++;
                while (bits(x1[j], b, 1) != 0 && j > i) --j;
                int t1 = x1[i], t2 = x2[i];
                x1[i] = x1[j];  x2[i] = x2[j];
                x1[j] = t1;     x2[j] = t2;
            } while (j != i);
            if (bits(x1[r], b, 1) == 0) j++;
            radixexchange(x1, x2, l, j - 1, b - 1, ones, zeros);
            l = j; --b;
        }
    #undef radixexchange
    }
    
    // The second sorting routine
    void wpc37b(int x1[], int x2[], int l, int r, int b) 
    {
    #define radixexchange wpc37b
        while (r > l && b >= 0) {
            int i = l, j = r;
            do {
                while (bits(x1[i], b, 1) == 0 && i < j) i++;
                while (bits(x1[j], b, 1) != 0 && j > i) --j;
                int t1 = x1[i], t2 = x2[i];
                x1[i] = x1[j];  x2[i] = x2[j];
                x1[j] = t1;     x2[j] = t2;
            } while (j != i);
            if (bits(x1[r], b, 1) == 0) j++;
            radixexchange(x1, x2, l, j - 1, b - 1);
            l = j; --b;
        }
    #undef radixecchange
    #undef bits
    }
    

    Das zweitere ist repräsentativer. 😃



  • mal im ernst den algorithmus kann man nur auf integer typen anwenden... ansonsten geht er entweder garnet oder is unglaublich lahm und muss immer neu implementiert werden.



  • @japro: Das ist mir bewusst. Ob quicksort geht, weiß ich nicht.



  • Du hast gar nicht auf mein Hauptkriterium geachtet:
    Das es kein bidirectional Iterator braucht



  • Original erstellt von Lars:
    Du hast gar nicht auf mein Hauptkriterium geachtet:
    Das es kein bidirectional Iterator braucht

    Du wolltest kein RandomAccess! Und den braucht es nicht.



  • ein bidirectional hat kein op[] bei dir braucht der iteratorer aber einen op[]



  • *lol*. schau mal i und j an.



  • ich hab ma propiert nen ganz simplem zu implementieren. Naja, hier das ungetesteste Ergebnis

    template<class iterator>
      struct sort_implementation<iterator, std::bidirectional_iterator_tag>
      {
        static void sort(iterator b, iterator e)
        {
    
          for(iterator bb(b); b != e;)
          {
            while(b < ++b && b != e)
            {
              swap(b, --b);
              ++b;
            }
            b = ++bb;
          }
        }
      };
    

    Kriegt das jemand unperformanter hin 😉

    [ Dieser Beitrag wurde am 08.01.2003 um 20:53 Uhr von Lars editiert. ]

    [ Dieser Beitrag wurde am 08.01.2003 um 20:55 Uhr von Lars editiert. ]


Log in to reply