Code-Beispiel

Datenfeld-Sortierung optimieren

Lizenz:	Erster Autor:	Letzte Bearbeitung:
Freeware (proprietär)	Sundboy60	24.06.2020

Mich störte, wie viel Zeit die Sortierung eines Datenfeldes verschlingt.
Ich versuchte die üblicher Weise verwendete "Ur-Variante" zu optimieren,
um so viel Zeitgewinn wie möglich zu erreichen!
Die allgemein gültigen Voraussetzungen wurden gebildet durch:
"T(1 TO E)" - Text-Array als String mit Anzahl "E" Datensätzen.

'' Dimensionierungen --------------------------------------------

    DIM SHARED AS INTEGER S                 '' Sortierschalter

    DIM SHARED AS INTEGER E = 50000         '' Endwert (Anzahl?)

    DIM SHARED AS STRING T(1 TO E)          '' Text-Array

    DIM SHARED AS INTEGER A, K              '' Anfang, Klein

    '' zusaetzlich, nur bei Variante 2:

    DIM SHARED AS INTEGER B, G              '' Ende, Gross

'' Declarationen der Unterprogramme -----------------------------

    DECLARE SUB Testen (A1 AS INTEGER, E1 AS INTEGER) '' Sortieren?

    DECLARE SUB Sortieren                   '' Sortieren !

Neu habe ich den eigendlichen Sortiervorgang
und den Test - ob eine Sortierung notwendig ist -
in Unterprogramme am Ende des Programmdurchlaufes "gesteckt"!
Die eigentliche Sortiervariante, die man nutzen möchte, muß nur
noch eingebunden werden!

'' UP: Ist eine Sortierung notwendig ? --------------------------

    SUB Testen (A1 AS INTEGER, E1 AS INTEGER)

        FOR I AS INTEGER = A1 TO E1

            S = 0 : IF T(I + 1) < T(I) THEN S = 1 : EXIT FOR '' SUB

        NEXT

    END SUB

'' UP: Text-Array sortieren ! -----------------------------------

    SUB Sortieren

        PRINT !"\10 Sortierung:"            '' temporaer

        '' HIER EINEN DER SORTIERBLOECKE EINFUEGEN!

    END SUB

Zuerst wird überprüft, ob eine Sortierung überhaupt notwendig ist.
Erst dann wird tatsächlich sortiert!

'' vorherige Abfrage, ob Sortierung notwendig ist ---------------

    Testen (1, E - 1)                       '' Sortieren ?

    IF S = 1 THEN Sortieren                 '' Sortieren !

Variante 1: "Ur-Variante!" - Allerdings auch die langsamste!
(Nur zum Vergleich mit eingefügt!)

'' Sortierung Variante 1 (Urversion)

        FOR A = 1 TO E

            FOR I AS INTEGER = 1 TO E

                IF T(I) > T(A) THEN SWAP T(I), T(A)

        NEXT : NEXT

Variante 1a: Leicht überarbeitet! - Bereits geringfügig schneller!
(Etwa 1,6x schneller gegenüber Variante 1!)
Die äußere Schleife "A" endet bereits am vorletzten Datensatz "E-1" des Array.
Die innere Schleife "I" beginnt einen Datensatz über der äußeren Schleife "A" ("A+1")

'' Sortierung Variante 1a (ueberarbeitet)

        FOR A = 1 TO E - 1

            FOR I AS INTEGER = A + 1 TO E

                IF T(I) < T(A) THEN SWAP T(I), T(A)

        NEXT : NEXT

Variante 1b: Komplett überarbeitet! - Auf Basis der Variante 1a.
Hierbei wurde eine eindeutige Zeitersparrnis erreicht, da "suchen" und "tauschen" von einander getrennt wurde!
(Etwa 3,1x schneller gegenüber Variante 1!)
In der äußeren Schleife "A" wird zuerst die erste Position in "K" (Klein) geschrieben.
Danach wird in der inneren Schleife "I" nach einem möglichen "kleinerem" Datensatz gesucht,
von dem nur die Position in "K" (Klein) geschrieben wird.
Es wird solange weiter gesucht, bis eventuell ein noch kleinerer Datensatz gefunden wurde.
Von diesem wird wiederrum die Position in "K" (Klein) eingetragen.
Ist die innere Schleife "I" durchlaufen, wird geprüft, ob die Position "K" (Klein)
noch mit der Position "A" (Außen) übereinstimmt.
Nur wenn dies nicht der Fall ist, werden die Datensätze
der neuen gefundenen Position "K" (Klein) mit der Position "A" (Außen) getauscht!

