Beiträge von Tale-X im Thema „Sortieren in V2 BASIC“

    So richtig geistig durchdringen kann ich es nicht - kämpfe gerade mit nem Virus (da sowohl Raspi als auch C128 immun gegen Viren sind, war ich wohl das naheliegendste Opfer). McBacons Variante ist nen Tick schneller: Bitte melde dich an, um diesen Link zu sehen. (also 21000 gegen 22000 Jiffies)

    Um mit Quicksort mithalten zu können müssten 66% Einsparung erzielt werden.

    Es ist (nur) eine C64-Besonderheit, die da ausgenutzt wird. Durch 0*a(.) wird dafür gesorgt, dass der Variablenzeiger in Speicheradresse 71, 72 (enthält die Adresse der zuletzt verwendeten Variable) auf das Array a()-zeigt (weil 0*a(.) zuletzt berechnet wurde). Und mit den Werten aus 71 und 72 wird dann der Zeiger ausgerechnet.

    Nachtrag: Speicheradressen sind jetzt korrigiert...

    @MacBacon: Nicht so pessimistisch... ich grübel gerade über den Abschnitt b = (n / 2) + 1 in Zeile 100. Funktioniert das so zuverlässig oder sollte da nicht lieber b=int(n/2)+1 stehen? Bei n=1 ergibt sich b=1.5 und erfüllt in Zeile 104 nicht die if-Bedingung.

    Das Konstrukt sorgt dafür, dass in 71 und 72 die Adresse von Array a steht. Damit haben wir jetzt Variablenzeiger in Basic... Mathematisch hat es (absichtlich) keine Auswirkung auf das Ergebnis. Das Ganze ist mir aber auch erst 2-3 Antworten später aufgefallen.

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

    Also wenn ich mir den groben Ablauf von Bucket Sort auf Wikipedia anschaue, dann kann ich so ziemlich alles mit sortieren:

    • Verteilung der Elemente auf die Buckets (Partitionierung)
    • Jeder Bucket wird mit einem weiteren Sortierverfahren wie beispielsweise Bitte melde dich an, um diesen Link zu sehen. sortiert.
    • Der Inhalt der sortierten Buckets wird Bitte melde dich an, um diesen Link zu sehen..

    Anders beim verwandten Countingsort, der hier gerade zum Einsatz kommt - ABER: wenn Du es schaffst, die Strings effizient in ein Array abzubilden, dann kannst Du auch Strings mit sortieren. Mein Ansatz wäre da: ein Array, in dem die Strings in ihrer Zielreihenfolge vorkommen ((0)="Sehr gut", (1)="Gut", (2)="Befriedigend"...), ein gleichgroßes Array für die Anzahl der Vorkommnisse und dazu ein Mapping (z. B. HashMap), dass für einen String den Index zurückliefert. Und dann kann ich die Strings durchgehen, zählen und sortiert ausgeben.

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

    Sehr schön! Die Geschwindigkeit ist beeindruckend - bei 1000 Elementen entweder 1860 Jiffies bzw. 2142. Quicksort benötigt da das 6fache an Zeit (sortiert im Gegenzug dafür alles, was vergleichbar ist).

    Die Ähnlichkeit war mir nicht entgangen, auch wenn die Variante sehr speziell ist :) Der Charme des Verfahrens kommt dann so richtig zum tragen, wenn die Anzahl der Werte größer ist als die Menge der Werte. Also 49 aus 6 statt 6 aus 49.

    Oder von den oberen Zehntausend - wie der Cocktailsort, der ein Hauch spritziger ist als der gewöhnliche Bubblesort.

    Und dann noch der Shellsort, naja, der Name sagts schon - wird garantiert von Greenpeace boykottiert.

    Ich bin bekennender Heapsort- und Counting-Sort Fan. In ner ruhigen Minute (eher ruhigen Monat) will ich mir mal den Smoothsort anschauen. Aber Shellsort... *schulterzuck* wie schlägt der sich denn so in Basic V2?

    Im Großen und Ganzen bin ich Deiner Meinung. Einschränkung: bei zwei Algorithmen der gleichen Laufzeitklasse speziell Heap- und Quicksort ist es für mich jedoch schon interessant, wie sie im direkten Vergleich abschneiden (ich weiß absolut nicht, ob und wieviel schneller das Basic eines VC20 im Vergleich zu dem eines C64 ist - auch wenn Vice mit VC20 nur 3 Mausklicks entfernt ist). Wenn die Randbedingungen gleich sind, ist der Rest (Bildschirmanzeige, Sprites) für mich hier egal - solange auch die gleich sind.

    Der Bubblesort - richtig abgewandelt - hat beim Highscore den Charme, dass er bei seiner Arbeit dargestellt werden kann und dem Spieler zeigt, wie er von hinten beginnend zu seiner Position vorgeschoben wird. Das bieten die anderen nicht.

    Das (zweite) Lottobeispiel gefällt mir, aast zwar etwas mit dem Speicherplatz (200 Bytes für 6 Werte), ist aber gut verständlich und vor allem sicher vor Flüchtigkeitsfehlern beim Programmieren :whistling:

    Ja, Quicksort für große Datenmengen. Wenn Du was schnelleres kennst - immer raus damit, ich bin ganz Ohr (und sicher auch die anderen). Randbedingung: die Elemente sind Fließkommazahlen. Ohne die würde ich noch den Counting Sort in den Ring werfen.

    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.

    ... Den Heap als Datenstruktur gibt es ja für verschiedene Zwecke. ;)

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