Jump to content

Talk:Quicksort: Difference between revisions

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
Sytelus (talk | contribs)
198 edits
→‎Error in code: Fixed plus added context of the previous version of the code
Line 86: Line 86:
: After edit-conflict:
: After edit-conflict:
:: The Sytelus's code fails for example on the array [7, 5]. First <code>pivot</code> becomes 5. The first <code>do-while</code> loop increments <code>i</code> and exits, because 7 is not less than 5. The second loop decrements <code>j</code>, then finds <code>A[lo]</code> greater than <code>pivot</code>, decrements again and ...tests the item which is ''outside'' (before, strictly speaking) the range being partitioned, because {{nowrap|1=<code>i == lo-1</code>}}. <br/> Your modified version fails to increment <code>i</code> if the first (leftmost) item of the array is greater than, or equal to, <code>pivot</code>. As a result it will later similary swap item <code>A[i]</code> which is ''before'' the array. In addition, if all items from <code>lo</code> till <code>hi-1</code> are greater than the last one, the second loop will continue decrementing <code>j</code> until it reaches value of <code>lo</code>, and in the next iteration it will compare item which is outside the array... :( --[[User:CiaPan|CiaPan]] ([[User talk:CiaPan|talk]]) 12:12, 5 August 2015 (UTC)
:: The Sytelus's code fails for example on the array [7, 5]. First <code>pivot</code> becomes 5. The first <code>do-while</code> loop increments <code>i</code> and exits, because 7 is not less than 5. The second loop decrements <code>j</code>, then finds <code>A[lo]</code> greater than <code>pivot</code>, decrements again and ...tests the item which is ''outside'' (before, strictly speaking) the range being partitioned, because {{nowrap|1=<code>i == lo-1</code>}}. <br/> Your modified version fails to increment <code>i</code> if the first (leftmost) item of the array is greater than, or equal to, <code>pivot</code>. As a result it will later similary swap item <code>A[i]</code> which is ''before'' the array. In addition, if all items from <code>lo</code> till <code>hi-1</code> are greater than the last one, the second loop will continue decrementing <code>j</code> until it reaches value of <code>lo</code>, and in the next iteration it will compare item which is outside the array... :( --[[User:CiaPan|CiaPan]] ([[User talk:CiaPan|talk]]) 12:12, 5 August 2015 (UTC)

