Beiträge von JeeK im Thema „Sortieren in V2 BASIC“

    Jeek: geht nur, wenn Du aus der Fließkommazahl eine Dezimalzahl mit einer festen Anzahl Stellen machst und so sicherstellst, dass z. B. zwischen 0,010 und 0,011 genau 10 Werte liegen. Ansonsten hast Du da viel zu viele, um diese in einem Array abzubilden (wieviel Bit hat eine Fließkommazahl beim C64? Imho 32Bit).


    Nein, 40 Bit. 8 Bit Exponent, 4 Byte Mantisse.

    Natürlich nur eine Hash-Funktion, oder sagen wir besser allgemeiner Funktion notwendig, die die Ordnung erhält. ;)
    Wie Mac schon vorgeschlagen hat, scheint mir der Exponent ganz gut zu passen, speziell in der (für diesen Zweck auch beabsichtigten Exzessdarstellung). Wenn man Sign-Bit entsprechend behandelt und natürlich einbezieht (es wäre das signifikanteste Ordnungskriterium, noch vor dem Exponent, steckte aber im 1. Mantissenbit), kann man bei gleichem Exponent dann auch die Mantisse als weiteres Ordnungskriterium in der jeweiligen Exponenten-Klasse heranziehen.

    Also
    Übliche Grundvorausssetzung beim Countingsort: ich kenne alle vorkommenden Werte
    Ich sehe das Problem/die Grenze von Countingsort bei Fließkommazahlen aus dem Zufallsgenerator...


    Also Fließkommazahlen umfassen ja auch nur einen endlichen Zahlenraum, also nichts anders als Strings mit konstanter Länge. Da ķann man genauso mit einer Hash-Funktion einen definierten Zahlenbereich zu Grunde legen.

    Ich hab Shell-Sort mal abgetippt und bin positiv überrascht.
    Bei genauem Hingucken kann man sogar noch das if GOTO durch if then ersetzen.
    Dann kommt SHELL-Sort sogar ohne Sprünge aus, was das ganze noch etwas schneller machen sollte.
    [..]


    Richtig. Das war sozusagen der Trivialschritt, den ich den Lesern überlassen hatte und du dankenswerterweise aufgegriffen hast.


    Äh, nein. Je nach Distanzfolge entweder O(N·log²(N)) (<- man beachte das ^2) oder O(N^(1+ε)), wobei ε eine sehr kleine, aber von 0 verschiedene positive Zahl ist.
    [..]
    Es wird gemutmaßt, daß man mit einer geeigneten Distanzfolge tatsächlich eine Laufzeitordnung von O(N·log(N)) für Shellsort hinbekommen könnte - bislang ist man aber nicht fündig geworden.


    Richtig (wie man auch in der Wikipedia nachlesen kann ;) ), ich hab mich da fälschlicherweise zu der Behauptung hinreißen lassen, aber mir genügt auch dieses Verhalten - selbst mit meiner unoptimalen Distanz - für die in der Praxis vorkommenden Größenordnungen beim C64. Ich hatte in der Praxis bei realen Programmen kaum mehr als 1000 Elemente und wenn man sich aufs RAM beschränkt, wird man da auch kaum mehr als 65000 haben. Und damit (zumindest für mich) ausreichend praxistauglich, trotz aller theoretischer Betrachtungen. Da macht Quick- und Heapsort das Kraut nicht fett ... und hab mit Shell-Sort trotz diverser Bremser meinen Spaß. ^^

    Mit der Distanzfunktion D=INT(D/2)-1, also

    Code
    510 d=int(d/2)-1:ifd<=0thenreturn


    ist man bei 1000 Elementen gleich bei ca. 17000 Jiffies (vorher 19000).

    Shellsort ist interessant, mir aber für den Praxiseinsatz zu kompliziert. Wenn Insertion Sort nicht ausreicht, gehe ich direkt zum Heapsort über.


    Wirklich? Hast du dir mal die Listings angesehen? Wo Heapsort mit Unterprogrammen und Baumstrukture via Indizes herumjongliert, kommt Shellsort relativ klar mit 3 ineinander verschachtelten Schleifen aus. Gut, das Prinzip muss man sich auch mal auf der Zunge zergehen lassen. Ich hab den Algo. schon des öfteren in Assembler umgesetzt, was mir recht bequem vorkam. ^^

    Gibts tatsächlich keine Shellsort-Anhänger hier?


    Ja, schon. Ich persönlich bevorzuge diesen Algorithmus, weil einfach und auch N*log(N).

    Die Variante aus meinem Fundus (nicht wirklich extrem optimiert, man möge mir verzeihen):


    Bei der Anzahl von 10/100/1000 sind es rund 50/1100/19000 Jiffies.
    Also zwischen Heap und Quicksort anzusiedeln. In Anbetracht der Einfachheit und geringeren Abhängigkeit von der Struktur der zu sortierenden Daten für mich persönlich mein bevorzugtes Verfahren. :)

    Schön!

    Die Zeilen 15 bis 18 lassen sich aber schon etwas kompakter formulieren, wenn man ausnutzt, daß das NEXT einer äußeren Schleife mit explizit benannter Laufvariable alle offenen inneren Schleifen vom Stapel entfernt. :)


    Sind jetzt alle aufgewacht oder erst jetzt in den Thread eingestiegen, dass jetzt das bereits im Wesentlichen in Bitte melde dich an, um diesen Link zu sehen. behandelte wieder aufgewärmt wird? Fein ist aber freilich, dass es hier noch einen weiteren Schliff erhalten hat (das hässliche GOTO durch Umdrehen der Vergleichsbedingung weg optimiert :thumbsup: ).

    Da in diesem Thread so oft der Bubble Sort erwähnt wurde, konnte ich nicht anders und hab hier zum Vergleich einen Insertion Sort gebaut:
    [..]
    Zur Erklärung: Selbst unter den naiven Sortieralgorithmen mit Komplexität O(n²) gilt der Bubble Sort eigentlich als das Standardbeispiel für einen schlechten Sortieralgorithmus, z.B. wegen der vielen unnötigen Schreibzugriffe auf das Array. Insertion Sort ist auch nicht schwieriger zu verstehen, aber immer schneller in der Ausführung. Ich nehme an, dass BIFs Programm eigentlich ein Insertion Sort sein/werden sollte, und Cyberdynes Ausführungen zu seinem "verbesserten Bubblesort" klingen auch sehr nach Insertion Sort.

    Die Funktionsweise: Man unterteilt das Array gedanklich in einen sortierten und einen unsortierten Teil. Am Anfang umfasst der sortierte Teil einfach das erste Element und der unsortierte den Rest.
    [..]


    Hatten wird doch schon schon alles, siehe Bitte melde dich an, um diesen Link zu sehen. ... oder? ;)

    Eigentlich weiß ich das ja, aber trotzdem waren die Unterschiede größer und z. T. auch anders als ich es erwartet hatte. Das erste Aha-Erlebnis war Quicksort vs. Heapsort. Ich hatte schon öfter gelesen und auch schon gesehen, dass Quicksort im Worst-Case zu O(n²) neigt und Heapsort mit seinem Worst-Case O(nlogn) deshalb im Vorteil ist. Aber wenn ich mir die Ergebnisse hier im Vergleich anschaue... klar, beim Heapsort hier können noch paar Prozente rausgeholt werden, aber Quicksort ist in einer anderen Region. Und dann kommt noch der popelige O(n²)-Selection Sort hinzu, der bei 100 Elementen dichter an Heapsort ist, als Heapsort an Quicksort.


    Hab mal beim Heapsort alles auf FOR-NEXT umgestellt, X*2 auf X+X, aber da holt man bei N=100 auch nur so 80-100 Jiffies heraus, bei 1000 sind es dann auch schon 1000 Jiffies.
    Die zuvor genannten Werte für Quicksort konnte ich nicht nachvollziehen - kommen mir zu niedrig vor. Bei N=100 ist Quicksort bei rund 1000 und Heapsort bei 2000. Faktor 2, der Faktor bleibt auch bei 1000. Es gibt wahrscheinlich etliche theoretische Abhandlungen dazu, aber gefühlsmäßig ist das für mich irgendwie plausibel, wenn gewissermaßen Heapsort das in 2 Schritten, die irgendwie bei N*LOG(N) angesiedelt sind, durchführt.

    Also, ist Q-Sort tatsächlich das schnellste ?


    Nein, bewiesenermaßen ist Fächersortierung optimal, hat aber Eigenschaften, die es für den praktischen Einsatz oft ungeeignet macht.


    Wie mein Programm hier gezeigt hat ist das nicht immer der Fall, da es natürlich verschiedene Sortierfälle gibt.
    Wie z.B. den Einfüg-Fall.


    Das ist kein Sortieren. Einfügen in bestehende (bereits sortierte) Daten ist nur ein Teilaspekt davon.


    Was ich hier mal anmerken möchte.
    Und ohne Ausschalten der GBC kann Q-Sort natürlich in der GBC steckenbleiben, wo beispielsweise Selection-Sort noch weiter arbeitet. Da hätte man natürlich das Problem des noch freien Speichers.


    Bitte nicht nochmal diese Diskussion :zzz:
    Wurde nicht schon erwähnt, dass wir hier keine Strings sortieren? Außerdem tut das hier überhaupt nichts zur Sache.
    Abgesehen davon: Bei In-Place-Sortierungen, sollte man ohnehin jede Vertauschung mit Stringdescriptoren-Tausch arbeiten (wenn jemand wirklich ernsthaft das im Basic-Umfeld nutzt, sollte hier ohnehin auf eine Assembler-Routine ausweichen). Das ist GC-Neutral.

    Theoretisier, theoretisier,

    Was hier wohl nicht beachtet wird, ist, daß es möglicherweise noch schnellere Sortierprogramme gibt.
    Offenbar sowohl auf Heap-Sort, Selection-Sort und Einfueg-Sort Basis.

    Schönen Gruß.


    Aber natürlich, haben die im Dritten Reich schon erfunden gehabt und damit wird in der Hohlwelt bis heute gearbeitet! ;)
    Um es mit Dr. Axel Stolls Worten zu sagen: Weiß man doch!

    z. B. um bei Kursteilnehmern die Spreu vom Weizen zu trennen :bgdev

    Aktuell finde ich es ja spannend, wie wenig die Komplexitiätsklasse (O(n²), O(nlogn) etc.) über die tatsächliche Geschwindigkeit des Algorithmus aussagt (keine Sorge, ich weiß, dass die Werte hier nur für das CBM-Basic gelten).


    Ist ja per Definition so, oder? (oder ich versteh die geäußerte Feststellung irgendwie nicht)
    Die Komplexitätsklasse hängt hängt ja nicht von der Implementierungssprache ab (es sei denn Operationen dort tragen dazu etwas bei - das wäre dann einzubeziehen). Die Komplexitätsklasse sagt ja generell nichts über die tatsächlich Geschwindigkeit aus. Soll sie ja auch nicht, sondern einen Hinweis geben, welcher "Sprung" zu erwarten ist, sagen wir bei einem Schritt von 100 auf 1000 Elementen usw.

    Man kann könnte ja die Abschätzung ja genauer angeben. Auch wenn Bubble und Selection quadratischer Ordnung sind, dann neigt Bubble zu N*N, Selection zu N*(N-1)/2, was freilich auch von der Beschaffenheit der Daten abhängt. Oder für den Worst-Case eben, als obere Grenze.

    Also bei allen Beispielen hier sieht man doch gut, dass die Klassen stimmen und die Algorithmen in der gleichen Klasse auch nur um einen mehr oder weniger konstanten Faktor auseinander liegen. Das liegt zum einen Teil am konkreten Algorithmus aber auch an der Implementierung. Solange es Rückwärts-GOTOs gibt, sind die Werte auch nicht seriös vergleichbar, speziell bei einem Programm, wo alle Implementierungen in einem Programm enthalten sind, also ein dahinter liegendes somit benachteiligt wird. Generell gehört jedes Rückwärts-GOTO durch ein FOR-NEXT ersetzt (zumindest fürs Vergleichen konkreter Werte). Für die Darstellung der Implementierung ist das GOTO sicher hübscher und eingängiger. ;)

    Nennt mich pingelig, aber Einfügen passt beim Heapaufbau nicht so richtig. Den Heapaufbau betreibe ich doch über den Gesamtbestand der Daten, vom letzten Knoten beginnend nach vorne - da kommt nix mehr zum Einfügen hinzu. Beim Korrigieren des Knotens wird auch nicht eingefügt, sondern mit dem größten Kindelement getauscht (sag ich mal so aus dem Kopf).


    Das korrigieren des Heaps nach dem Wegtauschen des "obersten Elementes" ist gewissermaßen das Einfügen eines neuen Wertes in den (verbleibenden ) Heap. Egal wie man es dann tatsächlich gebraucht und wie auch immer man dann das "Einordnen" in die Heap-Struktur bezeichnen will. Den Heap als Datenstruktur gibt es ja für verschiedene Zwecke. ;)

    Und wie kombinierst Du die doppelt verkettete Liste mit binärer Suche?


    Ja, das war zu kurz gedacht. Verkettete Listen eignen sich freilich für das arraybasierte binäre Suchen nicht, ohne die Listen selbst wieder mit einer Metadatenstruktur zu versehen ... da hat man dann schnell bei sowas wie Skip-Listen, einem binären Baum oder hat dann eine Baumstruktur auf ein Array abgebildet, was wie schon angesprochen zum Heap führt.
    Die billige Einfügeoperation war einfach zu verführerisch, hat aber wirklich nicht mit binärem Suchen zu tun. Blödes, unpassendes Beispiel. :(

    Mike: Die Einfügeoperation beim Heap ist O(1)? Was genau ist damit gemeint, die Schreibaktion ins Array? Ich hätte das als "ein Element zum Heap ergänzen" also das "Versickern" angesehen und diese "kostet" doch log(N) Schritte, um die Heap-Struktur zu reorganisieren, oder? Egal, das sind nur die Begrifflichkeiten, ist ja sonst schon klar. ;)

    JeeK: Neee, den Code ziehe ich mir nicht an - das ist noch die BIFF-Logik, samt Doppelpunkten. Ist nur angepasst, damit es in das restliche Gerüst reinpasst. Aber was Du daraus gemacht hast - Hut ab.


    Danke. ^^


    Neugierig wie ich bin hab' ich dann gleich die binäre Suche umgesetzt (oder es zumindest versucht):


    Hihi, ich hab's mir ja fast gedacht ... mir war die Nacht schon zu kurz, um es selbst auszuarbeiten.


    ...
    Sieht so aus, als ob die binäre Suche in Basic zuviel Overhead verursacht - was die Ersparnis bei den Iterationen auffrisst.


    Naja, auch, aber eher: Eine binäre Suche an sich wäre ja schon schnell (bei 1000 liegt ja schon fast ein Faktor 100 dazwischen), trotz all dem Basic-Overhead. Nur der Vorteil verpufft gleich wieder, weil für die Einfügeoperation die Stapelwerte ab der Einfügeposition wegen der Array-Organisation in eine Richtung linear durchgehend verschoben werden müssen. Das ist das, was in der Variante ohne binäre Suche beim linearen Durchsuchen einfach "nebenbei" passiert. D.h. die binäre Suche hat damit zu kämpfen, dass eine "weit entfernte" Einfügeposition (die schneller erreicht wurde - O(logN)-Aufwand) mit dann besonders vielen Verschiebungen O(N)-Aufwand bestraft wird. Das ist echt gemein. X(
    Anders gesagt: Die binäre Suche bringt nur dann etwas, wenn die Element z.B. in einer doppelt verketteten Liste organisiert sind, wo das Einfügen O(1) also quasi konstant, ohne großes Herumgeschiebe, machbar ist.
    Mich wunderts eigentlich, dass es mit der binären Suche nicht sogar länger braucht. :S


    Nachtrag: evtl. bietet sich ein hybrides Verfahren a: wenn der zu durchsuchende Bereich >x Elemente hat, fange binär an und wechsle zu iterativ, wenn die Spanne <=x wird.


    Wenn es sich um Arrays handelt, dann bringt m.E. die binäre Suche generell nicht wirklich viel, wenn nicht das Gegenteil. Nur wenn die Einfügeoperation nicht mit Aufwand O(N), also z.B. bei einer doppelt verketteten LIste nur O(1) hat.

    Damit bleibt der Aufwand insgesamt fürs Sortieren bei Array also O(N^2). Das ist mir auch jetzt erst nach genauerem Überlegen, speziell aufgrund deiner Messung klar geworden.


    ...
    Coole Idee, bastel ich doch gleich mal in das Programm rein, mit Anpassung für den Arraybereich von 0 bis 10:

    Was daran "cool" entzieht sich meiner Wahrnehmung. Das Einsortieren eines Wertes in einen sortierten Stapel ist in der linearen Implementierung auch nicht anders machbar. Wenn wenigstens das Einsortieren per binärer Suche vorgestellt worden wäre, aber selbst das gehört zu den nicht erwähnenswerten Standardalgorithmen in der Informatik.
    Das hat ja wirklich erstmal nichts mit Sortieren an sich nichts zu tun, außer das die Einfügeoperation von der Sortierung des "Stapels" profitiert.
    Der eigentliche Sortieralgorithmus hat dann in der Tat Tale-X zusammengebastelt ... also eigentlich Tale-X'es Einfueg-Sort!


    Array b brauche ich, damit das Ergebnis nachher Stück für Stück in ein leeres Array a reingesetzt werden kann. Der Fairness halber wird die Zeitmessung auch erst danach gestartet. Ansonsten dürfte ich das Wesen des Ausgangscodes gut aufgegriffen haben.


    Das Sortieren geht in dieser Form leider von recht vielen Voraussetzungen aus und macht mehr als notwendig.

    • Stillschweigend wird ein Minimum von 0 vorausgesetzt. D.h. die zu sortierenden Werte müssen >=0 sein.
    • Der Stapel, in den einsortiert wird, umfasst hier von Beginn immer mit N Elemente und muss daher mit "Minimumwerten" vorgefüllt sein. Es reicht hier den Stapel nach und nach aufzufüllen.
    • Unfairerweise ist die "innere" Schleife eine GOTO-Schleife (mit bekanntem schlechten Laufzeitverhalten) und daher zumindest im Vergleich zum Selection-Sort, wo FOR-NEXT in der inneren Schleife seine Vorteile ausspielt.


    Bei 6 Elementen:
    b12345 a12345
    654321 000000
    654321 000006
    654321 000056
    654321 000456
    654321 003456
    654321 023456
    654321 123456

    Hier sieht man, dass von Beginn an die Werte (die Nullen) von "vorne" durchgeschoben werden, nur damit die größeren Werte ans Ende des Arrays einsortiert werden. Eine sehr ungünstige Grundinitialisierung für den Stapel.

    Was sagen die Zahlen?

    Code
    Einfueg-Sort
    
    
       N  Lauf 1 Lauf 2 Lauf 3 Lauf 4 Lauf 5
    
    
      10    131    148    137    122    142
     100  10810  10390  11146  10675  10970
    1000  nicht getestet

    Ich glaub', ich bleib da lieber bei nem anderen Sort... obwohl, bei N=10 hat er fast QuickHeapsort-Niveau.

    Ein von mir korrigierte Variante zeigt sich da schon freundlicher (dabei mit der Initialisierung von B() gemessen!):

    Code
    N  Lauf 1  Lauf 2  Lauf 3  Lauf 4  Lauf 5
    
    
      10      36      38      52      45      47
     100    2516    2184    2394    2125    2505
    1000  225843  221826  223335 .....

    Also bei N=10 unter Quicksort- und sogar Selection-Sort-Niveau.
    Auch bei 100 noch auf Heap-Sort-Niveau, aber immer wieder deutliche Schwankungen.
    Bei 1000 noch immer unter Selection-Sort, aber als quadratischer Algorithmus gegenüber den logarithmischen dann schon deutlich hinten.
    Unter der Voraussetzung, dass hier noch ein 2. Array gleicher Größe gebraucht wird, schränkt sich der Gebrauch dieser Variante ziemlich ein.

    Als Fleißaufgabe, kann man das Stapeleinsortieren mit binärer Suche machen und müsste dann in die Region von Quicksort und Heap-Sort kommen (Aufwand O(N*logN)). Das sei dem geneigten Leser überlassen. ;)

    Meine Variante (mit linearem Einfügen) sieht nun so aus:

    Code
    30 dimb(n):fori=0ton:b(i)=a(i):next:t1=t1:rem startzeit korrigieren
       31 fort=1ton:a=b(t)
       32 fori=t-1to.step-1:ifa>=a(i)then34
       33 a(i+1)=a(i):next
       34 a(i+1)=a:next t:return


    Einige Bemerkungen dazu:

    • Gültig für n>=1 (also ab 2 Elementen).
    • Die Zeitnehmung beginnt also schon vorher, regulär (die T1-Zuweisung ist nur ein Dummy).
    • Es braucht kein Minimum angelegt werden - a() enthält wir schrittweise aufgebaut, nur a(0) wird initial übernommen (auch wenn alle weiteren Elemente unverändert bleiben, sie werden jedoch der Reihe nach überschrieben).
    • Das Verlassen der inneren FOR-NEXT-Schleife beim NEXT endet mit dem Wert -1 in i.
    • Die innere Schleife ist nun ein FOR-NEXT (also vergleichbar mit Selection-Sort)
    • Der Abbruch der inneren Schleife in Zeile 32 mit Sprung auf Z. 34 ist kein Problem, da NEXT T (mit expliziter Laufvariable) die offene innere Schleife beseitigt! Also keine Ausnutzung eines zufälligen Verhaltens, sondern eine reguläre Eigenschaft des Interpreters.


    Sortierablauf für 6 Elemente:
    b12345 a12345
    6(5)4321 6XXXXX
    65(4)321 56XXXX
    654(3)21 456XXX
    6543(2)1 3456XX
    65432(1) 23456X
    654321() 123456

    X sind nicht verwendet, Wert in () wird einsortiert.

    Ich muss mal schauen, ob ich den Fehler auch im angehängten Programm drin habe - bei mir waren die Ergebnisse sortiert. Irgendwie schaffe ich es immer wieder, das der Code im Notepad kleine Unterschiede zu dem in Vice hat... :schande: immerhin hab ich diesmal die Ergebnisausgabe nicht auskommentiert :whistling:


    Im sort4.prg war es auch ... :(

    Code
    70 rem ** selection sort 
    71 ifr<=lthenreturn 
    72 forx=ltor-1:m=x:fory=x+1tor:ifa(m)>a(y)thenm=x 
    73 next:ifm<>xthens=a(m):a(m)=a(x):a(x)=s 
    74 next:return


    Da hat sich ein Bug eingeschlichen: Es muss
    72 forx=ltor-1:m=x:fory=x+1tor:ifa(m)>a(y)thenm=y
    Sonst rutscht das gefundene Minimum nie nach unten, d.h. weil sonst x=m gilt, käme es nie zu einer Vertauschung. ;)
    Damit verlängert sich dann freilich auch die Laufzeit.

    Der Aufwand gegenüber Bubble ( (n-1)*(n-1) ) ist mit (n-1)*(n-2)/2 zumindest im Worst-Case geringer, aber es hat immer gleich viele Durchläufe, wenn auch nur n-1 Vertauschungen (bei Bubble meist viel mehr). Es profitiert damit kaum von einer Vorsortierung. Das dann praktisch, wenn
    die Vertauschungsoperation aufwändig ist oder überhaupt nicht so einfach geht (weil die Elementgröße verschieden sind). Typisch: Der Stringheap des Basic-Interpreters. Dort kommt auch quasi ein Selection-Sort zum Einsatz: Die Garbage-Collection ist genau das. Dort ist allerdings das Kriterium, jenen aktiven String mit der höchsten Adresse nach oben zu sortieren (um diesen dann über Lücken hinweg ganz nach oben zu schieben). Da sind Elementvertauschungen ala Bubble ziemlich unpraktisch (bzw. unmöglich). ;)

    Noch eine kleine Syntax-Erklärung für Anfänger die hier mitlesen zu Mike's Bubblesort-Urcode:

    Code
    10 n=10:dimx(n):fort=1ton:x(t)=rnd(1):next
    11 :
    12 p=0:fort=1ton-1:ifx(t)>x(t+1)thenx=x(t):x(t)=x(t+1):x(t+1)=x:p=-1
    13 next:ifpthen12
    14 :
    15 fort=1ton:printx(t):next


    [..]
    if p then 12 heißt wenn p = 0 dann 12. Man hätte auch schreiben können if p=0 then 12.
    [..]

    Vielleicht nur ein gedanklicher Ausrutscher, aber die Bedingung ist erfüllt, wenn p<>0 (ungleich 0) ist!
    D.h. die Ersatzschreibweise ist

    Code
    if p<>0 then12


    D.h. es wird hier sogar ganz sauber das Basic "true" (-1) verwendet, im konkreten Fall und so wie CBM-Basic das IF-THEN implementieren würde aber auch jeder Wert ungleich 0 reichen. ;)

    [..]

    Wie geschrieben, hatte ich das alles schon gemacht. Ich habe auch nie behauptet, dass man für die Highscoreliste einen besseren Bubblesort braucht. Es ging nur um die Vor- und Nachteile der Sorter und da stellt sich halt raus, dass der Quicksort in einigen Bereichen viel schneller ist aber in einigen Bereichen auch deutlich langsamer. Und genau in den Bereichen kann man den Bubblesort auch noch ganz einfach und schnell deutlich optimieren. Für die Highscoreliste würde ich den originalen Bubblesort auch anpassen, weil man bei einem neuen Score auch nur ein Durchlauf nötig ist. Ein weiterer Durchlauf wäre einfach Zeitverschwendung.
    [..]


    Im Übrigen finde ich Highscores sortieren ohnehin mit Kanonen auf Spatzen geschossen (also eigentlich keine wirkliche Aufgabe für einen Sortieralgorithmus).
    Geht man davon aus, dass die Highscore-Liste bereits sortiert ist, dann reduziert sich die Aufgabe ja auf das Einfügen eines neuen Wertes. Das Suchen der richtigen Position geht dann mit binärem Suchen in den Aufwand O(log N), das Einfügen variiert ja nach Datenstruktur von O(1) bis O(N). D.h. ein Bubble-Sort verkommt ohnehin nur zu einer Schleife, die genau einen "Bubble" (den neuen Highscore) mit im Schnitt N/2 Vertauschungen an den richtigen Platz bringt. ;)