StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POquicksort special case - seems to be a faulty algorithm from K&R
text
Body
copied!<p>I have a problem understanding quicksort algorithm (the simplified version without pointers) from K&R. There is already a thorough explanation provided by Dave Gamble here <a href="https://stackoverflow.com/questions/1231254/kr-qsort-example-with-pointers-and-arrays-confusion">explanation</a>. However I noticed that by starting with a slightly changed string we can obtain no swaps during many loops of the for loop. Firstly the code:</p> <pre><code>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); } </code></pre> <p>Walkthrough in my opinion:</p> <p>we start with CADBE; left=0; right=4; D is the pivot so according to algorithm we swap D with C obtaining DACBE</p> <p>last = left =0</p> <p>i = 1 if ( v<a href="https://stackoverflow.com/questions/1231254/kr-qsort-example-with-pointers-and-arrays-confusion">1</a> < v[0] ) it is true so we swap v<a href="https://stackoverflow.com/questions/1231254/kr-qsort-example-with-pointers-and-arrays-confusion">1</a> (because last is incremented before operation) with v<a href="https://stackoverflow.com/questions/1231254/kr-qsort-example-with-pointers-and-arrays-confusion">1</a> so nothing changes, last = 1, still having DACBE;</p> <p>now i = 2 if ( v[2] < v[0] ) -> true so we swap v[2] with v[2] nothing changed again; last = 2</p> <p>now i = 3 if ( v[3] < v[0] ) -> true so we swap v[3] with v[3] nothing changed AGAIN (!), last = 3</p> <p>So apparently something is wrong, algorithm does nothing. Your opinions appreciated very much. I must be wrong, authors are better than me ;D Thanks in advance!</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload