Der beste Weg, einzelne Ziffern von int für Radixsort in C / C ++ zu erhalten

Question

Was ist die beste Art und Weise in einem Radixsort Algorithmus einzelne Ziffern von einem int mit n Anzahl der Stellen für die Verwendung zu bekommen? Ich frage mich, ob es eine besonders gute Art und Weise ist es in C / C ++ zu tun, wenn nicht, was die allgemeinen beste Lösung ist?

bearbeitet. Nur zu klären, ich war auf der Suche nach einer Lösung, die nicht in einen String umzuwandeln und es wie eine Reihe von Ziffern Behandlung

Answer 1

Verwenden Sie die Ziffern der Größe 2^k. Um die nth Ziffer zu extrahieren:

#define BASE (2<<k)
#define MASK (BASE-1)

inline unsigned get_digit(unsigned word, int n) {
    return (word >> (n*k)) & MASK;
}

Die Verschiebung und der Maske (aktiviert durch die Basis eine Potenz von 2 ist) vermeidet teure Ganzzahl-Divisionsbefehle.

Danach wird die beste Basis der Wahl ist eine experimentelle Frage (Zeit / Raum Kompromiss für Ihre Hardware). Wahrscheinlich k==3 (Basis 8) funktioniert gut und begrenzt die Anzahl der Schaufeln, aber k==4 (Basis 16) sieht mehr attraktiv, weil sie das Wort Größe unterteilt. Allerdings gibt es wirklich nichts falsch mit einer Basis, die nicht das Wort Größe nicht teilt, und man könnte, dass die Basis 32 oder der Basis 64 eine bessere Leistung finden. Es ist eine experimentelle Frage und kann abweichen wahrscheinlich durch Hardware, je nachdem, wie der Cache verhält und wie viele Elemente gibt es in Ihrem Array.

Schlussbemerkung: Wenn Sie sortieren unterzeichnet Zahlen Leben ist ein viel größeren Schmerzen, weil Sie das signifikanteste Bit behandeln wollen wie unterzeichnet. Ich empfehle, alles als unsigned Behandlung, und dann, wenn Sie wirklich unterzeichnet müssen, im letzten Schritt Ihres Radixsort sehen Sie die Eimer tauschen, so dass Eimer mit einem höchstwertigen 1 kommen, bevor ein höchstwertiger 0. Dieses Problem ist auf jeden Fall einfacher, wenn k teilt die Wortgröße.

Answer 2

Nicht verwenden, Basis 10, die Verwendung der Basis 16.

for (int i = 0; i < 8; i++) {
    printf("%d\n", (n >> (i*4)) & 0xf);
}

Da ganze Zahlen intern binär gespeichert werden, wird dies effizienter sein, als durch 10 dividiert, um zu bestimmen dezimal Ziffern.