---
author: B. A. Sylla
category: Howto
date: 9025-05-23
language: de
tags: Documentation
---

Howto - Flowcharts mit Mermaid.js
=================================

<img class="bloghead" src="../../../_static/img/blogimg/bar_charts.jpg">

<small class="extrameta">Geändert: {sub-ref}`today`, Wörter: {sub-ref}`wordcount-words`, Lesedauer: {sub-ref}`wordcount-minutes` min</small>

TODO

Visualisierung mit Flussdiagramm
--------------------------------

TODO

### Quicksort

TODO

```{code-block} delphi
:linenos: true
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}
```
```{code-block} delphi
:linenos: true
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.
```

```{mermaid}
%%{ 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](https://en.wikipedia.org/wiki/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](https://web.archive.org/web/20230307185457/http://www.cs.rpi.edu/~musser/gp/introsort.ps). 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)`.

```{code-block} delphi
:linenos: true
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)
```
```{code-block} delphi
:linenos: true
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