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("");	
    }
}