Sortieralgorithmus für kleine Datenmengen

Tomahawk

Hallo!

Ich konnte bisher keine Informationen finden, welche Sortieralgorithmen für kleine Datenmengen (20 <= n <= 50) besonders gut geeignet sind. Der Algorithmus muss auch nicht stabil sein.

Das Problem sieht etwa so aus:

struct MoveInfo {
  int move;
  int value;
};

void SortMoves(MoveInfo* begin, MoveInfo* end) {
  // ???
}

Einen relativ schnellen "Sortieralgorithmus" für ganz kleine Datenmengen (2 <= n <= 5) konnte ich mittlerweile bauen:

int BestMove(MoveInfo* current, const MoveInfo* end) {
  MoveInfo* first = current;
  MoveInfo* best = current;

  while (++current != end) {
    if (current->value > best->value) {
      best = current;
    }
  }

  int move = best->move;
  *best = *first;

  return move;
}

Wie man sieht handelt es sich hier um die Sortierung von bewerteten Schachzügen.

Gruss,
T.

volkard

Dein Schneller sortiert nicht, der sucht den besten und stellt ihn vorne hin.

Für kleine Arrays dürfte insertion sort optimal sein. So bis 30 war es bei mir in Messungen immer anderen überlegen. Gelegentlich mal bis 50 sollte auch ok sein.

SeppJ

Ich werfe mal das Stichwort "optimal sorting network" in den Raum:
http://en.wikipedia.org/wiki/Sorting_network
http://pages.ripco.net/~jgamble/nw.html

Ich würde mehrere Kandidaten durchtesten. Das ganze kann je nach Architektur gerne stark schwanken.

Neben Volkards Vorschlag würde ich mir noch anschauen:

- quicksort (als Referenz)
- bubblesort (wird gefühlsmäßig bei n > 10 schon abkacken)
- radixsort (war bei mir auf einem sehr kleinen µC mal die schnellste allgemeine Variante bei n ~ 12)

Wenn du Abhängigkeiten unter den bewerteten "Moves" schon kennst kannst du das u.U. ausnützen (z.B. du hast m Teillisten/arrays die schon sortiert sind -> merge).

Kurze Antwort: Benchmarken