TU Wien:Algorithmen und Datenstrukturen VU (Szeider)/Algorithmen als Pseudocode

Selectionsort

Selectionsort(A):
for i ← 0 bis n − 2
    smallest ← i
    for j ← i + 1 bis n − 1
    if A[j] < A[smallest]
            smallest ← j
    Vertausche A[i] mit A[smallest]

Insertionsort

Insertionsort(A):
for i ← 1 bis n − 1
    key ← A[i], j ← i − 1
    while j ≥ 0 und A[j] > key
        A[j + 1] ← A[j]
        j ← j − 1
    A[j + 1] ← key

Breitensuche

Implementierung: Graph G = (V,E), Startknoten s, Array Discovered, Queue Q.

BFS(G,s):
Discovered[v] ← false für alle Knoten v ∈ V
Discovered[s] ← true
Q ← {s}
while Q ist nicht leer
    Entferne ersten Knoten u aus Q
    Führe Operation auf u aus
    foreach Kante (u,v) inzident zu u
        if !Discovered[v]
            Discovered[v] ← true
            Füge v zu Q hinzu

Tiefensuche

Implementierung: Graph G = (V,E), Startknoten s, globales Array Discovered.

DFS(G,s):
Discovered[v] ← false für alle Knoten v ∈ V
DFS1(G,s)

DFS1(G,u):
Discovered[u] ← true
Führe Operation auf u aus
foreach Kante (u,v) inzident zu u
    if !Discovered[v]
        DFS1(G,v)

Dijkstra

Dijkstra(G,s):
Discovered[v] ← false für alle Knoten v ∈ V
d[s] ← 0
d[v] ← ∞ für alle anderen Knoten v ∈ V \ {s}
L ← V
while L ist nicht leer
    wähle u ∈ L mit kleinstem Wert d[u]
    lösche u aus L
    Discovered[u] ← true
    foreach Kante e = (u,v) ∈ E
        if !Discovered[v]
            d[v] ← min(d[v],d[u]+‘e)

Heapify-up

Heapify-up(H,i):
if i > 1
    j ← ⌊i/2⌋
    if H[i] < H[j]
        Vertausche die Array-Einträge H[i] und H[j]
        Heapify-up(H,j)

Heapify-down

Heapify-down(H,i):
n ← length(H)-1
if 2 · i > n
    return
elseif 2 · i < n
    left ← 2 · i, right ← 2 · i + 1
    j ← Index des kleineren Wertes von H[left] und H[right]
else
    j ← 2 · i
if H[j] < H[i]
    Vertausche die Arrayeinträge H[i] und H[j]
    Heapify-down(H,j)

Prim

Annahme: Alle Kantengewichte sind unterschiedlich.

Prim(G, c):
foreach (v ∈ V )
    A[v] ← ∞
Initialisiere eine leere Priority Queue Q
foreach (v ∈ V )
    Füge v in Q ein
S ← ∅
while Q ist nicht leer
    u ← entnehme minimales Element aus Q
    S ← S ∪ {u}
    foreach Kante e = (u, v) inzident zu u
         if v ∉ S und ce < A[v]
             Verringere die Priorität A[v] auf ce

Mergesort

Merge(A,l,m,r):
i ← l, j ← m + 1, k ← l
while i ≤ m und j ≤ r
    if A[i] ≤ A[j]
        B[k] ← A[i], i ← i + 1
    else
        B[k] ← A[j], j ← j + 1
    k ← k + 1
if i > m
    for h ← j bis r
        B[k] ← A[h], k ← k + 1
else
    for h ← i bis m
        B[k] ← A[h], k ← k + 1
for h ← l bis r
    A[h] ← B[h]

Binäre Suchbäume

Inorder(p)
if p ≠ null
    Inorder(p.left)
    Bearbeite p
    Inorder(p.right)

Search(p,s):
while p ≠ null und p.key ≠ s
    if s < p.key
        p ← p.left
    else
        p ← p.right
return p

Minimum(p):
if p = null
    return null
while p.left ≠ null
    p ← p.left
return p

Maximum(p):
if p = null
    return null
while p.right ≠ null
    p ← p.right
return p

Successor(p):
if p.right ≠ null
    return Minimum(p.right)
else
    q ← p.parent
    while q ≠ null und p = q.right
        p ← q
        q ← q.parent
return q

Predecessor(p):
if p.left ≠ null
    return Maximum(p.left)
else
    q ← p.parent
    while q ≠ null und p = q.left
        p ← q
        q ← q.parent
return q

Insert(root, q):
r ← null, p ← root
while p ≠ null
    r ← p
    if q.key < p.key
        p ← p.left
    else
        p ← p.right
q.parent ← r, q.left ← null, q.right ← null
if r = null
    root ← q
else
    if q.key < r.key
        r.left ← q
    else
        r.right ← q

Remove(root, q):
if q.left = null oder q.right = null
   r ← q
else
   r ← Successor(q), q.key ← r.key, q.info ← r.info
if r.left ≠ null
   p ← r.left
else
   p ← r.right
if p ≠ null
   p.parent ← r.parent
if r.parent = null
   root ← p
else
   if r = r.parent.left
      r.parent.left ← p
   else
      r.parent.right ← p