10 Jul 2017

Die siebte Abgabe in Betriebssysteme und Systemsoftware

Übungsblatt

01 Jul 2017

Die sechste Abgabe in Betriebssysteme und Systemsoftware

Übungslatt 6

31 May 2017

LaTeX-Schnipsel zur Visualisierung von Rot-Schwarz-Bäumen (z.B. Aufgabe 11 von DSAL Abgabe 5, dort ist auch ein Java-programm zur generierung von TikZ-Bildern zu finden).

Benötigte Pakete sowie benutzte Style Settings:

\usepackage{tikz}
\usetikzlibrary{shapes,arrows,positioning,decorations,
  automata,backgrounds,petri,bending,
  shapes.multipart
} %Eventuell sind nicht alle nötig
\usepackage{pgf}

\tikzset{
  treenode/.style = {shape=circle,
    draw, align=center},
  graynode/.style = {fill=gray},
  normal/.style     = {treenode, font=\Large, bottom color=white},
  blackTreeNode/.style =
  {treenode,shape=rectangle,white,fill=black,minimum width=1.5em, ,
    minimum height=1.5em },% arbre rouge noir, noeud noir
  redTreeNode/.style = {treenode, red, draw=red,fill=red!15!white,
    thick},% arbre rouge noir, noeud rouge 
  externalBlackNode/.style = {treenode, shape=rectangle, draw=black,
    minimum width=0.25em, minimum height=0.25em,fill=black}% arbre rouge noir, nil
}

(Dies ist die ganze Aufgabe DSAL-U5-A11, klau dir einfach das, was du brauchst)

