Sortieralgorithmus

Lars

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.

Mr. N

Radix Exchange?

Lars

hast du ein Link dazu?

Lars

Leider hab ich das grade nicht in der Hand

Mr. N

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

japro

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...

Mr. N

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.

japro

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.

Mr. N

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

Lars

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

Mr. N

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.

Lars

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

Mr. N

*lol*. schau mal i und j an.

Lars

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. ]