Howto - Flowcharts mit Mermaid.js

Geändert: 2025-06-14 09:01:18, Wörter: 133, Lesedauer: 1 min

TODO

Visualisierung mit Flussdiagramm

TODO

Quicksort

TODO

function quicksort(A,p,r)
    if p < r
        {true, then there are at least two elements}
        q = Partition(A,p,r) {pivot element at index q is in the right position}
        Quicksort(A,p,q-1) {pivot element at index q is not included}
        Quicksort(A,q+1,r) {pivot element at index q is not included}
    else
        {false, then there is only one element}

function Partition(A,p,r)
    x = A[p]
    i = p - 1
    j = r + 1
    while TRUE
        do
            j = j - 1
        while not A[j] <= x
        do
            i = i + 1
        while not A[i] >= x
        if i < j
            Swap(A[i],A[j])
        else
            return j {pivot element at index j is in the right position}

Note

Im Source dieses Artikels kann man sehen wie der nachfolgende Flowchart mit Mermaid.js erstellt wurde.

        %%{ init: { 'flowchart': { 'curve': 'basis' } } }%%			%% Default, kantig-rund mit großen Rundungen.
%%{ init: { 'flowchart': { 'curve': 'stepAfter' } } }%%		%% Kantig, nicht perfekt, aber besser als andere Kantenwerte.
%%{ init: { 'flowchart': { 'curve': 'linear' } } }%%		%% Keine geraden Linien wie man denkt, sondern wie monotoneY, aber mit scharfen Ecken statt leicht runden.
%%{ init: { 'flowchart': { 'curve': 'monotoneY' } } }%%		%% Wie basis kantig-rund, nur kleine Rundungen.
flowchart TD
	Start(["`**Quicksort(A,p,r)**<hr>_{Lomuto's variant from<br>Cormen et. al.}_`"])
	Question{"p < r"}
	Pivot[["q = Partition(A,p,r)<hr>_{pivot element at index q<br>is in the right position}_"]]
	Call1[["Quicksort(A,p,q-1)<hr>_{pivot element at index q<br>**is not** included}_"]]
	Call2[["Quicksort(A,q+1,r)<hr>_{pivot element at index q<br>**is not** included}_"]]
	Stop(("O"))
	
	Start --> |"A := array<br>p := left index<br>r := right index"| Question
	Question --> |"true, then there are at least two elements"| Pivot
	Question --> |"false, then there is only one element"| Stop
	Pivot --> Call1
	Call1 --> Call2
	Call2 --> Stop
	
	Partition_Start(["`**Partition(A,p,r)**<hr>_{Hoare's variant from<br>Cormen et. al.}_`"])
	Partition_Line1("x = A[p]")
	Partition_Line2("i = p - 1")
	Partition_Line3("j = r + 1")
	Partition_While{{"while TRUE"}}
	
	Partition_Do1(("do"))
	Partition_Do1_Line1("j = j - 1")
	Partition_While1{{"while not A[j] <= x"}}
	
	Partition_Do2(("do"))
	Partition_Do2_Line1("i = i + 1")
	Partition_While2{{"while not A[i] >= x"}}
	
	Partition_If{"i < j"}
	Partition_Swap[["Swap(A[i],A[j])"]]
	Partition_Return("return j<hr>_{pivot element at index j<br>is in the right position}_")
	Partition_Stop(("O"))
	
	Partition_Start --> |"A := array<br>p := left index<br>r := right index"| Partition_Line1
	Partition_Line1 --> Partition_Line2
	Partition_Line2 --> Partition_Line3
	Partition_Line3 --> Partition_While
	Partition_While --> |"true"| Partition_Do1

	Partition_Do1 --> Partition_Do1_Line1
	Partition_Do1_Line1 --> Partition_While1
	Partition_While1 --> |"true"| Partition_Do1
	
	Partition_While1 --> |"false"| Partition_Do2

	Partition_Do2 --> Partition_Do2_Line1
	Partition_Do2_Line1 --> Partition_While2
	Partition_While2 --> |"true"| Partition_Do2

	Partition_While2 --> |"false"| Partition_If
	Partition_If --> |"true"| Partition_Swap
	Partition_Swap --> Partition_While
	Partition_If --> |"false"| Partition_Return
	Partition_Return --> Partition_Stop

%%	Partition_While --> |"false"| Partition_Stop
    

Introsort

Der bei Wikipedia abgebildete Pseudocode für Introsort ist Bullshit, weil er nicht original ist und da nicht mal ein Hinweis gegeben wird woher der ist. Der hier nachfolgende Pseudocode ist fast identisch mit dem aus dem originalen PostScript. Dort ist die Rede von Parametern (A,f,b) statt (A,p,r). Dabei ist b = r + 1 bzw. r = b - 1. Denn das PostScript zeigt Pseudocode für C++ und Code in C++. Und da ist bekanntlich die Norm, dass man Bereiche mit \([first,last)\) angibt. Wir nutzen hier die Norm aus Cormen et. al. mit (A,p,r).

function introsort(A,p,r)
    n = r - p + 1 {number of elements}
    introsort_loop(A,p,r,2*Floor(Log2(n)))
    insertionsort(A,p,r)

function introsort_loop(A,p,r,depth_limit)
    n = r - p + 1 {number of elements}
    while n > depth_limit
        if depth_limit == 0
            heapsort(A,p,r)
            return
        else
            depth_limit = depth_limit - 1
            p = Partition(A,p,r,TODO)
            introsort_loop(A,p,r,depth_limit)
            r = p

Note

Im Source dieses Artikels kann man sehen wie der nachfolgende Flowchart mit Mermaid.js erstellt wurde.

TODO: Flowchart von Intosort basteln.

Fazit

TODO