schnelle Sortierung in O(n)?

[nixchecker]

Es gilt ja:

1. Sortierung geht schnellstens mit O(n log(n)).
2. Eine Liste von ints in [min; max] kann man sortieren, indem man ein array der Länge max-min+1 anlegt, alles mit 0 initialisiert und für jeden Wert x der zu sortierenden Liste an die x-te Stelle des Arrays eine 1 schreibt. Das geht in O(n).

Wie kann man den Widerspruch auflösen?

[Helium]

Vergleichsbasierte Sortierung geht bestenfalls in O(n log n).

[SeppJ]

Annahme 1 gilt nur für serielles, vergleichsbasiertes Sortieren. Dein Algorithmus 2 ist kein Sortieren durch Vergleichen. Siehe:
https://en.wikipedia.org/wiki/Comparison_sort
https://en.wikipedia.org/wiki/Integer_sorting

edit: Zu langsam. Ich war mal wieder zu fleißig und habe zu lange gebraucht, um den Link zur Integersortierung zu finden .

[nixchecker]

Danke!

[icarus2]

nixchecker schrieb:

2. Eine Liste von ints in [min; max] kann man sortieren, indem man ein array der Länge max-min+1 anlegt, alles mit 0 initialisiert und für jeden Wert x der zu sortierenden Liste an die x-te Stelle des Arrays eine 1 schreibt. Das geht in O(n).

Das ist doch nicht $\mathcal{O}(n)$? Wir messen die Laufzeit anhand der Laenge des Inputs, d.h. in diesem Fall wird $n$ als die Anzahl der Elemente in der zu sortierenden Liste angenommen.

Angenommen du hast die Liste [2, 2^{32}-1, 0], die du sortieren moechtest. Dann hast du bloss drei Elemente, brauchst aber ein Array der Laenge $2^{32}$ und musst dieses initialisieren. Bereits hier ist offensichtlich, dass dieser Algorithmus nicht in $\mathcal{O}(n)$ laeuft.

Angenommen wir haben Zahlen im Intervall [0,max-1], dann hat dieser Algorithmus Laufzeit $\mathcal{O}(max)$. Auch wenn dies auf den ersten Blick polynomiell aussieht, so dieser Algorithmus bloss pseudopolynomiell. Der Grund dafuer ist, dass die die Darstellung von $max$ bloss $\lceil\log_2(m) + 1\rceil$ Bits braucht, d.h. die Laufzeit ist exponentiell in der Eingabelaenge.

Dieser Algorithmus laeuft also nicht in linearer Zeit, ausser man nimmt an, dass $max$ "klein" genug ist.

[hustbaer]

icarus2 schrieb:

Dieser Algorithmus laeuft also nicht in linearer Zeit, ausser man nimmt an, dass $max$ "klein" genug ist.

Was eine super-übliche Annahme in der Informatik ist.
Wenn "max" nämlich nicht klein genug ist, dann geht schon das Vergleichen nicht mehr in O(1).

Trotzdem bleibt das O(N) eines Radix Sort meist uninteressant, weil das implizierte k in den meisten Fällen viel zu gross ist.

[icarus2]

hustbaer schrieb:

icarus2 schrieb:

Dieser Algorithmus laeuft also nicht in linearer Zeit, ausser man nimmt an, dass $max$ "klein" genug ist.

Was eine super-übliche Annahme in der Informatik ist.
Wenn "max" nämlich nicht klein genug ist, dann geht schon das Vergleichen nicht mehr in O(1).

Mit "klein genug" meinte ich logarithmisch in der Eingabelaenge $n$. Dann ist der Algorithmus polynomiell.

Wenn wir aber annehmen, dass $max$ ein Integer (z.B. 32bit oder 64bit) lang ist, dann ist die Laufzweit $\mathcal{O}(max)$ exponentiell in der Eingabelaenge, d.h. nicht mehr polynomiell.
Und solche Integer sind sicher eine uebliche Annahme (alle Grundoperationen haben eine konstante Laufzeit).

hustbaer schrieb:

Trotzdem bleibt das O(N) eines Radix Sort meist uninteressant, weil das implizierte k in den meisten Fällen viel zu gross ist.

Die Laufzeit von Radix Sort ist $\mathcal{O}(kn)$, wobei $k = \lceil \log_2(max) + 1 \rceil$ gilt. Natuerlich wird Radix Sort sehr schnell unbrauchbar, wenn $k$ zu gross wird. Aber wenn wir wie oben Integer annehmen, dann ist das $k$ konstant.

[deadnuss]

icarus2 schrieb:

Angenommen du hast die Liste [2, 2^{32}-1, 0], die du sortieren moechtest. Dann hast du bloss drei Elemente, brauchst aber ein Array der Laenge $2^{32}$ und musst dieses initialisieren. Bereits hier ist offensichtlich, dass dieser Algorithmus nicht in $\mathcal{O}(n)$ laeuft.

Du beschreibst Counting Sort statt Radix Sort. Radix Sort sortiert bitweise und hat hier O(32*3) Zeit bei O(1) Speicher, allg. O(log(max)*n) bzw. O(sizeof(Element)*n) Zeit und O(1) Speicher.

Bereinigen wir es der Binärdarstellung haben wir immer noch O(n) in Bezug auf die Eingabelänge.

Wie ist das mit dem klassischen Sortieren? O(n log n * sizeof(Element)) Zeit (das sizeof für Vergleich/Kopieren) oder O(n log n) in bezug auf die Eingabelänge.

@hustbaer: Ich hoffe du sprichst vom naiven Countingsort mit numeric_limits<int>::max() Speicher. Das echte Radixsort schlägt std::sort bei ints um Längen.

[Michael E.]

hustbaer schrieb:

icarus2 schrieb:

Dieser Algorithmus laeuft also nicht in linearer Zeit, ausser man nimmt an, dass $max$ "klein" genug ist.

Was eine super-übliche Annahme in der Informatik ist.
Wenn "max" nämlich nicht klein genug ist, dann geht schon das Vergleichen nicht mehr in O(1).

Das Vergleichen geht in O(log max). icarus2 hat eigentlich alle Informationen genannt, nämlich dass max exponentiell beschränkt in der Eingabelänge ist und dass ein Algorithmus, dessen Laufzeit polynomiell in Eingabegröße und größter Zahl in der Eingabe abhängt, pseudopolynomielle Laufzeit hat.

Trotzdem bleibt das O(N) eines Radix Sort meist uninteressant, weil das implizierte k in den meisten Fällen viel zu gross ist.

Die versteckte Konstante in der O-Notation ist nicht das Problem, falls du das meinst.

Edit: Mein Gott, bin ich schnell heute Abend

[icarus2]

deadnuss schrieb:

Du beschreibst Counting Sort statt Radix Sort.

Ich beschreibe den Algorithmus, den der TE unter Punkt 2 vorgeschlagen hat. Und das ist doch nicht Radix Sort?

[deadnuss]

icarus2 schrieb:

deadnuss schrieb:

Du beschreibst Counting Sort statt Radix Sort.

Ich beschreibe den Algorithmus, den der TE unter Punkt 2 vorgeschlagen hat. Und das ist doch nicht Radix Sort?

Sorry, dein Post ist korrekt (er bezieht sich eindeutig den Counting Sort vom TE). hustbaers Post hat mich da verwirrt.