[C] Mergesort mit O(log n) zusätzlichem Speicherbedarf

[p1ttypl4tsch]

Hallo,

für die Uni sollen wir einen Mergesortalgrithmus schreiben, der auf einfach verketteten Listen basiert und höchstens O(log n) zusätzlichen Speicher benötigt.

Das Mergesort an sich ist kein Problem, aber die die Zusatzbedingung, dass nur O(log n) zusätzlicher Speicher verwendet werden darf, ist dann doch schon ein wenig Tricky.

Vllt könnt ihr mir ja helfen.

Mein Code bisher (Visual Studio 2010):

typedef struct _list{
	int elem;
	struct _list *next;
}ListRec, *List;

...

List msort(List l){
	List slow, fast, right;
	slow = l; fast = l->next;
	while(fast){	//Split: Wenn "fast" am Ende der Liste ist, ist "slow" in der Mitte
		if(fast->next){
			fast = fast->next->next;
			slow = slow->next;
		}else
			break;
	}
	right = slow->next;
	slow->next = NULL;
	if(l->next){
		l = msort(l);
		right = msort(right);
	}
	return merge(l, right);
}

List merge(List left, List right){
	List tmp = (List)malloc(sizeof(ListRec));
	if(!right && left){	
		tmp->elem = left->elem;
		tmp->next = merge(left->next, right);
		return tmp;
	}
	else if(right && !left){
		tmp->elem = right->elem;
		tmp->next = merge(left, right->next);
		return tmp;
	}
	if(right && left){
		if(left->elem <= right->elem){
			tmp->elem = left->elem;
			tmp->next = merge(left->next, right);
			return tmp;
		}else if(left->elem > right->elem){
			tmp->elem = right->elem;
			tmp->next = merge(left, right->next);
			return tmp;
		}
	}else
		return NULL;
}

 

[deepthroat]

Hi.

Kennst du denn die Geschichte mit dem Bauern, der Weizenkörner auf einem Schachbrett als Entlohnung verlangt? Ein Körnchen auf dem ersten Feld, 2 Körnchen auf dem zweiten Feld, 4 Körnchen auf dem dritten Feld usw.

Das sind ziemlich viele Körnchen... die Anzahl wächst stark exponentiell.

Umgekehrt kannst du das ganze mit der Liste machen.

Verwende x temp. Listen. Die erste Liste enthält (wenn gefüllt) 1 Element, die zweite 2, die dritte 4 usw.

Du entfernst immer ein Element aus der zu sortierenden Liste und vereinigst "benachbarte" temp. Listen.

Bsp:
tmp = [] // tmp. Listen
tmp = [[1]]
tmp = [[], [1, 2]]
tmp = [[3], [1, 2]]
tmp = [[], [], [1, 2, 3, 4]]

Wenn die zu sortierende Liste leer ist, vereinigst du alle temp. Listen und bist fertig.

Das nur mal so als Anregung...

Gruß

 

[p1ttypl4tsch]

Hi deepthroat,

danke für deine Antwort.
Ich habs jetzt hinbekommen (denke ich), es wird auf jeden Fall kein zusätzlicher Speicher mehr verschwendet (Stack ausgenommen, aber das geht ja nicht anders, da es ja einfach verkettete Listen sind und man sonst, also Iterativ, keine vernünftige Sortierung hinbekommt ... oder?!).

Mein Code sieht jetzt wie folgt aus (nur noch die Merge-Funktion):

List merge(List left, List right){
	if(left && right){
		if(left->elem < right->elem){
			left->next = merge(left->next, right);
			return left;
		}else{
			right->next = merge(left, right->next);
			return right;
		}
	}else if(!left){
		return right;
	}else if(!right){
		return left;
	}
}

 

[deepthroat]

Hi.

Ich habs jetzt hinbekommen (denke ich), es wird auf jeden Fall kein zusätzlicher Speicher mehr verschwendet (Stack ausgenommen, aber das geht ja nicht anders, da es ja einfach verkettete Listen sind und man sonst, also Iterativ, keine vernünftige Sortierung hinbekommt ... oder?!).

Doch, natürlich geht das auch iterativ.

Gruß

 

[Eburneolus]

Beim iterativen sortieren mittels Mergesort, zerlegst du die Liste nicht erst im rekursiven Abstieg.
Anhand der Länge weist du wieviel Sortierschritte durchgeführt werden müssen, nämlich log2.
Im ersten Iterationsschrit betrachtest du immer Zweierpaare und sortierst die, im zweiten Schritt betrachtes du Paare von Zweierpaaren und sortierst Sie....
Das Sortierverfahren der Paare unterscheidet sich nicht wesentlich von dem merge() welches beim rekursiven Aufstieg ausgeführt wird. Zeitkomplexität ist hier wie im rekrusiven Fall O(nlog2) und die Speicherplatzkomplexität kann als O(1) realisiert werden.