'' Sortierung Variante 1b (nach klein)

        FOR A = 1 TO E - 1 : K = A

            FOR I AS INTEGER = A + 1 TO E

                IF T(I) < T(K) THEN K = I

            NEXT

            IF K < > A THEN SWAP T(K), T(A)

        NEXT

Neue Variante 1c und Variante 1d: (Im Prinzip erweiterte Variante 1b!)
Es wird nach der Beendigung der innerern Schleife geprüft,
ob der Rest des Arrays noch sotiert werden muß!
Bei Variante 1c immer und bei Variante 1d nur, wenn nicht getauscht wurde.
(Es entsteht nur ein weiterer Zeitgewinn, wenn dies der Fall ist
und die Sortierung tatsächlich vorzeitig abgebrochen werden kann!)

'' Sortierung Variante 1c (vorzeitiger Abbruch?)

        FOR A = 1 TO E - 1 : K = A

            FOR I AS INTEGER = A + 1 TO E

                IF T(I) < T(K) THEN K = I

            NEXT

            IF K < > A THEN SWAP T(K), T(A)

            Testen (A + 1, E - 1) : IF S = 0 THEN EXIT FOR '' SUB

        NEXT



'' Sortierung Variante 1d (vorzeitiger Abbruch?)

        FOR A = 1 TO E - 1 : K = A

            FOR I AS INTEGER = A + 1 TO E

                IF T(I) < T(K) THEN K = I

            NEXT

            IF K < > A THEN

                SWAP T(K), T(A)

            ELSE : Testen (A + 1, E - 1) : IF S = 0 THEN EXIT FOR '' SUB

            END IF

        NEXT

Variante 2: Komplett neu von der Herangehensweise ausgelegt.
Im Prinzip habe ich mich jedoch an meine Variante 1b gehalten!
(Etwa 3,8x schneller gegenüber Varante 1!)
Noch mehr "TURBO"-Sortierung konnte ich bisher nicht erreichen!
Um eine Halbierung des Datensatzes zu ermöglichen, habe ich vorher einen Test einfügen
müssen. (Ungerader Datensatz läßt die Sortierung in einen Fehler laufen!)
Zuerst wird in der äußeren Schleife (DO LOOP) die erste Position "A" (Anfang) in "K" (Klein)
und die letzte Position "B" (Ende) in "G" (Groß) geschrieben.
Danach wird in einem Durchlauf der inneren Schleife "I", von "A" (Anfang) + 1 bis "B" (Ende) - 1,
gleichzeitig nach der kleinsten "K" (Klein) Position und nach der größten "G" (Groß) Position gesucht.
(Im Prinzip wie Variante 1b - nur ebend doppelt.)
Ist die innere Schleife "I" durchlaufen, wird geprüft, ob die Position "K" (Klein)
noch mit der Position "A" (Anfang) sowie die Position "G" (Groß) mit der Position "B" (Ende) übereinstimmt.
Nur wenn dies nicht der Fall ist, werden die jeweiligen Datensätze mit der neuen gefundenen Positionen getauscht!
Die geänderten Abfragen wurden notwendig, da sich bei den vorherigen Versionen
beim sortieren sehr oft Fehler eingeschlichen haben.
Gleichzeitig wird danach die Position "A" (Anfang) + 1 und die Position "B" (Ende) - 1 gesetzt.
Dies geschieht solange, bis sich "A" (Anfang) und "B" (Ende) der "Mitte" des Text-Array annähern oder treffen.

