3. Sortieralgorithmus

Sortieralgorithmus

  • L

    Leider hab ich das grade nicht in der Hand 🙄

    0
  • M

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

    0
  • J

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

    0
  • M

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

    0
  • J

    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.

    0
  • M

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

    0
  • L

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

    0
  • M

    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.

    0
  • L

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

    0
  • M

    *lol*. schau mal i und j an.

    0
  • L

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

    0
Anmelden zum Antworten