Squirrelsort

Projekt

Bei der Vorbereitung zur Abschlussprüfung für meine Schule bin ich über eine Aufgabe gestolpert:

Bitte lösen Sie folgendes Problem mit Pseudocode ...

Einen Sortieralgorithmus implementieren Sie selbst.

Au weia. Das Problem selbst war recht trivial, aber einen Bubblesort mal eben aus dem Ärmel schütteln?

Vor allem wenn man es gewohnt ist immer sorted() zu verwenden...

Idee

Ich bastel mir jetzt mal einen Bubblesort zusammen, um das mal wirklich zu verstehen.

Und um möglichst wenig schummeln zu können habe ich mich für C++ entschieden.

Umsetzung

Als erstes schreibt man sich ein makefile um mit clang vernünftig reden zu können.

Danach ein paar Funktionen um Arrays am Display darzustellen, sowie mit Zufallszahlen zu befüllen.

Jetzt geht es an den eigentlichen Sortieralgorithmus: Erstmal einen Bubblesort.

Nachdem man ein bisschen aufgeräumt hat, fängt man an im Web rumzuklicken..

Da gibt es doch noch viel mehr...

Umfang

Letztendlich habe ich eine ganze Menge Sortieralgorithmen implementiert:

• Bubblesort
• Combsort
• Heapsort
• Insertionsort
• Mergesort
• Quicksort
• Selectionsort
• Shellsort

Ausgabe

Das Programm generiert in der jetzigen Form folgende Ausgabe:

input data:
[    15,    14,    13,    12,    11,    10,     9,     8,     7,     6,     5,     4,     3,     2,     1,     0 ]
(ok) - bubble:
[     0,     1,     2,     3,     4,     5,     6,     7,     8,     9,    10,    11,    12,    13,    14,    15 ]
(ok) - comb:
[     0,     1,     2,     3,     4,     5,     6,     7,     8,     9,    10,    11,    12,    13,    14,    15 ]
(ok) - heap:
[     0,     1,     2,     3,     4,     5,     6,     7,     8,     9,    10,    11,    12,    13,    14,    15 ]
(ok) - insert:
[     0,     1,     2,     3,     4,     5,     6,     7,     8,     9,    10,    11,    12,    13,    14,    15 ]
(ok) - merge:
[     0,     1,     2,     3,     4,     5,     6,     7,     8,     9,    10,    11,    12,    13,    14,    15 ]
(ok) - quick:
[     0,     1,     2,     3,     4,     5,     6,     7,     8,     9,    10,    11,    12,    13,    14,    15 ]
(ok) - select:
[     0,     1,     2,     3,     4,     5,     6,     7,     8,     9,    10,    11,    12,    13,    14,    15 ]
(ok) - shell:
[     0,     1,     2,     3,     4,     5,     6,     7,     8,     9,    10,    11,    12,    13,    14,    15 ]

input data:
[     0,    -1,    -2,    -3,    -4,    -5,    -6,    -7,    -8,    -9,   -10,   -11,   -12,   -13,   -14,   -15 ]
(ok) - bubble:
[   -15,   -14,   -13,   -12,   -11,   -10,    -9,    -8,    -7,    -6,    -5,    -4,    -3,    -2,    -1,     0 ]
(ok) - comb:
[   -15,   -14,   -13,   -12,   -11,   -10,    -9,    -8,    -7,    -6,    -5,    -4,    -3,    -2,    -1,     0 ]
(ok) - heap:
[   -15,   -14,   -13,   -12,   -11,   -10,    -9,    -8,    -7,    -6,    -5,    -4,    -3,    -2,    -1,     0 ]
(ok) - insert:
[   -15,   -14,   -13,   -12,   -11,   -10,    -9,    -8,    -7,    -6,    -5,    -4,    -3,    -2,    -1,     0 ]
(ok) - merge:
[   -15,   -14,   -13,   -12,   -11,   -10,    -9,    -8,    -7,    -6,    -5,    -4,    -3,    -2,    -1,     0 ]
(ok) - quick:
[   -15,   -14,   -13,   -12,   -11,   -10,    -9,    -8,    -7,    -6,    -5,    -4,    -3,    -2,    -1,     0 ]
(ok) - select:
[   -15,   -14,   -13,   -12,   -11,   -10,    -9,    -8,    -7,    -6,    -5,    -4,    -3,    -2,    -1,     0 ]
(ok) - shell:
[   -15,   -14,   -13,   -12,   -11,   -10,    -9,    -8,    -7,    -6,    -5,    -4,    -3,    -2,    -1,     0 ]