: Fixed:
:: The code was from [https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3463 Sebastian Wild's thesis, Page 119, Listing 4]. I also confirmed that code is wrong and fails to maintain invariants. The reason I'd used this version as opposed to CLRS version was that this code required recursion on [lo..p) and (p..hi] partitions, i.e., same as Lomuto's version. The CLRS version requires recursing on [lo..p] and (p..hi] instead. But I don't see any other choice that can be used with good quality citation so I've reverted the change to use CLRS version as well as have both schemes use their own quicksort() function. I think this is good in long run because in future if new schemes are added then they are not forced to use same quicksort() function as Lomuto's. Thanks for pointing out this error. I'll also contact Sebastian Wild about the error in his thesis.

Revision as of 01:45, 7 August 2015

qsort

qsort should not redirect to this page, but rather something C-related as it is part of the standard library. Whenever qsort is used, it is always used in reference to the C-implementation which may not necessarily implement the Quicksort algorithm. To any extent; this should at least be mentioned.

Infobox animation description

Hello, CiaPan! Regarding this edit, please watch the animation – pivotal value isn't always "the rightmost value" so noting that is somewhat misleading. It is the case only in the beginning of the animation. — Dsimic (talk | contribs) 09:51, 2 March 2015 (UTC)[reply]

Animation too fast

The animation given here is way too fast. It does not really enable the reader to have a clearer understanding of the algorithm. It would be wonderful is it could be slowed down if possible. — Preceding unsigned comment added by Vinay93 (talk • contribs) 07:40, 3 May 2015 (UTC)[reply]

Pseudocode notation

Hey, Qwertyus! Sorry for reverting your edit, as I've noted in my edit summary we should simply let such complaints go by. IMHO, := is much more readable than ← and I really don't see the need for using an inferior notation. Hope you agree. — Dsimic (talk | contribs) 22:47, 5 June 2015 (UTC)[reply]

I don't see why := is superior to ←. Both are used in the literature and in actual programming languages (R uses <-), but in mathematics, := denotes a definition. I'm trying to avoid that meaning and find ← a good substitute. QVVERTYVS (hm?) 08:43, 6 June 2015 (UTC)[reply]
To me, := is simply more readable than ←, which is much easier to overlook when glancing over pseudocode, and the pseudocode is all about good readability. Also, as we know Pascal uses := as the assignment operator, which qualifies it for such use. — Dsimic (talk | contribs) 21:55, 6 June 2015 (UTC)[reply]
(ec) ...and it's not just Qwertyus' invention – see for example https://www.cs.rochester.edu/~gildea/csc282/slides/C07-quicksort.pdf page 4 or http://www.mif.vu.lt/~valdas/ALGORITMAI/LITERATURA/Cormen/Cormen.pdf page 25. --CiaPan (talk) 22:05, 6 June 2015 (UTC)[reply]
I've never called ← to be a Qwertyus' invention, I've just called := more readable. :) — Dsimic (talk | contribs) 22:19, 6 June 2015 (UTC)[reply]
Well, I didn't mean literary Qwertyus' invention. It was rather a fig. 'this is nothing new', as Qwertyus' was not the first one, some known authors (like Cormen) have used the notation before. BTW, I am quite familiar with both symbols (← and :=) and can read them with no trouble, but it's a personal point of view which notation is 'more readable' so I'm not going to advocate on either side :) --CiaPan (talk) 06:59, 24 June 2015 (UTC)[reply]
Agreed, the whole thing depends on one's point of view. — Dsimic (talk | contribs) 07:02, 24 June 2015 (UTC)[reply]

Blog interview

The new blog post that purported holds an interview with Tony Hoare isn't needed — most of the history contained in it has already been divulged by Hoare in other places. I'll try to find out where so we can get rid of the blog. QVVERTYVS (hm?)

Error in code

The code added in Sytelus's version from 3 August 2015, section Hoare partitioning scheme is not a Hoare's algorithm. It just resembles that of Hoare, at best.

Even worse, it is incorrect. --CiaPan (talk) 10:07, 5 August 2015 (UTC)[reply]

Whoops, the code has been changed by Qwertyus on 5 August 2015. Alas that one is wrong, too. They fail on different input data, anyway they both fail. --CiaPan (talk) 10:20, 5 August 2015 (UTC)[reply]

Ping: @Sytelus and Qwertyus:. --CiaPan (talk) 11:50, 5 August 2015 (UTC)[reply]

I only changed the pseudocode cosmetically, or so I thought, but you may be right. I just translated the Hoare partition function into Python and it goes into an infinite loop. It also doesn't match the Hoare partition discussed by Cormen et al. (3e, p. 185):
Hoare-Partition(A, p, r)
    x = A[p]
    i = p - 1
    j = r + 1
    while TRUE
        repeat
            j = j - 1
        until A[j] ≤ x
        repeat
            i = i + 1
        until A[i] ≥ x
        if i < j
            exchange A[i] with A[j]
        else return j
Note the additional swap in our version, and the lack of (hi+1) when initializing j. QVVERTYVS (hm?) 11:56, 5 August 2015 (UTC)[reply]
I reverted my edit since it changes the algorithm; the do-while loops execute at least once, but my while loops don't. QVVERTYVS (hm?) 11:59, 5 August 2015 (UTC)[reply]
After edit-conflict:
The Sytelus's code fails for example on the array [7, 5]. First pivot becomes 5. The first do-while loop increments i and exits, because 7 is not less than 5. The second loop decrements j, then finds A[lo] greater than pivot, decrements again and ...tests the item which is outside (before, strictly speaking) the range being partitioned, because i == lo-1.
Your modified version fails to increment i if the first (leftmost) item of the array is greater than, or equal to, pivot. As a result it will later similary swap item A[i] which is before the array. In addition, if all items from lo till hi-1 are greater than the last one, the second loop will continue decrementing j until it reaches value of lo, and in the next iteration it will compare item which is outside the array... :( --CiaPan (talk) 12:12, 5 August 2015 (UTC)[reply]
Fixed:
The code was from Sebastian Wild's thesis, Page 119, Listing 4. I also confirmed that code is wrong and fails to maintain invariants. The reason I'd used this version as opposed to CLRS version was that this code required recursion on [lo..p) and (p..hi] partitions, i.e., same as Lomuto's version. The CLRS version requires recursing on [lo..p] and (p..hi] instead. But I don't see any other choice that can be used with good quality citation so I've reverted the change to use CLRS version as well as have both schemes use their own quicksort() function. I think this is good in long run because in future if new schemes are added then they are not forced to use same quicksort() function as Lomuto's. Thanks for pointing out this error. I'll also contact Sebastian Wild about the error in his thesis.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Quicksort&oldid=674925576"