Forum: PC-Programmierung Bester Sortieralgorithmus


von Voltcraft (Gast)


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?

von Volker Z. (vza)


Lesenswert?

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

ciao Volker

von klaus (Gast)


Lesenswert?

> wird sogar mit jedem Kompiler mit ausgeliefert.

Hm?

von Klaus W. (mfgkw)


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

von Micha C. (Gast)


Lesenswert?

Hallo,

ein Blick in Wikipedia zeigt bereits ein paar Alternativen:

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



Viel Spass

     Micha

von Klaus W. (mfgkw)


Lesenswert?

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

von Claudio H. (bastelfinger)


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.

von Klaus W. (mfgkw)


Lesenswert?

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

von Wolfgang S. (wsm)


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.

von Klaus W. (mfgkw)


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!

von Sven P. (Gast)


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.

von Karl H. (kbuchegg)


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.

von Wolfgang S. (wsm)


Lesenswert?

".... leider ist der Rand im Forum hier zu klein,..... "

ist ein abgewandeltes Zitat von Fermat.

Wolfgang

von Klaus W. (mfgkw)


Lesenswert?

Sollte man ändern, ja.

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

von D. I. (Gast)


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

von Stefan (Gast)


Lesenswert?

In Hardware schaffe ich sogar O(1)...

von Stefan (Gast)


Lesenswert?

...zeitlich gesehen

von D. I. (Gast)


Lesenswert?

Stefan schrieb:
> O(1) ...zeitlich gesehen

Beweis?

Ich meinte natürlich Zeitkomplexität...

von Udo R. S. (Gast)


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.

von Rolf Magnus (Gast)


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.

von Läubi .. (laeubi) Benutzerseite


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.

von Karl H. (kbuchegg)


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.

von Marvin S. (demo)


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.

von Marvin S. (demo)


Lesenswert?

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

von Karl H. (kbuchegg)


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

von Marvin (Gast)


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

von Algerier (Gast)


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.

von Claudio H. (bastelfinger)


Lesenswert?

Hat die Promotion einen ausreichend breiten Rand?

von Lehrmann M. (ubimbo)


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 ?

von Stephan M. (stephanm)


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.

von Wegstaben V. (wegstabenverbuchsler)


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!

von Stephan M. (stephanm)


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

von jo (Gast)


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.

von D. I. (Gast)


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

von Klaus W. (mfgkw)


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.

von D. I. (Gast)


Lesenswert?

Wenns lineare Zeit sein muss dann doch lieber Radix-Sort

von Genmutant (Gast)


Lesenswert?

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

von D. I. (Gast)


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.

von Klaus W. (mfgkw)


Lesenswert?

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

von chris (Gast)


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.

von Karl H. (kbuchegg)


Lesenswert?

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

von Horst (Gast)


Lesenswert?

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

von Εrnst B. (ernst)


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

von Puppe (Gast)


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.

von Matthias N. (nippey)


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

von Matthias (Gast)


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?

von Klaus W. (mfgkw)


Lesenswert?

Superschnell!
Zumindest bei ganz wenigen Elementen...

von mh (Gast)


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

von Karl H. (kbuchegg)


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

von Klaus W. (mfgkw)


Lesenswert?

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

von mh (Gast)


Lesenswert?

kbuchegg, Du hast Bogosort gefunden (nicht erfunden)!

von Markus J. (markusj)


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

von Claudio H. (bastelfinger)


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.

von Karl H. (kbuchegg)


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.

von Martin (Gast)


Lesenswert?

Coole Jungs nehmen Bogosort - alles andere ist für Vorwärtseinparker.

von Michl (Gast)


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

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
Noch kein Account? Hier anmelden.