christian berrer tyron madlener
Architektur
How-To: Stooge Sort in PostScript
Vergleich & Metriken
Eine „kleine“ Vorführung
Integer Array
PostScript Canvas
swap get (put) unmarkPoints markPoints
Sorting Algorithms
?
Vergleich
Punkte markieren
Vergleich durchführen
Punkte de-markieren
Swap
Punkte am Spielfeld tauschen
Punkte im Array
tauschen
Canvas
Array
Algorithmus
Einfach, rekursiv, total ineffizient
algorithm stoogeSort (i = 0, j = length(L) - 1)
if L[j] < L[i] then
L[i] ↔ L[j]
if (j - i + 1) >= 3 then
t = (j - i + 1) / 3
stoogeSort (i, j - t)
stoogeSort (i + t, j )
stoogeSort (i, j-t)
Erster Schritt: Skelett festlegen
/stoogeSort
{
/ss
{
{
} if
{
ss
ss
ss
} if
} bind def
0 fsize % Stack: i j
ss % Stack:
} bind def
Code und Debug-Operationen einfügen
(ss, out, 0, Stack: i j) pp
2dup
(ss, out, 1, Stack: i j i j) pp
ppop % Mark
(ss, out, 2, Stack: i j) pp
2dup 2 { exch field exch get+ } repeat
(ss, out, 3, Stack: i j f[i] f[j]) pp
gt 3 1 roll 2dup ppop rot % Unmark
(ss, out, 4, Stack: i j res) pp
{
(ss, if1, 0, Stack: i j) pp
2dup swap
(ss, if1, 1, Stack: i j) pp
} if
...
L[j] L[i] ........
< .............
if then ...
L[i] ↔ L[j] .........
Die Funktion pp: /pp { print (\n) print field pstack pop flush pause } def
/pp { pop } def
Wie sieht das live aus?
173
65
0
20
40
60
80
100
120
140
160
180
200
Operationen
Bubble
Selection
Insertion
Shell
Merge
Heap
Quick
Comb
Shear
Shaker
Slow
Gnome
Stooge
-25000
-20000
-15000
-10000
-5000
0
5000
10000
15000
20000
R1 R2 R3 R4 R5 R6 R7 R8 R9
Bubble
Selection
Insertion
Shell
Merge
Heap
Quick
Comb
Shear
Shaker
Gnome
Stooge
Durchschnittliche Abweichungen
0
5000
10000
15000
20000
25000
30000
Get Operations Put Operations
Bubble
Selection
Insertion
Shell
Merge
Heap
Quick
Comb
Shear
Shaker
Gnome
Stooge
0
50000
100000
150000
200000
250000
300000
350000
400000
450000
Get Operations Put Operations
Bubble
Selection
Insertion
Shell
Merge
Heap
Quick
Comb
Shear
Shaker
Gnome
Stooge
0
5000000
10000000
15000000
20000000
25000000
30000000
35000000
40000000
45000000
50000000
Get Operations Put Operations
Bubble
Selection
Insertion
Shell
Merge
Heap
Quick
Comb
Shear
Shaker
Gnome
Stooge
1,33406E+11
124908 43165714,2 118994,2 0
2E+10
4E+10
6E+10
8E+10
1E+11
1,2E+11
1,4E+11
1,6E+11
Get Operations Put Operations
Stooge
Slow