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ę.