Jump to content

Talk:Quicksort

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Abuseslang (talk | contribs) at 06:03, 10 October 2018 (→‎Elegant quicksort *Musatov: code). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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?)

Bug in Lomuto Partition

There are two 3 errors in the Lomuto Partition: 

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo     // place for swapping
    for j := lo to hi – 1 do
        if A[j] ≤ pivot then
            swap A[i] with A[j]           
            i := i + 1
    swap A[i] with A[hi]
    return i

i := lo should be i := lo -1

and 

swap A[i] with A[j]
i := i +1

should be 

i := i +1
swap A[i] with A[j]

and 

return i

should be 

return i+1

I'm going to make the edit, but I'm leaving this comment first in case the edit is controversial. Also, I'm not particularly fond of the pseudo code. I'm keeping it mostly the same since that's how I found it, and it's used elsewhere in the Article. However I am changing the ordering to look more like the example in "Introduction to Algorithms" (p.146), which I think reads better. --FuturePrefect (talk) 09:27, 27 November 2016 (UTC)[reply]

Why don't you change it? I think your comment is right, but it can be improved:
for j := lo to hi – 1 do
should be changed to:
for j := lo+1 to hi do
swap A[i] with A[j]
i := i +1
should be
i := i +1
swap A[i] with A[j]
everything else should be left unchanged then. --Walkerlala (talk) 15:54, 12 February 2017 (UTC)[reply]


@FuturePrefect: WHY dou you think these are errors? Could you, please, show an example array, which would not be correctly partitioned with the algorithm presented in the article, and how your change woild fix the incorrect partitioning? --CiaPan (talk) 18:23, 12 February 2017 (UTC)[reply]
@CiaPan: consider the corner case where there are only two sorted elements: [4, 5] -- Walkerlala (talk) 23:07, 12 February 2017 (UTC)[reply]
@FuturePrefect: I think we should return i; rather than return i+1 because i is the position where the pivot finally live, which is what `partition()' should return. -- Walkerlala (talk) 04:24, 13 February 2017 (UTC)[reply]

This is still not correct: 

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo - 1    
    for j := lo to hi - 1 do
        if A[j] ≤ pivot then
            i := i + 1
            swap A[i] with A[j]
    swap A[i] with A[hi]
    return i

Consider the case that A[lo..hi-1]=1 and A[hi]=2. By the end of the j-loop, A[lo..hi-1] will have been swapped with themselves and i will be equal to hi-1. But then the final swap puts the pivot (2) into A[hi-1] with a 1 above it. What should actually happen is that the pivot is swapped into A[i+1] and i+1 is returned. The loop invariant is that A[lo..i] ≤ pivot; this is violated by the final swap if A[i] < pivot. McKay (talk) 07:18, 13 February 2017 (UTC)[reply]

@McKay: yes you are right. I just miss that corner case.

But, then what is true implementation of Lomuto Partition? I know a seemingly correct implementation: 

algorithm partition(A, lo, hi) is
    pivot := A[lo]
    i := lo    
    for j := lo+1 to hi do
        if A[j] ≤ pivot then
            i := i + 1
            swap A[i] with A[j]
    swap A[i] with A[lo]
    return i

which can handle the corner cases [3, 4] and [1, 1, 1, 2]. But, as someone suggest(in the revision history), pivot selecting is arbitrary and historically people use the last element. So I guess, we should change the implementation to this: 

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := hi    
    for j := hi - 1 to lo do
        if A[j] > pivot then
            i := i - 1
            swap A[i] with A[j]
    swap A[i] with A[hi]
    return i

what do you think? --Walkerlala (talk) 09:33, 13 February 2017 (UTC)[reply]


All right, after consulting the literature, I think the original implementation should be: 

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo - 1    
    for j := lo to hi - 1 do
        if A[j] ≤ pivot then
            i := i + 1
            swap A[i] with A[j]
    swap A[i+1] with A[hi]
    return i + 1

-- Walkerlala (talk) —Preceding undated comment added 09:40, 13 February 2017 (UTC)[reply]

I agree with this final algorithm, which matches the reference. I think the problem began when someone marked i as "place for swapping", even though it was at that point a pointer to one before the place, and would be incremented before the swap. Then other editors back then started modifying the algorithm. StarryGrandma (talk) 22:31, 13 February 2017 (UTC)[reply]
@Walkerlala: Although I don't like this implementation, since it doesn't work when using unsigned indices, it is the version found in Introduction to Algorithms, and it is consistent with the text describing the algorithm, while the current code is not. In particular, values equal to the pivot are in the right partition, not the left partition. Also, the text implies that the current algo is a stable sort, but it is not, since the final swap will move the last-occurring instance of the pivot to the front of the right partition. Changing to the above suggested code would resolve these inconsistencies. -- Drummist180 (talk) 04:12, 25 November 2017 (UTC)[reply]
@Drummist180: The current text (oldid=810951039#Lomuto partition scheme) does not claim the algorithm stable.
And the proposed change can not 'resolve' the Quicksort's non-stability. --CiaPan (talk) 21:29, 25 November 2017 (UTC)[reply]
@CiaPan: Ah, yes. I misunderstood. Can we make the change, though? --Drummist180 (talk) 22:51, 25 November 2017 (UTC)[reply]

FWIW, I think that the current pseudocode for both algorithms could be made clearer by increasing the i values by one and adjusting accordingly. To me it seemed odd on first inspection that the very first value of i is set to minus one, only for it to be incremented before use. In the case of Hoare's, it would mean a switch from do-while to while which is also clearer IMO. I suppose this is a matter of style; it seems like people here have strong opinions and the battle has already been fought, but just wanted to add one more voice. --AndrewChinery (talk) 16:12, 14 April 2018 (UTC)[reply]

Bug in Partition

I implemented partition as presently suggested: 

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo - 1    
    for j := lo to hi - 1 do
        if A[j] < pivot then
            i := i + 1
            swap A[i] with A[j]
    if A[hi] < A[i + 1] then
        swap A[i + 1] with A[hi]
    return i + 1

In python. Here is the ugly implementation: 

 def partition_broken(arr, lo, hi):
       pivot = arr[hi]
       print "starting partition.  pivot is arr[%d]=%d" % (hi, pivot)
       i = lo - 1
       for j in range(lo, hi):
               print "i=%d, j=%d" % (i, j), arr
               if arr[j] < pivot:
                       print "arr[j] < pivot, swapping"
                       i = i + 1
                       arr[i], arr[j] = arr[j], arr[i]
       if arr[hi] < arr[i + 1]:
               print "arr[%d]=%d < arr[%d]=%d; swapping" % (hi, arr[hi], i + 1, arr[i+1])
               arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
       print arr
       return i + 1

 partition_broken([1, 2, 1, 3, 1, 4, 1], 0, 6)

Here is what happens when you run this code: 

  starting partition.  pivot is arr[6]=1
  i=-1, j=0 [1, 2, 1, 3, 1, 4, 1]
  i=-1, j=1 [1, 2, 1, 3, 1, 4, 1]
  i=-1, j=2 [1, 2, 1, 3, 1, 4, 1]
  i=-1, j=3 [1, 2, 1, 3, 1, 4, 1]
  i=-1, j=4 [1, 2, 1, 3, 1, 4, 1]
  i=-1, j=5 [1, 2, 1, 3, 1, 4, 1]
  [1, 2, 1, 3, 1, 4, 1]

The problem seems to stem from the if arr[j] < pivot: which should be if arr[j] <= pivot:. Restoring the <= seems to make the algorithm work properly: 

  starting partition.  pivot is arr[6]=1
  i=-1 j=0 [1, 2, 1, 3, 1, 4, 1]
  arr[j] <= pivot, swapping
  i=0 j=1 [1, 2, 1, 3, 1, 4, 1]
  i=0 j=2 [1, 2, 1, 3, 1, 4, 1]
  arr[j] <= pivot, swapping
  i=1 j=3 [1, 1, 2, 3, 1, 4, 1]
  i=1 j=4 [1, 1, 2, 3, 1, 4, 1]
  arr[j] <= pivot, swapping
  i=2 j=5 [1, 1, 1, 3, 2, 4, 1]
  arr[6]=1 < arr[3]=3; swapping
  [1, 1, 1, 1, 2, 4, 3]

Dbprice (talk) 19:08, 4 August 2017 (UTC)[reply]

@Dbprice: This isn't a bug. When the pivot is 1, and the first element is the same as the pivot, and all elements are >= 1, then the array is already partitioned. Testing for < or <= are both valid, but it changes the interpretation of the partition point. It is either the last element in the lower partition (if using <=), or it is the first element in the upper partition (if using <). -- Drummist180 (talk) 15:04, 24 November 2017 (UTC)[reply]

Intro paragraph

The first paragraph of the article includes this statement: "Quicksort can operate in-place on an array, requiring small additional amounts of memory to perform the sorting.", but the best case amount of stack space used is log2(n) stack frames for the recursive calls, and the worst case is (n-1) stack frames. Rcgldr (talk) 16:51, 9 December 2017 (UTC)[reply]

That's correct: the algorithm can operate in-place on an array, it does not require to copy data from an array elsewhere to put them later back to the original array (except making a copy of a single item during the swap step).
And a logarithmic size of stack data actually is small amount of additional memory. Be aware that sorting five or ten items is a matter of school excersises. In real applications one often needs to sort thousands or even hundreds thousand items – then allocating 14-level stack to handle sorting of 10,000-items' array really IS a small amount...
And the worst case of (n-1) leves of stack happens only in most primitive implementations. A simple cure for it, published by Robert Sedgewick, is described in the #Space complexity section of the article. --CiaPan (talk) 17:25, 9 December 2017 (UTC)[reply]
I can read Rcgldr's comment as the naive quicksort is not an in-place algorithm. The narrow notion of in-place is O(1) space, but the relaxed notion of in place is satisfied by O(log n) additional space for something O(n). So naive quicksort is not in place but Sedgewick variation is in place. The phrase "can operate" sort of saves it, but a better statement would be QS can be an in-place algorithm in the best case when it uses log(n) stack frames. Glrx (talk) 22:05, 20 December 2017 (UTC)[reply]
What is a 'naive quicksort'? How does it differ from the quicksort, as defined by T.Hoare? --CiaPan (talk) 23:16, 20 December 2017 (UTC)[reply]
Here, Hoare/non-Sedgewick. (Modern imps should also do fat partition.) Glrx (talk) 18:32, 21 December 2017 (UTC)[reply]

Cole-Kandathil's algorithm

The (currently) last subsection is called "generalization," but it does not explain in what sense this algorithm family generalizes quicksort (as implied by the title). AmirOnWiki (talk) 09:40, 30 March 2018 (UTC)[reply]

The section is titled "Relation to other algorithms", which seems to justify inclusion of this algorithm. I agree the subsection "generalisations" is a bit misleading. Perhaps it should be changed to "partition sorts", which seems to be the name applied by the source. Kleuske (talk) 09:45, 30 March 2018 (UTC)[reply]

Hi, I have a suggestion for a new external link.

This link contains an implementation of quick sort in 10 different programming languages. It also has a widget for running quick sort directly in the browser.

https://repo.progsbase.com/repoviewer/no.inductive.libraries/QuickSort/0.1.0/main.QuickSort/QuickSort/quickSortNumbersBounds

I think it is of value and interest to a reader of this page. — Preceding unsigned comment added by Martinfjohansen (talk • contribs) 11:35, 6 July 2018 (UTC)[reply]

Elegant quicksort *Musatov

algorithm quiksort (A, lo, hi) is 

   if lo <hi then 
       p: = partition (A, lo, hi) 
       quicksort (A, lo, p - 1 
       )

algorithm partition (A, lo, hi) is 

   pivot: = A [hi] 
   i: = lo      // place for swapping 
   for j: = lo to hi - 1 do 
       if A [j] p pivot then 
           swap A [i] with A [j]            
           i: = i + 1 
   swap A [i] with A [hi] return i

The array is arranged by summing a quicksort (A, 1, length (A)) . — Preceding unsigned comment added by Abuseslang (talk • contribs) 05:59, 10 October 2018 (UTC)[reply]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Quicksort&oldid=863346265"