vielen Dank für die videos bitte können sie mal ein video zum bottom-up aufsteigend und absteigend machen, in dem sie anfang,ende,weg, E-position,ringtausch und vergleiche erklären? Danke im voraus
Hey vielen Dank für das Video, ist wirklich super erklärt! Der Algorithmus ist wirklich interessant, aber zwei Fragen hätte ich: 1. Warum muss die Rahmenbedingung 2, also dass man die größte Zahl kennt, gelten? Wenn die größte Zahl nicht bekannt ist kann ja, wie in der "CountingSort-Klasse" implementiert und (wie ich es verstanden habe) auch in "Wettlauf-Klasse" durchgeführt, das Maximum mit einem vorangehenden Listendurchlauf der Dauer n ermittelt werden. Auch die Zeitkomplexität würde sich ja dadurch nicht ändern da Maximum ermitteln + CountListe erstellen + sortierte Liste übertragen ja nach wie vor n + n + k ist und damit auch noch in O(n) sein müsste oder (wegen diesem konstanten Faktor c, wie in dem Video zur Zeitkomplexität gezeigt)? 2. Was würde passieren, wenn beispielsweise die Zahlen 1, 2, 3, ... 1000 (vermischt) und 912577 in der zu sortierenden Liste gespeichert wären (also ich kann es mir denken aber ist der Algorithmus dann nach wie vor schneller?)? Bitte mehr von diesen Videos, sind extrem hilfreich zur Examensvorbereitung ;-) Viele Grüße, Andi PS: So wie ich das verstanden habe liegen die einzigen Nachteile dieses Algorithmus im (im Vergleich zu den anderen Sortieralgorithmen) hohen Speicherplatzverbrauch und im Ignorieren einer Vorsortierung
+Andi D Zu (1) Es gibt halt zwei Möglichkeiten: Entweder ich kenne das Maximum, oder ich muss einen linearen Durchlauf zum Bestimmen des Maximums durchführen (das hat auf die Komplexität letztendlich keinen Einfluss). Zu (2) Um wirklich sagen zu können, ob ein Algorithmus schneller ist als ein anderer, reicht die Angabe der Komlexitätsklasse allein nicht aus. Bei deinem Beispiel entsteht halt ein enorm großes CountingArray, dass zum großen Teil nur Nullen beinhaltet. Das ist natürlich ungünstig und kann dazu führen, dass das k (von O(n+k)) so groß wird, dass einer der rekursiven Sortieralgorithmen trotz O(n log(n)) schneller ist als der CountingSort. Nehme ich mal statt der 912577 die Zahl 99999999 als Maximum, so benötigt auf meinem System der Quicksort ca. 80 ms und der CountingSort bereits 230 ms.
Wirklich sehr gut erklärt. Hab den Algorithmus nun endlich verstanden! Die Schritt für Schritt Erklärungen helfen wirklich sehr.
sehr krasse Erklärung, danke dir!
Super gut erklärt! Danke!
vielen Dank für die videos
bitte können sie mal ein video zum bottom-up aufsteigend und absteigend machen, in dem sie anfang,ende,weg, E-position,ringtausch und vergleiche erklären?
Danke im voraus
Hey vielen Dank für das Video, ist wirklich super erklärt! Der Algorithmus ist wirklich interessant, aber zwei Fragen hätte ich:
1. Warum muss die Rahmenbedingung 2, also dass man die größte Zahl kennt, gelten? Wenn die größte Zahl nicht bekannt ist kann ja, wie in der "CountingSort-Klasse" implementiert und (wie ich es verstanden habe) auch in "Wettlauf-Klasse" durchgeführt, das Maximum mit einem vorangehenden Listendurchlauf der Dauer n ermittelt werden. Auch die Zeitkomplexität würde sich ja dadurch nicht ändern da Maximum ermitteln + CountListe erstellen + sortierte Liste übertragen ja nach wie vor n + n + k ist und damit auch noch in O(n) sein müsste oder (wegen diesem konstanten Faktor c, wie in dem Video zur Zeitkomplexität gezeigt)?
2. Was würde passieren, wenn beispielsweise die Zahlen 1, 2, 3, ... 1000 (vermischt) und 912577 in der zu sortierenden Liste gespeichert wären (also ich kann es mir denken aber ist der Algorithmus dann nach wie vor schneller?)?
Bitte mehr von diesen Videos, sind extrem hilfreich zur Examensvorbereitung ;-)
Viele Grüße, Andi
PS: So wie ich das verstanden habe liegen die einzigen Nachteile dieses Algorithmus im (im Vergleich zu den anderen Sortieralgorithmen) hohen Speicherplatzverbrauch und im Ignorieren einer Vorsortierung
+Andi D Zu (1) Es gibt halt zwei Möglichkeiten: Entweder ich kenne das Maximum, oder ich muss einen linearen Durchlauf zum Bestimmen des Maximums durchführen (das hat auf die Komplexität letztendlich keinen Einfluss).
Zu (2) Um wirklich sagen zu können, ob ein Algorithmus schneller ist als ein anderer, reicht die Angabe der Komlexitätsklasse allein nicht aus. Bei deinem Beispiel entsteht halt ein enorm großes CountingArray, dass zum großen Teil nur Nullen beinhaltet. Das ist natürlich ungünstig und kann dazu führen, dass das k (von O(n+k)) so groß wird, dass einer der rekursiven Sortieralgorithmen trotz O(n log(n)) schneller ist als der CountingSort. Nehme ich mal statt der 912577 die Zahl 99999999 als Maximum, so benötigt auf meinem System der Quicksort ca. 80 ms und der CountingSort bereits 230 ms.