Timeline for What if Indexes in Hoare's Quick Sort Algorithm Both Land on Values Less than Pivot?
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 28, 2018 at 13:47 | comment | added | Bulat | @Apass.Jack David,yes - Wikipedia is incorrect saying that the algo always find an inversion. OTOH, this allows to simplify the description, focusing on the most important point of the algorithm at the first approach. So I'm not sure how it should be edited. Anyway, it should be obvious for you that wikipedia description and algo text contradict each other. | |
| Aug 28, 2018 at 10:11 | comment | added | David Richerby | @Apass.Jack Wikipedia's description of the algorithm says that array elements are only swapped if they are in the wrong order, relative to one another; their pseudocode swaps them regardless. | |
| Aug 28, 2018 at 9:16 | comment | added | John L. | I am not sure what you imply by your last comment, "the Wikipedia article contradicts itself". Let me state the fact in a way that is independent of Wikipedia, as pointed out by @Bulat: the algorithm you stated does not work in some (corner) cases. | |
| Aug 22, 2018 at 15:33 | comment | added | David Richerby | Well, then the Wikipedia article contradicts itself. Woo. | |
| Aug 22, 2018 at 15:32 | comment | added | John L. | According to @Bulat's careful analysis, in order to avoid endless loop, we do need to switch when both pointers stop on values equal to the pivot. | |
| Aug 22, 2018 at 15:24 | comment | added | John L. | The version in the Wikipedia does swap identical elements as I have verified by tracing an actual program. Have you done the same? You can also check, for example, a stackoverflow answer on why does Hoare partitioning work, where you can find the following. "Note that sometimes the i and j pointer will actually both stop on E values. When this happens, the values will be switched, even though there's no need for it." | |
| Aug 22, 2018 at 15:03 | comment | added | David Richerby | @Apass.Jack OK, fixed. But neither the version I originally described nor the version in the Wikipedia article will ever swap identical elements so I'm not sure there was a huge issue. | |
| Aug 22, 2018 at 14:58 | history | edited | David Richerby | CC BY-SA 4.0 |
Wikipedia uses a slightly different version of the algorithm
|
| Aug 22, 2018 at 2:04 | comment | added | John L. | If we just want to answer the specific question of OP, "What if ... both land on Values Less than Pivot?" (not on values equals to Pivot), then this answer may make more sense, since if the algorithm exchanges two equal elements, then both elements will must be equal to the Pivot. | |
| Aug 22, 2018 at 1:48 | comment | added | John L. | Of course, this answer might be updated to claim that the algorithm can use extra steps to detect whether the elements encountered are equal (to the pivot value) and NOT exchange the two elements in those situations. However, we will then have, apparently, an uncommon version of the algorithm that is not the topic of this question. | |
| Aug 22, 2018 at 1:39 | comment | added | John L. | This answer contradicts the description of the algorithm at wikipedia item, which reads, "Hoare uses two indices that start at the ends of the array being partitioned, then move toward each other, until they detect an inversion: a pair of elements, one greater than or equal to the pivot, one lesser or equal, that are in the wrong order relative to each other. The inverted elements are then swapped" (bold font added by me). Note the "equal to" part in the description is critical in this question and all its answers. | |
| Aug 20, 2018 at 11:55 | comment | added | Bulat | Not really. On cs.stackexchange.com/questions/92562/… I analyzed various variants of the partition algo. | |
| Aug 20, 2018 at 11:11 | history | answered | David Richerby | CC BY-SA 4.0 |