Frage zu Altklausur WS12/13 Aufgabe 7b)

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Frage zu Altklausur WS12/13 Aufgabe 7b)
Hallo,

kann mir jemand die Aufgabe 7 in der WS12/13 Klausur erklären. Ich hänge beim Aufgabenteil b) und verstehe nicht was der Gedanke hinter den Operationen ist.

Viele Grüße

3

Es wäre einfacher, wenn du die Aufgabe einfach anhängst :slight_smile:
Dann muss man die Altklausur nicht extra raussuchen.

4 
import java.util.Arrays;


public class Sort {
	int[] values;
	
	// primitive bubblesort
	void groupSort(int left, int right) {
		boolean changed = true;
		for(int j = 0; j <= right && changed; j++) {
			changed = false;
			for(int i = left; i < right - j; i++) {
				if(values[i] > values[i+1]) {
					swap(i, i+1);
					changed = true;
				}
			}
		}
	}
	
	void swap(int i, int j) {
		int tmp = values[i];
		values[i] = values[j];
		values[j] = tmp;
	}
	
	int partition(int left, int right, int index) {
		swap(right, index);
		index = right;
		
		int j = left - 1;
		for(int i = left; i < right; i++) {
			if(values[i] < values[index]) {
				j++;
				swap(i, j);
			}
		}
		j++;
		swap(j, index);
		
		return j;
	}
	
	void prepareGroups(int left, int right) {
		int lower = left;
		while(lower <= right) {
			int median = lower + 2;
			int upper = lower + 4;
			
			if(upper > right) {
				upper = right;
				median = lower + (upper - lower) / 2;
			}
			
			groupSort(lower, upper);
			swap(lower, median);
			
			lower += 5;
		}
	}
	
void pivotFirst(int left, int right) {
		if(left >= right)
			return;
		
		prepareGroups(left, right);
		
		int nextMedianPos = left;
		for(int i = left; i <= right; i+= 5)
			swap(i, nextMedianPos++);
		
		pivotFirst(left, nextMedianPos - 1);
	}
	
	void quickSortMedian(int left, int right) {
		if(left < right) {
			int indexOfPivot = left;
			
			pivotFirst(left, right);			
			int index = partition(left, right, left);
			
			quickSortMedian(left, index - 1);
			quickSortMedian(index + 1, right);
		}
	}
	
	public static void main(String[] args) {
		Sort s = new Sort();
		s.values = new int[] {4, 1, 8, 2, 6, 7, 6, 3, 2, 9};
		int l = 0;
		int r = s.values.length - 1;
		
		s.quickSortMedian(l, r);
		
		System.out.println(Arrays.toString(s.values));
	}
}
5

Jetzt hast du die Frage vergessen :slight_smile:

6

Ich war noch gerade am Code anpassen haha

Was ist der Gedanke bei der Methode PivotFirst alle Pivotelemente an den Anfang des Arrays zu schieben?