problem z analizą quicksort'a

0

Witam, mam problem ze zrozumieniem quicksorta ujętego w K&R. Znalazłem bardzo przydatny post usera StackOverflow jednak pominął on pewien przypadek, który mnie nurtuje. Link [url]http://stackoverflow.com/questions/1231254/kr-qsort-example-with-pointers-and-arrays-confusion[/url]
Tu jest kod:

void qsort(int v[], int left, int right)
{
	int i, last;
	void swap(int v[], int i, int j);
	
	if (left >= right) /* do nothing if array contains */
		return; 	/* fewer than two elements */
	swap(v, left, (left + right)/2); /* move partition elem */
	last = left;    		/* to v[0] */
	for (i = left + 1; i <= right; i++) /* partition */
		if (v[i] < v[left])
			swap(v, ++last, i);
	swap(v, left, last);  		/* restore partition elem */
	qsort(v, left, last-1);
	qsort(v, last+1, right);
}
 

Przebieg (moim zdaniem):

Zaczynamy od CADBE left=0 right=4, pivotem jest D
więc zamieniamy z pozycją left -> DACBE
last = left = 0
i = 1 if ( v[1] < v[0] ) jest to prawda więc robimy swap v[1] (bo last inkrementujemy PRZED operacją) z v[1] (tyle wynosi i) czyli nic się nie zmienia, last = 1 nadal mamy DACBE
teraz i = 2 if( v[2] < v[0] ) prawda więc robimy swap v[2] z v[2] ZNOWU NIC SIĘ NIE ZMIENIA, last = 2
teraz i = 3 if ( v[3] < v[0] ) prawda więc robimy swap v[3] z v[3] ZNOWU BEZ ZMIAN, last = 3

Wychodzi więc na to, że jest tu jakąs wada algorytmu. Prosiłbym o spostrzeżenia, może źle myślę.

0

http://ideone.com/jyi2K
Proponuję prześledzić wykonywanie kodu w debuggerze

1 użytkowników online, w tym zalogowanych: 0, gości: 1