\newsubsubproblem[1]
\begin{figure}[H]
  \centering
  \begin{tikzpicture}
    [sibling distance        = 3em,
    level distance          = 3em,
    edge from parent/.style = {draw, -latex},
    every node/.style       = {font=\footnotesize},
    level 1/.style={sibling distance=8em},
    level 2/.style={sibling distance=4em},
    level 3/.style={sibling distance=2em},
    level 4/.style={sibling distance=1em},
    sloped
    ]
    \node [blackTreeNode] {6}
    child { 
      node [externalBlackNode] {}} 
    child { 
      node [externalBlackNode] {}}
    ;
  \end{tikzpicture}
  \caption{\texttt{Einf\"uge-Operation} von 6}
\end{figure}

\newsubsubproblem[2]
\begin{figure}[H]
  \centering
  \begin{tikzpicture}
    [sibling distance        = 3em,
    level distance          = 3em,
    edge from parent/.style = {draw, -latex},
    every node/.style       = {font=\footnotesize},
    level 1/.style={sibling distance=8em},
    level 2/.style={sibling distance=4em},
    level 3/.style={sibling distance=2em},
    level 4/.style={sibling distance=1em},
    sloped
    ]
    \node [blackTreeNode] {6}
    child { 
      node [redTreeNode] {0}
      child { 
        node [externalBlackNode] {}} 
      child { 
        node [externalBlackNode] {}}
    } 
    child { 
      node [externalBlackNode] {}};
  \end{tikzpicture}
  \caption{\texttt{Einf\"uge-Operation} von 0}
\end{figure}

\newsubsubproblem[3]
\begin{figure}[H]
  \centering
  \begin{tikzpicture}
    [sibling distance        = 3em,
    level distance          = 3em,
    edge from parent/.style = {draw, -latex},
    every node/.style       = {font=\footnotesize},
    level 1/.style={sibling distance=8em},
    level 2/.style={sibling distance=4em},
    level 3/.style={sibling distance=2em},
    level 4/.style={sibling distance=1em},
    sloped
    ]
    \node [blackTreeNode] {6}
    child { 
      node [redTreeNode] {0}
      child { 
        node [externalBlackNode] (rotate2) {}} 
      child { 
        node [redTreeNode] (rotate1) {2}
        child { 
          node [externalBlackNode] {}} 
        child { 
          node [externalBlackNode] {}}
      }
    } 
    child { 
      node [externalBlackNode] {}};

    \node [left=.01 of rotate1] (rotate1L) {};
    \node [right=.01 of rotate2] (rotate2R) {};
    %\draw [->, line width=2pt,color=blue] (rotate2R) to[bend left=75] (rotate1L);
    \draw [->, line width=2pt,color=blue] (rotate1L) to[bend right=75] (rotate2R);
  \end{tikzpicture}
  \caption{\texttt{Einf\"uge-Operation} von 2}
\end{figure}

\begin{figure}[H]
  \centering
  \begin{tikzpicture}
    [sibling distance        = 3em,
    level distance          = 3em,
    edge from parent/.style = {draw, -latex},
    every node/.style       = {font=\footnotesize},
    level 1/.style={sibling distance=8em},
    level 2/.style={sibling distance=4em},
    level 3/.style={sibling distance=2em},
    level 4/.style={sibling distance=1em},
    sloped
    ]
    \node [blackTreeNode] {6}
    child { 
      node [redTreeNode] (rotate1) {2}
      child { 
        node [redTreeNode] {0}
        child { 
          node [externalBlackNode] {}} 
        child { 
          node [externalBlackNode] {}}
      } 
      child { 
        node [externalBlackNode] {}}
    } 
    child { 
      node [externalBlackNode] (rotate2) {}};

    
    \node [left=.01 of rotate1] (rotate1L) {};
    \node [right=.01 of rotate2] (rotate2R) {};
    \node [left=.01 of rotate2] (rotate2L) {};
    \node [right=.01 of rotate1] (rotate1R) {};
    \draw [->, line width=2pt,color=blue] (rotate1R) to[bend left=45] (rotate2L);
    %\draw [->, line width=2pt,color=blue] (rotate1L) to[bend right=75] (rotate2R);
  \end{tikzpicture}
  \caption{\texttt{Left-Rotate} \"uber 0}
\end{figure}

\begin{figure}[H]
  \centering
  \begin{tikzpicture}
    [sibling distance        = 3em,
    level distance          = 3em,
    edge from parent/.style = {draw, -latex},
    every node/.style       = {font=\footnotesize},
    level 1/.style={sibling distance=8em},
    level 2/.style={sibling distance=4em},
    level 3/.style={sibling distance=2em},
    level 4/.style={sibling distance=1em},
    sloped
    ]
    \node [redTreeNode] {2}
    child { 
      node [redTreeNode] {0}
      child { 
        node [externalBlackNode] {}} 
      child { 
        node [externalBlackNode] {}}
    } 
    child { 
      node [blackTreeNode] {6}
      child { 
        node [externalBlackNode] {}} 
      child { 
        node [externalBlackNode] {}}
    }
    ;
  \end{tikzpicture}
  \caption{\texttt{Right-Rotate} \"uber 6}
\end{figure}

\begin{figure}[H]
  \centering
  \begin{tikzpicture}
    [sibling distance        = 3em,
    level distance          = 3em,
    edge from parent/.style = {draw, -latex},
    every node/.style       = {font=\footnotesize},
    level 1/.style={sibling distance=8em},
    level 2/.style={sibling distance=4em},
    level 3/.style={sibling distance=2em},
    level 4/.style={sibling distance=1em},
    sloped
    ]
    \node [blackTreeNode] {2}
    child { 
      node [redTreeNode] {0}
      child { 
        node [externalBlackNode] {}} 
      child { 
        node [externalBlackNode] {}}
    } 
    child { 
      node [redTreeNode] {6}
      child { 
        node [externalBlackNode] {}} 
      child { 
        node [externalBlackNode] {}}
    }
    ;
  \end{tikzpicture}
  \caption{\texttt{Umf\"arbung}}
\end{figure}

\newsubsubproblem[4]
\begin{figure}[H]
  \centering
  \begin{tikzpicture}
    [sibling distance        = 3em,
    level distance          = 3em,
    edge from parent/.style = {draw, -latex},
    every node/.style       = {font=\footnotesize},
    level 1/.style={sibling distance=8em},
    level 2/.style={sibling distance=4em},
    level 3/.style={sibling distance=2em},
    level 4/.style={sibling distance=1em},
    sloped
    ]
    \node [blackTreeNode] {2}
    child { 
      node [redTreeNode] {0}
      child { 
        node [externalBlackNode] {}} 
      child { 
        node [externalBlackNode] {}}
    } 
    child { 
      node [redTreeNode] {6}
      child { 
        node [externalBlackNode] {}} 
      child { 
        node [redTreeNode] {19}
        child { 
          node [externalBlackNode] {}} 
        child { 
          node [externalBlackNode] {}}
      }
    }
    ;
  \end{tikzpicture}
  \caption{\texttt{Einf\"uge-Operation} von 19}
\end{figure}

\begin{figure}[H]
  \centering
  \begin{tikzpicture}
    [sibling distance        = 3em,
    level distance          = 3em,
    edge from parent/.style = {draw, -latex},
    every node/.style       = {font=\footnotesize},
    level 1/.style={sibling distance=8em},
    level 2/.style={sibling distance=4em},
    level 3/.style={sibling distance=2em},
    level 4/.style={sibling distance=1em},
    sloped
    ]
    \node [blackTreeNode] {2}
    child { 
      node [blackTreeNode] {0}
      child { 
        node [externalBlackNode] {}} 
      child { 
        node [externalBlackNode] {}}
    } 
    child { 
      node [blackTreeNode] {6}
      child { 
        node [externalBlackNode] {}} 
      child { 
        node [redTreeNode] {19}
        child { 
          node [externalBlackNode] {}} 
        child { 
          node [externalBlackNode] {}}
      }
    }
    ;
  \end{tikzpicture}
  \caption{\texttt{Umf\"arbung}}
\end{figure}

\newsubsubproblem[5]
\begin{figure}[H]
  \centering
  \begin{tikzpicture}
    [sibling distance        = 3em,
    level distance          = 3em,
    edge from parent/.style = {draw, -latex},
    every node/.style       = {font=\footnotesize},
    level 1/.style={sibling distance=8em},
    level 2/.style={sibling distance=4em},
    level 3/.style={sibling distance=2em},
    level 4/.style={sibling distance=1em},
    sloped
    ]
    \node [blackTreeNode] {2}
    child { 
      node [blackTreeNode] {0}
      child { 
        node [externalBlackNode] {}} 
      child { 
        node [externalBlackNode] {}}
    } 
    child { 
      node [blackTreeNode] {6}
      child { 
        node [externalBlackNode] {}} 
      child { 
        node [redTreeNode] {19}
        child { 
          node [redTreeNode] (rotate1) {12}
          child { 
            node [externalBlackNode] {}} 
          child { 
            node [externalBlackNode] {}}
        } 
        child { 
          node [externalBlackNode] (rotate2) {}}
      }
    };
    
    \node [left=0 of rotate1] (rotate1L) {};
    \node [right=0 of rotate2] (rotate2R) {};
    \node [left=0 of rotate2] (rotate2L) {};
    \node [right=0 of rotate1] (rotate1R) {};
    \draw [->, line width=2pt,color=blue] (rotate1) to[bend left=90] (rotate2);
    %\draw [->, line width=2pt,color=blue] (rotate1L) to[bend right=75] (rotate2R);
  \end{tikzpicture}
  \caption{\texttt{Einf\"uge-Operation} von 12}
\end{figure}

\begin{figure}[H]
  \centering
  \begin{tikzpicture}
    [sibling distance        = 3em,
    level distance          = 3em,
    edge from parent/.style = {draw, -latex},
    every node/.style       = {font=\footnotesize},
    level 1/.style={sibling distance=8em},
    level 2/.style={sibling distance=4em},
    level 3/.style={sibling distance=2em},
    level 4/.style={sibling distance=1em},
    sloped
    ]
    \node [blackTreeNode] {2}
    child { 
      node [blackTreeNode] {0}
      child { 
        node [externalBlackNode] {}} 
      child { 
        node [externalBlackNode] {}}
    } 
    child { 
      node [blackTreeNode] {6}
      child { 
        node [externalBlackNode] (rotate2) {}} 
      child { 
        node [redTreeNode] (rotate1) {12}
        child { 
          node [externalBlackNode] {}} 
        child { 
          node [redTreeNode] {19}
          child { 
            node [externalBlackNode] {}} 
          child { 
            node [externalBlackNode] {}}
        }
      }
    };

    \node [left=.01 of rotate1] (rotate1L) {};
    \node [right=.01 of rotate2] (rotate2R) {};
    \node [left=.01 of rotate2] (rotate2L) {};
    \node [right=.01 of rotate1] (rotate1R) {};
    %\draw [->, line width=2pt,color=blue] (rotate1R) to[bend left=45] (rotate2L);
    \draw [->, line width=2pt,color=blue] (rotate1L) to[bend right=75] (rotate2R);
  \end{tikzpicture}
  \caption{\texttt{Right-Rotate} \"uber 19}
\end{figure}

\begin{figure}[H]
  \centering
  \begin{tikzpicture}
    [sibling distance        = 3em,
    level distance          = 3em,
    edge from parent/.style = {draw, -latex},
    every node/.style       = {font=\footnotesize},
    level 1/.style={sibling distance=8em},
    level 2/.style={sibling distance=4em},
    level 3/.style={sibling distance=2em},
    level 4/.style={sibling distance=1em},
    sloped
    ]
    \node [blackTreeNode] {2}
    child { 
      node [blackTreeNode] {0}
      child { 
        node [externalBlackNode] {}} 
      child { 
        node [externalBlackNode] {}}
    } 
    child { 
      node [redTreeNode] {12}
      child { 
        node [blackTreeNode] {6}
        child { 
          node [externalBlackNode] {}} 
        child { 
          node [externalBlackNode] {}}
      } 
      child { 
        node [redTreeNode] {19}
        child { 
          node [externalBlackNode] {}} 
        child { 
          node [externalBlackNode] {}}
      }
    }
    ;
  \end{tikzpicture}
  \caption{\texttt{Left-Rotate} \"uber 6}
\end{figure}

\begin{figure}[H]
  \centering
  \begin{tikzpicture}
    [sibling distance        = 3em,
    level distance          = 3em,
    edge from parent/.style = {draw, -latex},
    every node/.style       = {font=\footnotesize},
    level 1/.style={sibling distance=8em},
    level 2/.style={sibling distance=4em},
    level 3/.style={sibling distance=2em},
    level 4/.style={sibling distance=1em},
    sloped
    ]
    \node [blackTreeNode] {2}
    child { 
      node [blackTreeNode] {0}
      child { 
        node [externalBlackNode] {}} 
      child { 
        node [externalBlackNode] {}}
    } 
    child { 
      node [blackTreeNode] {12}
      child { 
        node [redTreeNode] {6}
        child { 
          node [externalBlackNode] {}} 
        child { 
          node [externalBlackNode] {}}
      } 
      child { 
        node [redTreeNode] {19}
        child { 
          node [externalBlackNode] {}} 
        child { 
          node [externalBlackNode] {}}
      }
    }
    ;
  \end{tikzpicture}
  \caption{\texttt{Umf"arbung}}
\end{figure}

\newsubsubproblem[6]
\begin{figure}[H]
  \centering
  \begin{tikzpicture}
    [sibling distance        = 3em,
    level distance          = 3em,
    edge from parent/.style = {draw, -latex},
    every node/.style       = {font=\footnotesize},
    level 1/.style={sibling distance=8em},
    level 2/.style={sibling distance=4em},
    level 3/.style={sibling distance=2em},
    level 4/.style={sibling distance=1em},
    sloped
    ]
    \node [blackTreeNode] {2}
    child { 
      node [blackTreeNode] {0}
      child { 
        node [externalBlackNode] {}} 
      child { 
        node [externalBlackNode] {}}
    } 
    child { 
      node [blackTreeNode] {12}
      child { 
        node [redTreeNode] {6}
        child { 
          node [externalBlackNode] {}} 
        child { 
          node [externalBlackNode] {}}
      } 
      child { 
        node [redTreeNode] {19}
        child { 
          node [redTreeNode] {12}
          child { 
            node [externalBlackNode] {}} 
          child { 
            node [externalBlackNode] {}}
        } 
        child { 
          node [externalBlackNode] {}}
      }
    }
    ;
  \end{tikzpicture}
  \caption{\texttt{Einf\"uge-Operation} von 12}
\end{figure}

\begin{figure}[H]
  \centering
  \begin{tikzpicture}
    [sibling distance        = 3em,
    level distance          = 3em,
    edge from parent/.style = {draw, -latex},
    every node/.style       = {font=\footnotesize},
    level 1/.style={sibling distance=8em},
    level 2/.style={sibling distance=4em},
    level 3/.style={sibling distance=2em},
    level 4/.style={sibling distance=1em},
    sloped
    ]
    \node [blackTreeNode] {2}
    child { 
      node [blackTreeNode] {0}
      child { 
        node [externalBlackNode] {}} 
      child { 
        node [externalBlackNode] {}}
    } 
    child { 
      node [redTreeNode] {12}
      child { 
        node [blackTreeNode] {6}
        child { 
          node [externalBlackNode] {}} 
        child { 
          node [externalBlackNode] {}}
      } 
      child { 
        node [blackTreeNode] {19}
        child { 
          node [redTreeNode] {12}
          child { 
            node [externalBlackNode] {}} 
          child { 
            node [externalBlackNode] {}}
        } 
        child { 
          node [externalBlackNode] {}}
      }
    }
    ;
  \end{tikzpicture}
  \caption{\texttt{Umf\"arbung}}
\end{figure}

31 May 2017

Die fünfte Abgabe in DSAL.

Uebungsblatt 5 (Korrektur)

Hier der Java-Code, welcher (vielleicht) zur Generierung der RS-Bäume verwendet wurde. Im großen und ganzen ist er aus der Vorlesung von Prof. Woeginger geklaut. Theoretisch kann dieser Code durch minimale anpassung auch AVL- bzw normale binäre Bäume ausgeben, dies ist aber nicht getestet.

Damit LaTeX diese Figuren Compiliert, müssen die Requirements aus LaTeX-Snippets: Rot-Schwarz-Bäume erfüllt sein.

ACHTUNG: Die Methoden zum Löschen aus einem RS-Baum funktionieren aus einem mir nicht erklärbaren Grund nicht.

Ich entschuldige mich für die komische Formatierung, ich war zu faul Emacs umzustellen.

a11.java

public class a11{

    public static void main(String[] args){
	Tree t = new Tree();
	t.root = new Node();
	t.root.color=Color.BLACK;
	t.root.key=6;
	
	System.out.println("\\newsubsubproblem[1]");
	t.toTeX("\\texttt{Einf\\\"uge-Operation} von 6");
	
	//2
	System.out.println("\\newsubsubproblem[2]");
	Tree.rbtIns(t,new Node(0));

	//3.
	System.out.println("\\newsubsubproblem[3]");
	Tree.rbtIns(t,new Node(2));

	//4.
	System.out.println("\\newsubsubproblem[4]");
	Tree.rbtIns(t,new Node(19));

	//5.
	System.out.println("\\newsubsubproblem[5]");
	Tree.rbtIns(t,new Node(12));

	//6.
	System.out.println("\\newsubsubproblem[6]");
	Tree.rbtIns(t,new Node(12));
    }
}

Node.java:

public class Node {
    int key;
    Node left, right;
    Node parent;
    Color color;
    static Color BLACK = Color.BLACK;
    static Color RED = Color.RED;

    public Node(){
    }
    
    public Node(int k){
	key=k;
    }

    public Node(int k,Color c){
	key=k;
	color= c;
    }
    
    public Node(int k,Color c, Node l, Node r){
	key=k;
	color= c;
	left=l;
	right=r;
    }
    
    public String toTeX() {
        String result = "node [";
        if (color == RED) {
            result = result + "redTreeNode";
        } else {
            result = result + "blackTreeNode";
        }


        //Children

        result = result + "] {" + key + "}\nchild { \n";
        if (left == null) {
            result = result + "node [externalBlackNode] {}";
        } else {
            result = result + left.toTeX();
        }

        result = result + "} \nchild { \n";
        if(right==null)
        {
            result = result + "node [externalBlackNode] {}";
        }else
        {
            result = result + right.toTeX();
        }

        result=result+"}\n";
        return result;
    }
}

Tree.java

import java.lang.Math;

public class Tree{
    Node root;
    static Color BLACK = Color.BLACK;
    static Color RED = Color.RED;


    
//VL 10 Folie 16
    static void bstIns ( Tree t, Node node)
	{ // Fuege node in t ein
// Suche freien Platz
	    Node root = t.root;
	    Node parent = null;
	    while (root!=null)
	    {
		parent = root;
		if ( node.key < root.key ){
		    root = root.left;
		} else {
		    root = root.right;
		}
	    } // Einfuegen
	    node.parent = parent;
	    if (parent==null) { // t war leer = > neue Wurzel
		t.root = node;
	    } else if ( node.key < parent.key ) { // richtige Seite
		parent.left = node;
	    } else {
		parent.right = node;
	    }
	}
    
    
    //VL 10 Folie 22
    // Ersetzt im Baum t den Teilbaum old durch
// den Teilbaum node ( ohne Sortierung !)
    static void bstReplace ( Tree t , Node old , Node node ) {
	if ( node!=null ) { // erlaube node == null !
	    node.parent = old.parent;
	   % System.out.println("Node == null");
	} 
	if (old.parent==null) { // war die Wurzel
	    t.root = node ;
	} else if ( old == old.parent.left ) {
// war linkes Kind
	    old.parent.left = node ;
	} else { // rechtes Kind
	    old.parent.right = node ;
	}
    }
    
    static Node bstMin ( Node root ) { // root != null
	while ( root.left!=null) {
	    root = root.left ;
	}
	return root ;
    }
//VL 10 Folie 20
    static Node bstSucc ( Node node ) // node != nul
	{
	    if ( node.right!=null) {
		return bstMin ( node.right );
	    }
// Abbruch, wenn node nicht mehr rechtes Kind
// oder wenn node.parent leer
	    while ( node.parent!=null && node.parent.right == node ) {
		node = node.parent;
	    }
	    return node.parent;
	}

//VL 10 Folie 28

// Entfernt node aus dem Baum .
// Danach kann node ggf.aus Speicher entfernt werden
    static void bstDel ( Tree t, Node node )
	{
	    if ( node.left!=null && node.right!=null ) { // zwei Kinder
		Node tmp = bstMin ( node.right );
		bstDel (t, tmp ); // hochstens ein Kind, rechts
		bstSwap (t, node, tmp );
	    } else if ( node.left!=null ) { // ein Kind, links
		bstReplace (t, node, node.left );
	    } else { // ein oder kein Kind ( node.right == null )
		bstReplace (t, node, node.right );
	    }
	}

    
// Tauscht den Knoten old gegen node aus ;
// die Kinder von old sind weiterhin im BST !
    static  void bstSwap ( Tree t , Node old , Node node ) {
// uebernimm linken Teilbaum
	node.left = old.left ; // auch moeglich : swap ()
	if ( node.left!=null ) {
	    node.left.parent = node ;
	}
// rechten Teilbaum
	node.right = old . right ;
	if ( node.right!=null ) {
	    node.right.parent = node ;
	}
// fuege den Knoten ein
	bstReplace (t , old , node ) ;
    }

    
//VL 10 Folie 34
    static void leftRotate ( Tree t, Node node1 )
	{
// voellig analog : rightRotate ()
	    Node node2 = node1.right;
// Baum B verschieben
	    node1.right = node2.left;
	    if ( node1.right!=null ) {
		node1.right.parent = node1;
	    }
// node2 wieder einhaengen
	    node2.parent = node1.parent;
	    if ( node1.parent==null ) { // node1 war die Wurzel
		t.root = node2;
	    } else if ( node1 == node1.parent.left ) {
		node2.parent.left = node2;
	    } else { // war rechtes Kind
		node2.parent.right = node2;
	    }
// node1 einhaengen
	    node2.left = node1;
	    node1.parent = node2;
	    t.toTeX("\\texttt{Left-Rotate} \\\"uber "+node1.key);
	}

//VL 10 Folie 34
    static void rightRotate ( Tree t, Node node1 )
	{
// voellig analog : rightRotate ()
	    Node node2 = node1.left;
// Baum B verschieben
	    node1.left = node2.right;
	    if ( node1.left!=null ) {
		node1.left.parent = node1;
	    }
// node2 wieder einhaengen
	    node2.parent = node1.parent;
	    if ( node1.parent==null ) { // node1 war die Wurzel
		t.root = node2;
	    } else if ( node1 == node1.parent.right ) {
		node2.parent.right = node2;
	    } else { // war linkes Kind
		node2.parent.left = node2;
	    }
// node1 einhaengen
	    node2.right = node1;
	    node1.parent = node2;
	    t.toTeX("\\texttt{Right-Rotate} \\\"uber "+node1.key);
	}


//VL 10 Folie 39
    static void AVLIns ( Tree t, Node node ) {
	bstIns (t, node );
// Node d e e p e s t U n b a l a n c e d N o d e ( Tree t, Node node )
// gibt null zurueck wenn t balanziert ist
// und den tiefsten unbalan zierten Knoten in t sonst
// ( der Parameter node wird zur effizienten
// I mp l em en ti er u ng verwendet )
	Node A = deepestUnbalancedNode(t, node);
	if ( A != null ) balance (t, A );
    }

//VL 10 Folie 40
    static void balance ( Tree t, Node A ) {
// A ist tiefster unbala nzierter Knoten in t
	if ( height ( A.left ) > height ( A.right ) ) {
	    if ( height ( A.left.left ) >= height ( A.left.right ) ) {// LL
		rightRotate (t, A );
	    } else { // LR
		leftRotate (t, A.left ); rightRotate (t, A );
	    }
	} else {
	    if ( height ( A.right.right ) >= height ( A.right.left ) ) {
// RR
		leftRotate (t, A );
	    } else { // RL
		rightRotate (t, A.right ); leftRotate (t, A );
	    }
	}
    }


//VL 10 Folie 42
    static void AVLDel ( Tree t, Node node ) {
	bstDel (t, node );
// Node d e e p e s t U n b a l a n c e d N o d e ( Tree t, Node node )
// gibt null zurueck wenn t balanziert ist
// und den tiefsten unb alanzier ten Knoten in t sonst
//( der Parameter node wird zur effizienten
// Im pl e me nt ie r un g verwendet )
	Node A = deepestUnbalancedNode (t, node );
	while ( A != null )
	{
// bool balanced ( Tree t, Node A )
// gibt true zurueck wenn A balanziert ist in t
// und false sonst
	    if (! balanced (t, A ) ) {
		balance (t, A );
		A = A.parent.parent;
	    } else {
		A = A.parent;
	    }
	}
    }




    //VL 11 Folie 13
    static void rbtIns ( Tree t , Node node ) {
// Fuege node in den Baum t ein
	bstIns(t , node ) ; // Einfuegen wie beim BST
	node.left = null ;
	node.right = null ;
	node.color = RED ;
	t.toTeX("\\texttt{Einf\\\"uge-Operation} von "+node.key);
// eingefuegter Knoten immer zunaechst rot
// stelle Rot - Schwarz - Eigenschaft ggf . wieder her
	rbtInsFix (t , node ) ;
	
    }

    //VL 11 Folie 18
    // Behebe eventuelle Rot - Rot - Verletzung mit Vater
    // Knoten node ist rot
    static void rbtInsFix ( Tree t , Node node ) {
        // solange noch eine Rot - Rot - Verletzung besteht
	while ( node.parent != null && node . parent . color == RED ) {
	    if ( node . parent == node . parent . parent . left ) {
                // der von uns betrachtete Fall
		node = leftAdjust (t , node ) ;
                // node jetzt weiter oben ?
                // ( node = node . parent . parent im Fall 1 von
		// leftAdjust )
	    } else {
		// der dazu symmetrischer Fall
		node = rightAdjust (t , node ) ;
	    }
	}
	t . root . color = BLACK ; // Wurzel bleibt schwarz
    }
    
    //VL 11 Folie 19
    static Node leftAdjust ( Tree t , Node node ) {
	Node uncle = node.parent.parent.right ;
	if ( uncle != null && uncle.color == RED ) { // Fall 1
	    node.parent.parent.color = RED ; // Grossvater
	    node.parent.color = BLACK ; // Vater
	    uncle.color = BLACK ; // Onkel
	    t.toTeX("\\texttt{Umf\\\"arbung}");
	    return node.parent.parent ; // pruefe Rot - Rot weiter
	    // oben
	} else { // Fall 2 und 3
	    if ( node == node.parent.right ) { // Fall 2
                // dieser Knoten wird das linke , rote Kind :
		node = node.parent ;
		leftRotate (t , node ) ;
	    } // Fall 3
	    rightRotate (t , node . parent . parent ) ;
	    node.parent.color = BLACK ;
	    node.parent.right.color = RED ;
	    t.toTeX("\\texttt{Umf\\\"arbung}");
	    return node ; // fertig , node . parent . color == BLACK
	}
    }

   //Analog zu VL 11 FOlie 19
    static Node rightAdjust ( Tree t , Node node ) {
	Node uncle = node.parent.parent.left ;
	if ( uncle != null &&  uncle.color == RED ) { // Fall 1
	    node.parent.parent.color = RED ; // Grossvater
	    node.parent.color = BLACK ; // Vater
	    uncle.color = BLACK ; // Onkel
	    t.toTeX("\\texttt{Umf\\\"arbung}");
	    return node.parent.parent ; // pruefe Rot - Rot weiter
	    // oben
	} else { // Fall 2 und 3
	    if ( node == node.parent.left ) { // Fall 2
                // dieser Knoten wird das linke , rote Kind :
		node = node.parent ;
		rightRotate (t , node ) ;
	    } // Fall 3
	    leftRotate (t , node . parent . parent ) ;
	    node.parent.color = BLACK ;
	    node.parent.left.color = RED ;
	    t.toTeX("\\texttt{Umf\"arbung}");
	    return node ; // fertig , node . parent . color == BLACK
	}
    }

    //VL 11 Folie 29
    // Entfernt node aus dem Baum .
    static void rbtDel ( Tree t , Node node ) {
	if ( node . left!=null && node . right!=null ) { // zwei Kinder
	    Node tmp = bstMin ( node . right ) ; // finde Nachfolger
	    rbtDel (t , tmp ) ; // loesche Nachfolger
	    bstSwap (t , node , tmp ) ; // ersetze node durch Nfolger
	    t.toTeX("\\texttt{L\\\"oschung} von "+node.key);
	    tmp . color = node . color ; // uebernimm die Farbe
	    t.toTeX("\\texttt{Umf\\\"arbe-Operation}");
	} else { // ein Kind , oder kein Kind
	    Node child ; // Hilfsvariable
	    if ( node . left!= null ) child = node . left ; // Kind ist links
	    else if ( node . right!= null ) child = node . right ; // rechts
	    else child = null ; // kein Kind
	    rbtDelFix (t , node , child ) ;
	    t.toTeX("\\texttt{L\\\"oschung} von "+node.key+" mit "+
		    "anschlie\\ss{}ender \\texttt{Umf\\\"arbung}");
	    bstReplace (t , node , child ) ;
	}
    }

    //VL 11 Folie 32
    // node soll geloescht werden , child ist einziges Kind
    // ( bzw . node hat keine Kinder , und child == null ) ;
    // Ist node rot , so ist nichts zu tun ; sonst suchen wir
    // einen roten Knoten , der durch Umfaerben auf schwarz
    // die schwarze Farbe von node uebernimmt
    static void rbtDelFix ( Tree t , Node node , Node child )
	{
	    if ( node . color == RED ) return ;
	    if ( child != null && child . color == RED ) {
		child . color = BLACK ;
	    } else {
		Node searchPos = node ;
		// solange Schwarzwert nicht eingefuegt werden kann
		while ( searchPos . parent != null && searchPos . color == BLACK ) {
		    if ( searchPos == searchPos . parent . left ) // linkes Kind
		    searchPos = delLeftAdjust (t , searchPos ) ;
		    else // rechtes Kind
			searchPos = delRightAdjust (t , searchPos ) ;
		}
		searchPos . color = BLACK ;
	    }
	}
    
    //VL 11 Folie 33
    // Erleichtert node um einen Schwarzwert ,
    // wobei node das linke Kind ist .
    static Node delLeftAdjust ( Tree t , Node node )
	{
// brother existiert immer wegen Schwarzhoehe
	    Node brother = node . parent . right ;
	    if ( brother . color == RED ) {
// Fall 1: Reduktion auf 2 ,3 ,4
		brother . color = BLACK ;
		node . parent . color = RED ; // Vater
		leftRotate (t , node . parent ) ;
		brother = node . parent . right ; // nun Bruder von node
	    }
	    if ( brother . left . color == BLACK &&
		 brother . right . color == BLACK ) { // Fall 2
		brother . color = RED ;
		return node . parent ; // Doppel - schwarz weiter oben ...
	    } else { // Fall 3 und 4
		if ( brother . right . color == BLACK ) {// Fall 3
		    brother . left . color = BLACK ;
		    brother . color = RED ;
		    rightRotate (t , brother ) ;
		    brother = node . parent . right ; // nun Bruder von node
		} // Fall 4
		brother . color = node . parent . color ;
		node . parent . color = BLACK ;
		brother . right . color = BLACK ;
		leftRotate (t , node . parent ) ;
		return t . root ; // Fertig .
	    }
	}

    static Node delRightAdjust ( Tree t , Node node )
	{
// brother existiert immer wegen Schwarzhoehe
	    Node brother = node . parent . left ;
	    if ( brother . color == RED ) {
// Fall 1: Reduktion auf 2 ,3 ,4
		brother . color = BLACK ;
		node . parent . color = RED ; // Vater
		rightRotate (t , node . parent ) ;
		brother = node . parent . left ; // nun Bruder von node
	    }
	    if ( brother . right . color == BLACK &&
		 brother . left . color == BLACK ) { // Fall 2
		brother . color = RED ;
		return node . parent ; // Doppel - schwarz weiter oben ...
	    } else { // Fall 3 und 4
		if ( brother . left . color == BLACK ) {// Fall 3
		    brother . right . color = BLACK ;
		    brother . color = RED ;
		    leftRotate (t , brother ) ;
		    brother = node . parent . left ; // nun Bruder von node
		} // Fall 4
		brother . color = node . parent . color ;
		node . parent . color = BLACK ;
		brother . left . color = BLACK ;
		rightRotate (t , node . parent ) ;
		return t . root ; // Fertig .
	    }
	}
    




    
    //Eigene Methoden
    static Node deepestUnbalancedNode(Tree t, Node a)
	{
	    Node unbalancedLeft = deepestUnbalancedNode(t,a.left);
	    Node unbalancedRight = deepestUnbalancedNode(t,a.right);
	    if(unbalancedRight == null){
		if(unbalancedLeft != null){
		    return unbalancedLeft;
		}else{
		    if(Math.abs(height(a.left)-height(a.right))==2){
			return a;
		    }else{
			return null;
		    }
		}
	    }else{
		if(unbalancedLeft == null){
		    return unbalancedRight;
		}else{
		    //Beides unbalanciert
		    if(height(unbalancedLeft)<=height(unbalancedRight)){
			return unbalancedLeft;
		    }else{
			return unbalancedRight;
		    }
		}
	    }
	}
    
    
    static int height(Tree t){
	return height(t.root);
    }
    
    static int height(Node a){
	if(a==null){
	    return 0;
	}
	return Math.max(height(a.left),height(a.right))+1;
    }

    static boolean balanced(Tree t, Node a){
	return deepestUnbalancedNode(t,a) == null;
    }

    String toTeX(){
	return toTeX("");
    }
    
    String toTeX(String caption){
	String TeX = "\\begin{figure}[H]\n"+
	    "\\centering\n"+
	    "\\begin{tikzpicture}\n"+
	    "[sibling distance        = 3em,\n"+
	    " level distance          = 3em,\n"+
	    " edge from parent/.style = {draw, -latex},\n"+
	    " every node/.style       = {font=\\footnotesize},\n"+
	    " level 1/.style={sibling distance=8em},\n"+
	    " level 2/.style={sibling distance=4em},\n"+
	    " level 3/.style={sibling distance=2em},\n"+
	    " level 4/.style={sibling distance=1em},\n"+
	    " sloped\n"+
	    "]\n"+
	    "\\"+root.toTeX()+
	    ";\n"+
	    "\\end{tikzpicture}\n"+
	    "\\caption{"+caption+"}\n"+
	    "\\end{figure}\n";
	System.out.println(TeX);
	return TeX;
    }
}

23 May 2017

Die dritte Abgabe in FoSAP.

Uebungsblatt 3

Die Implementation des in Aufgabe 6 geforderten Algorithmus, der endliche reguläre Ausdrücke erkennt.

f :: [Char] -> Bool -> Bool
f (')':ss:s) b = b && if ss=='0' then (f ('0':s) True) else (f ('a':ss:s) True)
f (')':s) b = b && (f ('a':s) b)
f ('+':s) b = b && (f s b)
f ('0':s) _ = f s True
f ('0':'*':s) _ = f s True

f ('E':s) _ = f s True
f (a:'*':[]) _ = False
f (a:'*':s:ss:sss) b = if (s=='0') then (f (ss:sss) True)
                       else (if (s==')' && ss == '0') then (f sss True )
                        else (b && (f (s:ss:sss) False)))
f (a:'?':s) _ = f (a:a:"*") False && (f s True)

23 May 2017

LaTeX-Schnipsel zur Visualisierung von Sortierungsalgorithmen (z.B. Aufgabe 4 von DSAL Abgabe 3)

Benötigte Pakete sowie benutzte Style Settings:

\usepackage{tikz}
\usetikzlibrary{shapes,arrows,positioning,decorations,
  automata,backgrounds,petri,bending,
  shapes.multipart
} %Eventuell sind nicht alle nötig
\usepackage{pgf}

\tikzset{
  treenode/.style = {shape=circle, rounded corners,
    draw, align=center},
  graynode/.style = {fill=gray},
  normal/.style     = {treenode, font=\Large, bottom color=white}
  }

\begin{figure}[H]
  \centering
  \subfloat[Heap vor dem Sortieren.]
  {
    \begin{tikzpicture}
      [
      sibling distance        = 3em,
      level distance          = 3em,
      edge from parent/.style = {draw, -latex},
      every node/.style       = {font=\footnotesize},
      level 1/.style={sibling distance=6em},
      level 2/.style={sibling distance=3em},
      sloped
      ]
      \node [treenode] {5}
      child {node [treenode] {7}
        child {node [treenode] {4}}
        child {node [treenode] {2}}}
      child {node [treenode] {97}
        child {node [treenode] {42}}
        child[fill=none] {edge from parent[draw=none]}};
      
      
    \end{tikzpicture}
  }
  \subfloat[Heap-Array vor dem sortieren.]
  {
    \begin{tikzpicture}
      \node[array, name = array, rectangle split parts=6,draw] at (0,1)
      {\nodepart{one}5
        \nodepart{two}7
        \nodepart{three}97
        \nodepart{four}4
        \nodepart{five}2
        \nodepart{six}42
      };
      \draw [<->] (array.one north) |- ++(0,0.4) -| (array.three north);
    \end{tikzpicture}
  }
  
  \subfloat[Heap vor dem Sortieren.]
  {
    \begin{tikzpicture}
      [
      sibling distance        = 6em,
      level distance          = 3em,
      edge from parent/.style = {draw, -latex},
      every node/.style       = {font=\footnotesize},
      level 1/.style={sibling distance=6em},
      level 2/.style={sibling distance=3em},
      sloped
      ]
      \node [treenode] {97}
      child {node [treenode] {7}
        child {node [treenode] {4}}
        child {node [treenode] {2}}}
      child {node [treenode] {5}
        child {node [treenode](left node) {42}}
        child[fill=none] {edge from parent[draw=none]}};
      
      
    \end{tikzpicture}
  }
  \subfloat[Heap-Array vor dem sortieren.]
  {
    \begin{tikzpicture}
      \node[array, name=array, rectangle split parts=6] at (0,1)
      {\nodepart{one}97
        \nodepart{two}7
        \nodepart{three}5
        \nodepart{four}4
        \nodepart{five}2
        \nodepart{six}42
      };
      \draw [<->] (array.three north) |- ++(0,0.4) -| (array.six north);
    \end{tikzpicture}
  }
  
  \caption[Heap Aufbau]{Aufbau des Heaps }
  \label{fig:a6_heapsort_1}
\end{figure}

22 May 2017

LaTeX-Schnipsel zur Visualisierung von Sortierungsalgorithmen (z.B. Aufgabe 5 von DSAL Abgabe 3)

Benötigte Pakete:

\usepackage{tikz}
\usetikzlibrary{shapes,arrows,positioning,decorations,
  automata,backgrounds,petri,bending,
  shapes.multipart
} %Eventuell sind nicht alle nötig
\tikzset{
 array/.style = {rectangle split, rectangle split horizontal,
 	         draw}
}

\usepackage{pgf}


\begin{tikzpicture}[ level 1/.style={sibling distance=30mm}, level
  2/.style={sibling distance=30mm}, level 3/.style={sibling
    distance=20mm}]
  % Layer 0
  \node[array,rectangle split parts=9] at (-0.25,0)
  {14
    \nodepart{two}97
    \nodepart{three}7
    \nodepart{four}42
    \nodepart{five}12
    \nodepart{six}3
    \nodepart{seven}5
    \nodepart{eight}2
    \nodepart{nine}7 };

  % Layer 1
  \node[style=array, rectangle split parts=5,color=gray] at (-1.9,-1)
  {14
    \nodepart{two}97
    \nodepart{three}7
    \nodepart{four}42
    \nodepart{five}12
  };
  \node[array,rectangle split parts=4,color=gray] at (1.75,-1)
  {3
    \nodepart{two}5
    \nodepart{three}2
    \nodepart{four}7};

  % Layer 2
  \node[array, rectangle split parts=3,color=gray] at (-2.75,-2)
  {14
    \nodepart{two}97
    \nodepart{three}7
  };
  \node[array, rectangle split parts=2,color=gray] at (-.9,-2)
  {42
    \nodepart{two}12
  };
  \node[array,rectangle split parts=4, draw,color=gray] at (1.75,-2)
  {3
    \nodepart{two}5
    \nodepart{three}2
    \nodepart{four}7};
  
  % Layer 3
  \node[array, rectangle split parts=2,color=gray] at (-3.3,-3)
  {14
    \nodepart{two}97
  };
  \node[array, rectangle split parts=1,color=gray] at (-2.2,-3)
  {7};
  \node[array, rectangle split parts=2,color=gray] at (-.9,-3)
  {42
    \nodepart{two}12
  };
  \node[array,rectangle split parts=4, draw,color=gray] at (1.75,-3)
  {3
    \nodepart{two}5
    \nodepart{three}2
    \nodepart{four}7
  };
  
  
  % Layer 4
  \node[array, rectangle split parts=1,color=gray] at (-3.75,-4)
  {14
  };
  \node[array, rectangle split parts=1,color=gray] at (-3,-4)
  {97};
  \node[array, rectangle split parts=1,color=gray] at (-2.2,-4)
  {7};
  \node[array, rectangle split parts=2,color=gray] at (-.9,-4)
  {42
    \nodepart{two}12
  };
  \node[array,rectangle split parts=4,color=gray] at (1.75,-4)
  {3
    \nodepart{two}5
    \nodepart{three}2
    \nodepart{four}7
  };

  % Layer 5
  \node[array, rectangle split parts=2] at (-3.3,-5)
  {14
    \nodepart{two}97
  };
  \node[array, rectangle split parts=1] at (-2.2,-5)
  {7};
  \node[array, rectangle split parts=2] at (-.9,-5)
  {42
    \nodepart{two}12
  };
  \node[array,rectangle split parts=4, draw] at (1.75,-5)
  {3
    \nodepart{two}5
    \nodepart{three}2
    \nodepart{four}7
  };

  % Layer 6
  \node[array, rectangle split parts=3] at (-2.75,-6)
  {7
    \nodepart{two}14
    \nodepart{three}97
  };
  \node[array, rectangle split parts=2] at (-.9,-6)
  {42
    \nodepart{two}12
  };
  \node[array,rectangle split parts=4, draw] at (1.75,-6)
  {3
    \nodepart{two}5
    \nodepart{three}2
    \nodepart{four}7
  };

  % Layer 7
  \node[array, rectangle split parts=3, color=gray] at (-2.75,-7)
  {7
    \nodepart{two}14
    \nodepart{three}97
  };
  \node[array, rectangle split parts=1, color=gray] at (-1.3,-7)
  {42};
  \node[array,rectangle split parts=1, color=gray] at (-.5,-7)
  {12 };
  \node[array,rectangle split parts=4, color=gray] at (1.75,-7)
  {3
    \nodepart{two}5
    \nodepart{three}2
    \nodepart{four}7
  };

  % Layer 8
  \node[array, rectangle split parts=3] at (-2.75,-8)
  {7
    \nodepart{two}14
    \nodepart{three}97
  };
  \node[array, rectangle split parts=2] at (-.9,-8)
  {12
    \nodepart{two}42
  };
  \node[array,rectangle split parts=4, draw] at (1.75,-8)
  {3
    \nodepart{two}5
    \nodepart{three}2
    \nodepart{four}7
  };

  % Layer 9
  \node[style=array, rectangle split parts=5] at (-1.9, -9)
  {7
    \nodepart{two}12
    \nodepart{three}14
    \nodepart{four}42
    \nodepart{five}97
  };
  \node[array,rectangle split parts=4, draw] at (1.75,-9)
  {3
    \nodepart{two}5
    \nodepart{three}2
    \nodepart{four}7
  };

  % Layer 10
  \node[style=array, rectangle split parts=5,color=gray] at (-1.9, -10)
  {7
    \nodepart{two}12
    \nodepart{three}14
    \nodepart{four}42
    \nodepart{five}97
  };
  \node[array, rectangle split parts=2,color=gray] at (1.25,-10)
  {3
    \nodepart{two}5
  };
  \node[array, rectangle split parts=2,color=gray] at (2.5,-10)
  {2
    \nodepart{two}7
  };

  % Layer 11
  \node[style=array, rectangle split parts=5,color=gray] at (-1.9, -11)
  {7
    \nodepart{two}12
    \nodepart{three}14
    \nodepart{four}42
    \nodepart{five}97
  };
  \node[array ,rectangle split parts=1,color=gray] at (.9,-11)
  {3 };
  \node[array ,rectangle split parts=1,color=gray] at (1.5,-11)
  {5 }; 
  \node[array, rectangle split parts=2,color=gray] at (2.5,-11)
  {2
    \nodepart{two}7
  };
  
  % Layer 12
  \node[style=array, rectangle split parts=5] at (-1.9, -12)
  {7
    \nodepart{two}12
    \nodepart{three}14
    \nodepart{four}42
    \nodepart{five}97
  };
  \node[array, rectangle split parts=2] at (1.25,-12)
  {3
    \nodepart{two}5
  };
  \node[array, rectangle split parts=2] at (2.5,-12)
  {2
    \nodepart{two}7
  };
  
  % Layer 13
  \node[style=array, rectangle split parts=5,color=gray] at (-1.9, -13)
  {7
    \nodepart{two}12
    \nodepart{three}14
    \nodepart{four}42
    \nodepart{five}97
  };
  \node[array, rectangle split parts=2,color=gray] at (1.25,-13)
  {3
    \nodepart{two}5
  };
  \node[array, rectangle split parts=1,color=gray] at (2.3,-13)
  {2 };
  \node[array,rectangle split parts=1,color=gray] at (3,-13)
  {7 };

\end{tikzpicture}

Zweite Hälfte:

\begin{tikzpicture}[ level 1/.style={sibling distance=30mm}, level
  2/.style={sibling distance=30mm}, level 3/.style={sibling
    distance=20mm}]

  % Layer 14
  \node[style=array, rectangle split parts=5] at (-1.9, -14)
  {7
    \nodepart{two}12
    \nodepart{three}14
    \nodepart{four}42
    \nodepart{five}97
  };
  \node[array, rectangle split parts=2] at (1.25,-14)
  {3
    \nodepart{two}5
  };
  \node[array, rectangle split parts=2] at (2.5,-14)
  {2
    \nodepart{two}7
  };

  
  % Layer 14
  \node[style=array, rectangle split parts=5] at (-1.9, -15)
  {7
    \nodepart{two}12
    \nodepart{three}14
    \nodepart{four}42
    \nodepart{five}97
  };
  \node[array,rectangle split parts=4, draw] at (1.75,-15)
  {2
    \nodepart{two}3
    \nodepart{three}5
    \nodepart{four}7
  };
  
  \node[array,rectangle split parts=9] at (-0.25,-16)
    {2
      \nodepart{two}3
      \nodepart{three}5
      \nodepart{four}7
      \nodepart{five}7
      \nodepart{six}12
      \nodepart{seven}14
      \nodepart{eight}42
      \nodepart{nine}97 };

\end{tikzpicture}

(Diese Trennung wurde wegen der Länge des Bildes eingeführt)

22 May 2017

Die vierte Abgabe in DSAL.

Wer Fehler findet, kann sich bitte bei uns melden.

23.05.2017: v-tron hat einen Fehler in Aufgabe 5 der visualisierung des Quicksort-Algorithmus gefunden. Es fehlten einige Zwischenschritt, welche nun hinzugefügt wurden.

Uebungsblatt 4(Korrektur)

Hier der Java-Code, der zur generierung der Quicksortvisualisierung genutzt wurde. Nicht vergessen das gesamte dann in eine geeignete tikz-Umgebung zu setzen.

public class aufgabe5{
    static int[] E = {5,4,0,9,2,1,3,7,6,8};
    static String[] num = {"one", "two", "three", "four", "five", "six",
			   "seven", "eight", "nine", "ten", "eleven", "twelve"};
    //static int[] E = {3,7,9,1,2,4,8,6};
    public static void main(String[] args){
	tex();
	quickSort(0, E.length -1);	
	tex();	
    }

    static void swap(int l, int r){
	int tm = E[l];
	E[l] = E[r];
	E[r] = tm;
    }
    
    static void quickSort(int left, int right) {
	if (left < right) {
	    int i = partition(left, right);
	    // i ist Position des Split -punktes (Pivot)
	    quickSort(left, i-1); // sortiere linken Teil
	    quickSort(i+1, right); // sortiere rechten Teil
	}
    }
    
    static int partition(int left, int right) {
	// Waehle einfaches Pivotelement
	int ppos = right , pivot = E[ppos];
	right --; // Pivot ausgenommen
	while (true) {
	    // Bilineare Suche
	    while (left < right && E[left] < pivot) left++;
	    while (left < right && E[right] >= pivot) right --;
	    if (left >= right) {
		break;
	    }
	    swap(left, right);
	}
	if (E[left]<pivot) {
	    tex();
	    return ppos; // nur bei (left==ppos -1) moeglich
	}
	swap(left, ppos);

	tex();
	return left; // gib neue Pivotposition zurueck
    }


    static void tex(){
	System.out.println("\\subfloat[X ter Aufruf der Partition-Operation.]");
	System.out.println("{");
	System.out.println("\\begin{tikzpicture}");
	System.out.println("\\node[rectangle split, rectangle split horizontal,rectangle split parts=10,draw] at (0,1)");
	System.out.print("{");
	int j = 0;
	for(int i : E){
	    System.out.println("\\nodepart{" + num[j] + "} " + i);
	    j++;
	}
	System.out.println("};");
	System.out.println("\\end{tikzpicture}");
	System.out.println("}");
	System.out.println("");	
    }
}