Ich habe ein Zahlenarray von 16384 float Zahlen, das sortiert werden müsste. Habe mir gedacht "hui, da schreib ich mal schnell meine eigene Sortierroutine und werde schön, reich und berühmt" Naja, was soll ich sagen, meine eigene Routine funktioniert nicht gut und ist lahm wie Bubblesort. Und nix mit schön, reich und berühmt. Schande über mich. Habt ihr eine Routine die schnell abläuft, und auch schnell programmiert ist?
Hallo: qsort (quicksort). wird sogar mit jedem Kompiler mit ausgeliefert. Nur noch benutzen. ciao Volker
Quick sort ist in ein paar Zeilen hingeschrieben, wenn man es verstanden hat, im Allgemeinen recht fix (es gibt nur wenige Fälle, wo andere besser sind) und vor allem fertig in der C-Bibliothek (qsort()).
Hallo, ein Blick in Wikipedia zeigt bereits ein paar Alternativen: http://de.wikipedia.org/wiki/Sortierverfahren Viel Spass Micha
Aber da wird es dir gehen wie mir: Mit Reichwerden wird das nix, andere sind da meistens schneller.
Ich habe einen wahrhaft wunderbaren Algorithmus gefunden, der mit O(log n) läuft, leider ist der Rand im Forum hier zu klein, um ihn darzustellen.
wenn er wirklich mit O(log n) läuft, kannst du damit reich werden. Wahrhaft wunderbar.
ich kann mich erinnern. Er ergibt sich aus Fermats letztem Satz. Die Beweisführung hat einige Jahre gedauert und hat ein dickes Buch hervorgebracht. Wenn man dieses Buch gelesen und verstanden hat, ist der entsprechende Sortieralgorithmus mit Leichtigkeit aufzuschreiben. W.
@ Claudio: Würde dein Algo jedes Element auch nur einmal ansehen, hätte er schon O(n). Log n liegt darunter, d.h. er sortiert, ohne alle Elemente gesehen zu haben. Sofort patentieren!
Claudio H. schrieb: > Ich habe einen wahrhaft wunderbaren Algorithmus gefunden, der mit O(log > n) läuft, leider ist der Rand im Forum hier zu klein, um ihn > darzustellen. Is natürlich ein Hinderniss, richtig. Ich glaube, du meinst eher O(n * log n), aber davon gibt es etliche Verfahren.
Klaus Wachtler schrieb: > Log n liegt darunter, d.h. er sortiert, ohne alle Elemente gesehen zu > haben. > > Sofort patentieren! Ist das vielleicht eine Abart des sagenumwobenen "Do what I mean" Algorithmus? Die Legende sagt, wer ihn programmieren kann, kann auch Blei in Gold verwandeln :-) Schade, dass das Forum einen so kleinen Rand hat.
".... leider ist der Rand im Forum hier zu klein,..... " ist ein abgewandeltes Zitat von Fermat. Wolfgang
Sollte man ändern, ja. Ich eröffne die Petition "Forum mit breitem Rand für Sortieralgorithmen"
Klaus Wachtler schrieb: > @ Claudio: > Würde dein Algo jedes Element auch nur einmal ansehen, hätte er schon > O(n). > Log n liegt darunter, d.h. er sortiert, ohne alle Elemente gesehen zu > haben. > > Sofort patentieren! In Hardware schaffe ich O(log²(n)) zeitlich gesehen :D
Stefan schrieb:
> O(1) ...zeitlich gesehen
Beweis?
Ich meinte natürlich Zeitkomplexität...
Christopher D. schrieb:
> In Hardware schaffe ich O(log²(n)) zeitlich gesehen :D
Klar, vor allem durch verstärkten Einsatz von Immer und Nimmer Gattern.
Ein modernerer Ansatz wäre allerdings die hardwäremäßige Implementierung
als Fuzzy Netzwerk mit Manchmal oder Meistens Gatter.
Udo R. S. schrieb: > Christopher D. schrieb: >> In Hardware schaffe ich O(log²(n)) zeitlich gesehen :D > > Klar, vor allem durch verstärkten Einsatz von Immer und Nimmer Gattern. > Ein modernerer Ansatz wäre allerdings die hardwäremäßige Implementierung > als Fuzzy Netzwerk mit Manchmal oder Meistens Gatter. Nicht das ABER vergessen.
Christopher D. schrieb: > Stefan schrieb: >> O(1) ...zeitlich gesehen > > Beweis? > > Ich meinte natürlich Zeitkomplexität... Eine Look-up Tabelle hat die (Zeit-)komplexität O(1). Genau aus diesem Grund betrachtet man die Laufzeit ja auch bezüglich eines Beschränkten (Speicher-)kapazität, weil sonst jedweder Alg. in O(1) lösbar ist indem man einfach eine entsprechend große Tabelle definiert.
Christopher D. schrieb: > Stefan schrieb: >> O(1) ...zeitlich gesehen > > Beweis? > > Ich meinte natürlich Zeitkomplexität... Analogrechner :-) Wir bauen einen SpaCo. Einen Spaghetti Computer Die Länge jeder Spaghetti ist proportional zur Zahl. Je höher die Zahl, desto länger. Dann teilt sich die ganze Aufgabe in 3 Teile auf * Vorbereitungsphase zuschneiden der Spaghetti auf die korrekte Länge * Sortieren Alle Spaghetti in eine Hand und auf dem Tisch aufschlagen. Die Die Spaghetti rutschen in Position, dass sie alle mit einem Ende am Tisch anstehen * Nachbearbeitung Mit einem Brett von oben an den Pack Spaghetti herangehen und immer die Nudel rausziehen, welche das Brett berührt. Vorbereitung und Nachbearbeitung dauern etwas. Aber das eigentliche Sortieren ist O(1) Bei größeren Mengen braucht man dann natürlich das Equipment für SuperSpaCo: Einen Gabelstapler und einen großen Stahlreifen um die Spaghetti während des Aufstossens in Form zu halten.
Eine Look-Up-Tabelle hat keinesfalls eine Komplexitaet von O(1): Sie kann nur beschraenkt gross sein. Fuer beliebige Problemgroessen waeren wieder mehrere Lookups noetig, was sich dann asymptotisch hoechstens so gut wie das Optimum verhaelt.
Ach, btw... was zum Teufel ist denn bitte Zeitkomplexitaet?! Das macht nichtmal intuitiv Sinn.
Marvin Sebulov schrieb:
> Ach, btw... was zum Teufel ist denn bitte Zeitkomplexitaet?!
Der funktionale Zusammenhang zwischen Problemgröße und des zur Lösung
des Problems benötigten Zeit.
Wobei im allgemeinen nur die Tendenz, also die Charakteristik der
Funktion interessiert.
Das hier
1 | for( i = 0; i < n; ++i ) { |
2 | for( j = 0; j < n; ++j ) { |
3 | if( a[i] > a[j] ) |
4 | swap( &a[i], &a[j] ); |
5 | }
|
6 | }
|
ist O(n^2) Bei Verdopplung von n landet man daher bei der 4-fachen Laufzeit. Warum sollte intuitiv klar sein. Der innerste Anweisungsblock wird durch beiden ineinander geschachtelten for-Schleifen n^2 oft mal ausgeführt.
Karl heinz Buchegger schrieb: > Marvin Sebulov schrieb: >> Ach, btw... was zum Teufel ist denn bitte Zeitkomplexitaet?! > > Der funktionale Zusammenhang zwischen Problemgröße und des zur Lösung > des Problems benötigten Zeit. Hups. Das ist nun natuerlich ein wenig peinlich. Ich hatte tatsaechlich noch nie den Begriff "Zeitkomplexitaet" fuer asymptotische Komplexitaet gehoert. Aber dennoch danke fuer die nette Erklaerung :) .
Warum hat bisher keiner die Korrelationskoinvarianz des Komplexitätsgrades bei der zweidimensionalen Aproximationsebene berücksichtigt. Die Austauschbarkeit verschiedener Verfahren mit gleichem O() erlaubt einen Homomorphismus 2. Grades dessen Extremalebenen vor der Optimierung bestimmt werden können. Für den worst case gilt dann O(n^(0.5)*log(n)/e). Der Beweis wird z.Z. im Rahmen einer Promotion geführt.
Claudio H. schrieb: > Ich habe einen wahrhaft wunderbaren Algorithmus gefunden, der mit O(log > n) läuft, leider ist der Rand im Forum hier zu klein, um ihn > darzustellen. Oja sofort patentieren lassen ^^ =) Oder darf ich ?
Lehrmann Michael schrieb:
> Oja sofort patentieren lassen ^^ =) Oder darf ich ?
Alles völliger Quatsch!
Es gibt einen Sortieralgorithmus mit einer Laufzeit von O(1) und jeder
Anfänger kann ihn implementieren!
Stephan
Randnotiz [a.k.a. die letzten Worte des Informatik-Hiwis]:
Heute habe ich einen neuen Sortieralgorithmus entdeckt. Seine Laufzeit
ist für ein Element genau so groß wie für Nmax =
(RAM_SIZE-KERNEL_SIZE-APPLICATION_SIZE)/ELEMENT_SIZE Elemente, und damit
ist bereits bewiesen, dass er in O(1) läuft. Es wird einfach ein
statisches Array für Nmax Elemente benötigt, so simpel ist das!
Die Rechenzeit liegt zwar bei 6 Stunden, aber ich bin mir immens sicher,
dass sich das noch weiter optimieren lässt.
wenn wir schon bei Superlativen sind: ich habe neulich ein Epsilon entdeckt, das kleiner ist als alle bisher bekannten Epsilon. Es ist sogar so klein, daß es negativ wird, wenn man es durch 2 teilt!
Wegstaben Verbuchsler schrieb: > ich habe neulich ein Epsilon entdeckt, das kleiner ist als alle bisher > bekannten Epsilon. Es ist sogar so klein, daß es negativ wird, wenn man > es durch 2 teilt! Eine Zahl, die erst dann negativ wird, wenn man sie durch zwei Teilt, wäre wirklich mal ne Entdeckung. Dagegen sähen O(1)-Sortieralgorithmen wirklich aus wie Raumschiff Ohrion gegen die neue Enterprais. Stephan
O(n): erstelle ein Array (neu) mit ausreichender Größe. Durchlaufe das zu sortierende Array, und füge die aktuelle Zahl i an der Stelle neu[i] ein.
jo schrieb: > O(n): > erstelle ein Array (neu) mit ausreichender Größe. > Durchlaufe das zu sortierende Array, und füge die aktuelle Zahl i an der > Stelle neu[i] ein. Oh du hast gerade Bucketsort erfunden :D
Vor allem ganz toll, wenn ein Wert mehrfach vorkommt. Abgesehen davon muß man sich klarmachen, was n in O(n) ist. Bei n Elementen im Bereich z.B. von 0...m-1 muß man erstmal m Elemente im Feld neu[] als ungültig initalisieren und hinterher durchlaufen, um die dann noch ungültigen irgendwie von den benutzten zu trennen. Da m>n ist, hat man nicht O(n), sondern O(m). Aber O(n) hört sich erst mal gut an.
Genmutant schrieb: > Oder Bogo-Sort! :-P > Das ist mit etwas Glück auch O(1) Zen-Sort ist garantiert O(1) Schließlich hat es einen natürlichen Grund warum die Reihenfolge der Reihung so ist wie sie ist also sollte man die auch nicht ändern.
BWL-sort hat auch O(1): "Morgen ist es garantiert fertig, egal wie viele Elemente es hat"
es gibt O(1), in der Tat. Erzeuge ein Array S mit ausreichender Größe. Füge das Element n der zu sortierenden Arrys an der Stelle S(n) ein.
Wenn du das meinst was ich glaube das du meinst, dann ist das immer noch O(n) und unter dem Namen Bucketsort bekannt.
O(0) mit Quantosort: Es hat bereits die richtige Reihenfolge bis man hinschaut. Also bloß nicht anrühren.
O(log N) geht mit Moore-Sort, der sich duch Anwendung des Mooreschen Gesetzes auf Bucket-Sort ergibt: Der Rechner wird schließlich jede "Zeiteinheit" doppelt so schnell, und kann deshalb auch doppelt soviele Elemente wegsortieren wie in der vorhergehenden Zeiteinheit ;)
O(n*log(n)) ist bereits eine untere Schranke bei Vergleichs-Sortierern, die also jedes Element notwendigerweise mit jedem anderen vergleichen. Das ist auch in 500 Jahren noch so. Ein guter Quicksort ist also nah am Optimum. Und Quicksort ist wunderbar parallelisierbar.
Randomsort: for( int i = 0; i<Max; i++ ) Sorted[randInt(Max)] = Unsorted[randInt(Max)]; Mit etwas Glück ists nach O(n) auch sortiert xD </troll> Ich bin ein riesen Fan des Heapsorts: O(n log n) http://de.wikipedia.org/wiki/Heapsort Kann einem beim ersten Mal so schön die Hirnwindungen verwinden ;)
Hallo. Was haltet ihr vom Selectionsort (http://de.wikipedia.org/wiki/Selectionsort)? Der ist echt easy zum Prorammieren. Obwohl der O(n²) hat, find ich den ganz cool, weil recht wenig hin und her gemoved wird. Zeitlich gesehen müsste der doch recht schnell durchgelaufen sein, oder?
Sehr amüsant, die vielen neuen Sortierverfahren! Ich hätte da noch Homöopathie-Sort. Ist leider nur O(n). foreach i { a = i; a = a*0; // "Potenzieren" a = a*0; // "Potenzieren" a = a*0; // "Potenzieren" ziel_array[a] = i; // wir nutzen das "Gedächtnis" der Speicherzelle } Jetzt aber mal im Ernst: Bei all den Komplexitätsvergleich muss man immer beachten, dass die Konstanten weggelassen werden. So kann es sein, dass ein O(n*log n)-Algorithmus erst ab 5 Millionen Elementen tatsächlich schneller läuft als ein O(n^n).
Matthias N. schrieb: > Randomsort: > > for( int i = 0; i<Max; i++ ) > Sorted[randInt(Max)] = Unsorted[randInt(Max)]; > > Mit etwas Glück ists nach O(n) auch sortiert xD Ts, ts. Und wenn nicht? Dass ein Sortierverfahren etwas unsortiertes hinterlässt geht ja wohl gar nicht.
1 | sorted = false; |
2 | |
3 | while( ! sorted ) { |
4 | |
5 | GenerateRandomDistribution(); |
6 | |
7 | for( int i = 0; i<Max; i++ ) |
8 | Sorted[randInt(Max)] = Unsorted[randInt(Max)]; |
9 | |
10 | sorted = true; |
11 | for( int i = 0; i<Max-1; i++ ) { |
12 | if( !( Sorted[i] < Sorted[i+1] ) ) |
13 | sorted = false; |
14 | }
|
15 | }
|
(Ich geh mal davon aus, dass randInt sich darum kümmert, dass jede Zufallszahl nur 1 mal auftaucht und bei wiederholtem Aufruf richtig arbeitet. Wenn diese Funktion das nicht gewährleisten kann, dann müsste man sich darum kümmern
Wenn eine Zahl nicht wiederholt vorkommen kann, ist es mit Zufall aber auch nicht soweit her....
Matthias schrieb: > Obwohl der O(n²) hat, find ich den ganz cool, weil recht > wenig hin und her gemoved wird. Zeitlich gesehen müsste der doch recht > schnell durchgelaufen sein, oder? [ ] Du hast das Konzept der Landau-Symbole verstanden O(n²) ist ein guter Hinweis darauf, dass es nicht schnell durchläuft. Für einen Algorithmus in O(n²) ist der Rechenaufwand proportional zum Quadrat der Elementanzahl. Das mag für 100 Elemente noch Ok sein, vielleicht auch noch bei 100.000 Einträgen (Unterschied: Faktor 1.000.000), aber bei 100.000.000 Elementen hört der Spaß dann wahrscheinlich auf. mfG Markus
Man kann die Sortieralgorithmen nicht nur nach ihrem Ressourcenbedarf bewerten, sondern auch nach ihren Anforderungen an die Daten. Es werden ja nicht nur Zahlen sortiert, sondern auch komplett andere Dinge. In einen Projekt wurden mal Abhängigkeiten zwischen Modulen sortiert, der Entwickler hat dafür Quicksort genommen. Leider hat er nicht bedacht, dass die Abhängigkeiten nicht die Transitivität besitzen, manchmal kamen sortierte Daten raus, aber meistens hat der Sortierer die falschen Daten verglichen, und es kam Mist raus. Da mussten wir einen Algorithmus mit O(n*n) nehmen. Andersherum geht es auch: Wenn man weiss in welcher Form die Daten vorliegen, kann man oft bessere Ergebnisse (Ressourcenbedarf) als Quicksort erzielen, wohlgemerkt hat man dann aber kein allgemeingültiges Sortierverfahren mehr.
Claudio H. schrieb: > Man kann die Sortieralgorithmen nicht nur nach ihrem Ressourcenbedarf > bewerten, sondern auch nach ihren Anforderungen an die Daten. Zeitweilig kann man auch Wissen über die momentane Sortierreihenfolge ausnützen. Ich hatte tatsächlich einen Fall, in dem der ganz banale, oft verteufelte, Bubble Sort (mit vorzeitigem Abbruch) sich als die schnellste Variante herausgestellt hat. Warum? Weil die Daten praktisch ständig schon sortiert waren und wenn sich an den Daten etwas ändert, dann waren das nur marginale Änderungen, bei denen 2 Elemente ihre Plätze getauscht haben Der Fall tauchte auf bei einem Scanline Algorithmus über ein Polygon, bei dem Schnittpunkte nach aufsteigender X-Koorindate zu sortieren waren. Die Anordnung der Schnittpunkte hat sich aber von einer Scanline zur nächsten im Regelfall nicht verändert und wenn dann haben höchstens 2 Schnittpunkte die Plätze getauscht. Das Sortieren war daher in Wirklichkeit eher ein Überprüfen ob die Reihenfolge noch stimmt und Vertauschen falls nicht. In einem Wort: Bubble-Sort mit vorzeitigem Abbruch.
Der Quantum Bogosort soll der beste sein des sortiert beliebig lange Listen in nur einem Schritt. Aber die Implementierung ist sehr knifflig :) MfG Michl
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.