Bester Sortieralgorithmus

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()).

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!

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"

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.

Hat die Promotion einen ausreichend breiten Rand?

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

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.

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

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

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 ;)

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 ;)

Superschnell!
Zumindest bei ganz wenigen Elementen...

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.