Sortieren in V2 BASIC

Es gibt 150 Antworten in diesem Thema, welches 27.067 mal aufgerufen wurde. Der letzte Beitrag (26. Dezember 2015 um 13:42) ist von BlackJack.

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

    Wissen ist das einzige Gut, das sich beim Teilen vermehrt. Also seid vorsichtig damit!

  • Hier mal beide Verfahren gut verständlich erklärt.

    Bitte melde dich an, um diesen Link zu sehen.

    Bitte melde dich an, um diesen Link zu sehen.

    Es ist praktisch unmöglich, ein schnelles Programm zu schreiben, wenn man es in Basic programmiert.

  • Hier mal beide Verfahren gut verständlich erklärt.

    Bitte melde dich an, um diesen Link zu sehen.

    Bitte melde dich an, um diesen Link zu sehen.


    Danke....sehr gute Erklärung! :ilikeit:

    ___________________________________________________________
    Meine Kreationen: Bitte melde dich an, um diesen Link zu sehen. | Bitte melde dich an, um diesen Link zu sehen. | Bitte melde dich an, um diesen Link zu sehen. | Bitte melde dich an, um diesen Link zu sehen.
    | Bitte melde dich an, um diesen Link zu sehen.
    Avatar: Copyright 2017 by Saiki

  • Hier mal beide Verfahren gut verständlich erklärt.

    Bitte melde dich an, um diesen Link zu sehen.

    Bitte melde dich an, um diesen Link zu sehen.


    Also, es tut mir leid, aber das, was da als "Bucketsort" in dem Video verkauft wird, ist nichts anderes als ein reinrassiger Radixsort.

    Die Bezeichnung Bucketsort holt sich ihre Berechtigung schon daher, daß die Elemente wie "Tropfen" in einem zugehörigen Eimer gesammelt werden, und man daher eben nicht mehr weiß, woher sie kamen und ob sie sich noch irgendwie unterscheiden. Wenn einem das Eimerbild zu wenig akademisch vorkommt, kann man ja gerne den Zählvorgang zur Namensgebung bemühen, aber warum dann Countingsort und nicht gleich "Countsort"?

    Leicht ins Off-Topic abgleitend: genauso ist mir vor ein paar Jahren der Begriff "Code-Reflection" untergekommen. Damit ist wohl eigentlich wahlweise selbstmodifizierender oder dynamisch erzeugter Code gemeint. Eine viel nahelegendere Nutzung des Begriffs, nämlich, daß ein wie auch immer geartetes Programm introspektiv seinen eigenen Code überschaut, um festzustellen was es da eigentlich tut (aus welchem Grund und mit welchem Erfolg auch immer) wird durch so eine Neubelegung nur erschwert. Neusprech haben wir ohnehin schon genug.

  • Zitat von Tale-X

    Sehr schön! Die Geschwindigkeit ist beeindruckend [...]


    Allerdings hab' ich hier auch schon darauf geachtet, daß möglichst wenig Index-Arithmetik stattfindet. Ansonsten ließe die Routine nämlich schnell ein paar hundert Jiffies liegen.

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

  • Hashes bringen imho aber die innere Ordnung durcheinander. Es bringt nichts, Zahlen nach ihrer Quersumme zu sortieren.

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

    Wissen ist das einzige Gut, das sich beim Teilen vermehrt. Also seid vorsichtig damit!

  • Hashes bringen imho aber die innere Ordnung durcheinander. Es bringt nichts, Zahlen nach ihrer Quersumme zu sortieren.

    Dann nimmt man halt das Exponenten-Byte als Hash... :whistling:

    Yes, I'm the guy responsible for the Bitte melde dich an, um diesen Link zu sehen. cross assembler. And some Bitte melde dich an, um diesen Link zu sehen..

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

  • Bleibt noch das Problem, dass der Hash nicht eindeutig ist - zum Zählen brauchst Du aber ein eindeutiges Mapping zum Array, in welchem Du die Vorkommnisse zählst.

    Wissen ist das einzige Gut, das sich beim Teilen vermehrt. Also seid vorsichtig damit!

  • Also das erste Zeichen eines Strings oder ein leicht veränderter Exponent einer Fließkommazahl würde ich jetzt nicht Hash nennen wollen. Ging ja los mit einem Counting-Sort, der alle Werte kennen soll. Für einen Bucket- oder Radixsort mag dieser Hash zwar sehr gut sein, aber zum Zählen aller Werte wohl doch nicht. Eine Tabelle mit 40Bit Index wäre selbst am PC ein bisschen arg viel.

  • Die Bitte melde dich an, um diesen Link zu sehen. (Sound!) gab's in diesem Thread noch nicht?

    Bitte melde dich an, um diesen Link zu sehen. - Bitte melde dich an, um diesen Link zu sehen.

  • Die Bitte melde dich an, um diesen Link zu sehen. (Sound!) gab's in diesem Thread noch nicht?


    Nee, aber hier schon: Bitte melde dich an, um diesen Link zu sehen.

    Bitte melde dich an, um diesen Anhang zu sehen. :verehr: .: Mit Bitte melde dich an, um dieses Bild zu sehen.wäre das nicht passiert! :. :prof:  Bitte melde dich an, um diesen Anhang zu sehen.

    :syshack: .: Meine 3D-Drucker Teile auf :. Bitte melde dich an, um diesen Link zu sehen. :strom:

  • Ich hab mir den Film mit den Sortieralgorithmen gleich zweimal angesehen.
    Sehr interessant und anschaulich gemacht.

    Sortier-Programme sind ja ein interessantes Programmierfeld, bei dem man manche Stunde verbringen kann.

    Und der Thread hat ja sogar zu zwei oder drei schnelleren Sortier-Programmen geführt.

    Da mußte ich gar nicht mal beweisen, daß es ein schnelleres Einfüg-Sort oder Selection-Sort gibt.

    Schönen Gruß.

  • Ach, auch andere haben dort noch nach Einsendeschluß ihre verbesserten Algorithmen und Implementierungen derselben vorgestellt. Von daher: nur Mut!

    btw., warum schreibst du Einfüg-Sort (deutsch/englisch)? ich kenne das nur unter dem englischen Begriff "Insertion-Sort." bei der ASM-Compo habe ich zufällig mit einem Insertion-Sort teilgenommen, deswegen frage ich.

  • btw., warum schreibst du Einfüg-Sort (deutsch/englisch)? ich kenne das nur unter dem englischen Begriff "Insertion-Sort." bei der ASM-Compo habe ich zufällig mit einem Insertion-Sort teilgenommen, deswegen frage ich.


    Wecke nicht den schlafenden Troll

  • Und der Thread hat ja sogar zu zwei oder drei schnelleren Sortier-Programmen geführt.

    Da mußte ich gar nicht mal beweisen, daß es ein schnelleres Einfüg-Sort oder Selection-Sort gibt.


    Oh, auf deinen 'Beweis' wäre ich gespannt gewesen, denn bislang kam von Dir nur (wie leider üblich) halbgares Gefrickel (einfügen in eine vorsortierte Liste, verkauft als Sortieren, ignorieren der Vorgaben (es ging um Zahlen, nicht um Strings)) und etwas heiße Luft.
    Mag aber dran liegen dass Sortieralgorhitmen gut erfoscht sind und Dir damit nichts schnelleres gelingen kann, die theoretische Obergrenze ist ja schon erreicht.

    GREETINGS PROFESSOR FALKEN
    A STRANGE GAME.
    THE ONLY WINNING MOVE IS NOT TO PLAY.
    HOW ABOUT A NICE GAME OF CHESS?