mikrocontroller.net

Forum: PC-Programmierung Bester Sortieralgorithmus


Autor: Voltcraft (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Volker Zabe (vza)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo: qsort  (quicksort).
wird sogar mit jedem Kompiler mit ausgeliefert.
Nur noch benutzen.

ciao Volker

Autor: klaus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> wird sogar mit jedem Kompiler mit ausgeliefert.

Hm?

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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()).

Autor: Micha C. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

ein Blick in Wikipedia zeigt bereits ein paar Alternativen:

http://de.wikipedia.org/wiki/Sortierverfahren



Viel Spass

     Micha

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Aber da wird es dir gehen wie mir:
Mit Reichwerden wird das nix, andere sind da meistens schneller.

Autor: Claudio H. (bastelfinger)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
wenn er wirklich mit O(log n) läuft, kannst du damit reich werden.
Wahrhaft wunderbar.

Autor: Wolfgang Schmidt (wsm)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ 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!

Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Wolfgang Schmidt (wsm)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
".... leider ist der Rand im Forum hier zu klein,..... "

ist ein abgewandeltes Zitat von Fermat.

Wolfgang

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sollte man ändern, ja.

Ich eröffne die Petition "Forum mit breitem Rand für Sortieralgorithmen"

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Stefan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
In Hardware schaffe ich sogar O(1)...

Autor: Stefan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
...zeitlich gesehen

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Stefan schrieb:
> O(1) ...zeitlich gesehen

Beweis?

Ich meinte natürlich Zeitkomplexität...

Autor: Udo R. S. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Marvin S. (demo)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Marvin S. (demo)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ach, btw... was zum Teufel ist denn bitte Zeitkomplexitaet?! Das macht 
nichtmal intuitiv Sinn.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

   for( i = 0; i < n; ++i ) {
     for( j = 0; j < n; ++j ) {
       if( a[i] > a[j] )
         swap( &a[i], &a[j] );
     }
   }

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.

Autor: Marvin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 :) .

Autor: Algerier (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Claudio H. (bastelfinger)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hat die Promotion einen ausreichend breiten Rand?

Autor: Lehrmann Michael (ubimbo)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ?

Autor: Stephan M. (stephanm)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Wegstaben Verbuchsler (wegstabenverbuchsler)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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!

Autor: Stephan M. (stephanm)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: jo (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenns lineare Zeit sein muss dann doch lieber Radix-Sort

Autor: Genmutant (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Oder Bogo-Sort! :-P
Das ist mit etwas Glück auch O(1)

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
BWL-sort hat auch O(1):
"Morgen ist es garantiert fertig, egal wie viele Elemente es hat"

Autor: chris (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn du das meinst was ich glaube das du meinst, dann ist das immer noch 
O(n) und unter dem Namen Bucketsort bekannt.

Autor: Horst (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
O(0) mit Quantosort:
Es hat bereits die richtige Reihenfolge bis man hinschaut. Also bloß 
nicht anrühren.

Autor: Εrnst B✶ (ernst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ;)

Autor: Puppe (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Matthias N. (nippey)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ;)

Autor: Matthias (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Superschnell!
Zumindest bei ganz wenigen Elementen...

Autor: mh (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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).

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.
  sorted = false;

  while( ! sorted ) {

    GenerateRandomDistribution();

    for( int i = 0; i<Max; i++ )
      Sorted[randInt(Max)] = Unsorted[randInt(Max)];

    sorted = true;
    for( int i = 0; i<Max-1; i++ ) {
      if( !( Sorted[i] < Sorted[i+1] ) )
        sorted = false;
    }
  }

(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

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn eine Zahl nicht wiederholt vorkommen kann, ist es mit Zufall aber 
auch nicht soweit her....

Autor: mh (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
kbuchegg, Du hast Bogosort gefunden (nicht erfunden)!

Autor: Markus J. (markusj)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Claudio H. (bastelfinger)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Martin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Coole Jungs nehmen Bogosort - alles andere ist für Vorwärtseinparker.

Autor: Michl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Der Quantum Bogosort soll der beste sein des sortiert beliebig lange 
Listen in nur einem Schritt.
Aber die Implementierung ist sehr knifflig :)

MfG
Michl

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.