input data:
[    36,   -91,   -39,    71,    23,   -66,    78,   -67,   -72,    96,    58,   -16,   -58,     9,    73,   -55 ]
(ok) - bubble:
[   -91,   -72,   -67,   -66,   -58,   -55,   -39,   -16,     9,    23,    36,    58,    71,    73,    78,    96 ]
(ok) - comb:
[   -91,   -72,   -67,   -66,   -58,   -55,   -39,   -16,     9,    23,    36,    58,    71,    73,    78,    96 ]
(ok) - heap:
[   -91,   -72,   -67,   -66,   -58,   -55,   -39,   -16,     9,    23,    36,    58,    71,    73,    78,    96 ]
(ok) - insert:
[   -91,   -72,   -67,   -66,   -58,   -55,   -39,   -16,     9,    23,    36,    58,    71,    73,    78,    96 ]
(ok) - merge:
[   -91,   -72,   -67,   -66,   -58,   -55,   -39,   -16,     9,    23,    36,    58,    71,    73,    78,    96 ]
(ok) - quick:
[   -91,   -72,   -67,   -66,   -58,   -55,   -39,   -16,     9,    23,    36,    58,    71,    73,    78,    96 ]
(ok) - select:
[   -91,   -72,   -67,   -66,   -58,   -55,   -39,   -16,     9,    23,    36,    58,    71,    73,    78,    96 ]
(ok) - shell:
[   -91,   -72,   -67,   -66,   -58,   -55,   -39,   -16,     9,    23,    36,    58,    71,    73,    78,    96 ]

input data:
[  -823,  -800,  -326,  -213,  -415,  -765,  -926,  -409,  -997,  -877,  -290,   844,  -302,  -121,   614,  -842 ]
(ok) - bubble:
[  -997,  -926,  -877,  -842,  -823,  -800,  -765,  -415,  -409,  -326,  -302,  -290,  -213,  -121,   614,   844 ]
(ok) - comb:
[  -997,  -926,  -877,  -842,  -823,  -800,  -765,  -415,  -409,  -326,  -302,  -290,  -213,  -121,   614,   844 ]
(ok) - heap:
[  -997,  -926,  -877,  -842,  -823,  -800,  -765,  -415,  -409,  -326,  -302,  -290,  -213,  -121,   614,   844 ]
(ok) - insert:
[  -997,  -926,  -877,  -842,  -823,  -800,  -765,  -415,  -409,  -326,  -302,  -290,  -213,  -121,   614,   844 ]
(ok) - merge:
[  -997,  -926,  -877,  -842,  -823,  -800,  -765,  -415,  -409,  -326,  -302,  -290,  -213,  -121,   614,   844 ]
(ok) - quick:
[  -997,  -926,  -877,  -842,  -823,  -800,  -765,  -415,  -409,  -326,  -302,  -290,  -213,  -121,   614,   844 ]
(ok) - select:
[  -997,  -926,  -877,  -842,  -823,  -800,  -765,  -415,  -409,  -326,  -302,  -290,  -213,  -121,   614,   844 ]
(ok) - shell:
[  -997,  -926,  -877,  -842,  -823,  -800,  -765,  -415,  -409,  -326,  -302,  -290,  -213,  -121,   614,   844 ]