'' Sortierung Variante 2 (nach klein und gross)

        A = 1 : B = E : G = 1

        '' ungerader Datensatz

        IF E / 2 < > E \ 2 THEN

            FOR I AS INTEGER = A TO B

                IF T(I) > T(G) THEN G = I

            NEXT : SWAP T(E), T(G) : B - = 1

        END IF

        '' Sortierung

        DO : K = A : G = A

            FOR I AS INTEGER = A TO B - 1

                IF T(I + 1) < T(K) THEN K = I + 1

                IF T(I + 1) > T(G) THEN G = I + 1

            NEXT

            IF G = A AND K < > B THEN SWAP T(G), T(B)

            IF K < > A THEN SWAP T(K), T(A)

            IF G < > B _

                    AND ((B - A - 1) > 0) _

                    AND (NOT (K = B AND G = A)) _

                    AND (NOT (G = A)) _

                    THEN SWAP T(G), T(B)

            A + = 1 : B - = 1

        LOOP UNTIL A > = B

Neue Variante 2a und Variante 2b: (Im Prinzip erweiterte Variante 2!)
Es wird nach der Beendigung der innerern Schleife geprüft,
ob der Rest des Arrays noch sotiert werden muß!
Bei Variante 2a immer und bei Variante 2b nur,
wenn die kleine und große Position nicht getauscht wurden.
(Ob der höhere Programmieraufwand gerechtfertigt ist, sei dahin gestellt!)
Wie gesagt, Zeitersparnis ergibt sich nur, wenn man die Sortierung vorzeitig beenden kann!

'' Sortierung Variante 2a (vorzeitiger Abbruch?)

        A = 1 : B = E : G = 1

        '' ungerader Datensatz

        IF E / 2 < > E \ 2 THEN

            FOR I AS INTEGER = A TO B

                IF T(I) > T(G) THEN G = I

            NEXT : SWAP T(E), T(G) : B - = 1

        END IF

        '' Sortierung

        DO : K = A : G = A

            FOR I AS INTEGER = A TO B - 1

                IF T(I + 1) < T(K) THEN K = I + 1

                IF T(I + 1) > T(G) THEN G = I + 1

            NEXT

            IF G = A AND K < > B THEN SWAP T(G), T(B)

            IF K < > A THEN SWAP T(K), T(A)

            IF G < > B _

                    AND ((B - A - 1) > 0) _

                    AND (NOT (K = B AND G = A)) _

                    AND (NOT (G = A)) _

                    THEN SWAP T(G), T(B)

            Testen (A + 1, B - 1) : IF S = 0 THEN EXIT DO '' SUB

            A + = 1 : B - = 1

        LOOP UNTIL A > = B



'' Sortierung Variante 2b (vorzeitiger Abbruch?)

        A = 1 : B = E : G = 1

        '' ungerader Datensatz

        IF E / 2 < > E \ 2 THEN

            FOR I AS INTEGER = A TO B

                IF T(I) > T(G) THEN G = I

            NEXT : SWAP T(E), T(G) : B - = 1

        END IF

        '' Sortierung

        DO : K = A : G = A

            FOR I AS INTEGER = A TO B - 1

                IF T(I + 1) < T(K) THEN K = I + 1

                IF T(I + 1) > T(G) THEN G = I + 1

            NEXT

            IF G = A AND K < > B THEN SWAP T(G), T(B)

            IF K < > A THEN SWAP T(K), T(A)

            IF G < > B _

                    AND ((B - A - 1) > 0) _

                    AND (NOT (K = B AND G = A)) _

                    AND (NOT (G = A)) _

                    THEN SWAP T(G), T(B)

            IF (K = A) AND (G = B) THEN

                Testen (A + 1, B - 1) : IF S = 0 THEN EXIT DO '' SUB

            END IF

            A + = 1 : B - = 1

        LOOP UNTIL A > = B

Viel Spaß beim ausprobieren...
(Danke auch für Infos zur weiteren Verbesserung und ev. Hinweise auf Fehler in meiner Programmierung)

Zusätzliche Informationen und Funktionen

Das Code-Beispiel wurde am 09.05.2020 von Sundboy60 angelegt.
Die aktuellste Version wurde am 24.06.2020 von Sundboy60 gespeichert.

Bearbeiten

Versionen