input data:
[ -4586, -6474,  3483, -9694,  -963,  6604, -1012,  2676,  8453, -2115,  -459, -1230,  3181,  -801,  8572, -5436 ]
(ok) - bubble:
[ -9694, -6474, -5436, -4586, -2115, -1230, -1012,  -963,  -801,  -459,  2676,  3181,  3483,  6604,  8453,  8572 ]
(ok) - comb:
[ -9694, -6474, -5436, -4586, -2115, -1230, -1012,  -963,  -801,  -459,  2676,  3181,  3483,  6604,  8453,  8572 ]
(ok) - heap:
[ -9694, -6474, -5436, -4586, -2115, -1230, -1012,  -963,  -801,  -459,  2676,  3181,  3483,  6604,  8453,  8572 ]
(ok) - insert:
[ -9694, -6474, -5436, -4586, -2115, -1230, -1012,  -963,  -801,  -459,  2676,  3181,  3483,  6604,  8453,  8572 ]
(ok) - merge:
[ -9694, -6474, -5436, -4586, -2115, -1230, -1012,  -963,  -801,  -459,  2676,  3181,  3483,  6604,  8453,  8572 ]
(ok) - quick:
[ -9694, -6474, -5436, -4586, -2115, -1230, -1012,  -963,  -801,  -459,  2676,  3181,  3483,  6604,  8453,  8572 ]
(ok) - select:
[ -9694, -6474, -5436, -4586, -2115, -1230, -1012,  -963,  -801,  -459,  2676,  3181,  3483,  6604,  8453,  8572 ]
(ok) - shell:
[ -9694, -6474, -5436, -4586, -2115, -1230, -1012,  -963,  -801,  -459,  2676,  3181,  3483,  6604,  8453,  8572 ]


input length:                     64
(ok) - bubble:                 45800
(ok) - comb:                   12000
(ok) - heap:                   51600
(ok) - insert:                 10100
(ok) - merge:                  21700
(ok) - quick:                 193300
(ok) - select:                 16400
(ok) - shell:                  30400

input length:                    128
(ok) - bubble:                178000
(ok) - comb:                   26000
(ok) - heap:                   39100
(ok) - insert:                 34300
(ok) - merge:                  38600
(ok) - quick:                  20300
(ok) - select:                 68500
(ok) - shell:                  24600

input length:                    256
(ok) - bubble:               1102700
(ok) - comb:                   56000
(ok) - heap:                   97900
(ok) - insert:                109000
(ok) - merge:                  77100
(ok) - quick:                  40500
(ok) - select:                196400
(ok) - shell:                  57300

input length:                    512
(ok) - bubble:               1629200
(ok) - comb:                  126800
(ok) - heap:                  185700
(ok) - insert:                427700
(ok) - merge:                 178900
(ok) - quick:                  88700
(ok) - select:                700500
(ok) - shell:                 131200

input length:                   1024
(ok) - bubble:               8501400
(ok) - comb:                  296100
(ok) - heap:                  407900
(ok) - insert:               1708400
(ok) - merge:                 343800
(ok) - quick:                 187500
(ok) - select:               3683300
(ok) - shell:                 357700

input length:                   2048
(ok) - bubble:              35942700
(ok) - comb:                  683700
(ok) - heap:                  921300
(ok) - insert:              12688500
(ok) - merge:                 761800
(ok) - quick:                 410300
(ok) - select:              12900200
(ok) - shell:                 852900

input length:                   4096
(ok) - bubble:             135837800
(ok) - comb:                 1438200
(ok) - heap:                 1948400
(ok) - insert:              37952300
(ok) - merge:                1761300
(ok) - quick:                1538600
(ok) - select:              52090200
(ok) - shell:                2136500

Der obere Teil zeigt das zu sortierende Array, sowie das Ergebnis an.

Anfangs absteigend positive bzw. negative Zahlen, dann Zufallszahlen zwischen ± 99, ± 999 und ± 9999.

Einfach nur um sicher zu stellen, dass korrekt sortiert wird.

Im unteren Teil werden Arrays in den Längen von 64 bis 4096 mit Zufallszahlen ± 9999 sortiert.

Dabei wird die Zeit gestoppt - somit lassen sich die Algorithmen untereinander vergleichen.

Fazit

Bubblesort ist in allen Tests immer mit Abstand am langsamsten.

Quicksort macht seinem Namen alle Ehere! Leider nicht bei kurzen Arrays, bei langen aber umso mehr.

Ganz interessant sind noch Combsort, sowie Insertionsort.