0

So I've been trying to reproduce the dual-pivot Quicksort algorithm in Python 2.7; the basic one ran perfectly:

def quicksort_by_length(list, start, top):
    if top <= start:
        return
    p = start
    k = start+1
    h = k
    while k <= top:
        if list[k] < list[p]:
            list[k], list[h] = list[h], list[k]
            h += 1
        k += 1
    h -= 1
    list[p], list[h] = list[h], list[p]
    quicksort_by_length(list, start, h-1)
    quicksort_by_length(list, h+1, top)

Next, I moved on to dual pivot and this was what I tried:

def dual_pivot_sort(list, start, top):
    if top <= start:
        return
    p = start
    q = top
    k = p+1
    h = k
    l = q-1
    if list[p] > list[q]:
        list[p], list[q] = list[q], list[p]
    while k < top:
        if list[k] < list[p]:
            list[h], list[k] = list[k], list[h]
            h += 1
        elif list[k] > list[q]:
            list[k], list[l] = list[l], list[k]
            l -= 1
        k += 1
    h -= 1
    l += 1
    list[p], list[h] = list[h], list[p]
    list[q], list[l] = list[l], list[q]
    dual_pivot_sort(list, start, h-1)
    dual_pivot_sort(list, h+1, l-1)
    dual_pivot_sort(list, l+1, top)

On trying a couple of lists, this code can sort a reversed list but can't handle a random or ascending then descending list: trying to sort [1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 2, 1] gives [1, 1, 2, 3, 4, 5, 5, 6, 3, 4, 7, 2, 6, 7, 8, 8, 9]. Is there something simple I'm missing?

Anand S Kumar
  • 88,551
  • 18
  • 188
  • 176
Isaac Middlemiss
  • 208
  • 2
  • 4
  • 13

1 Answers1

2
def dual_pivot_sort(list, start, top):
    if top <= start:
        return
    p = start
    q = top
    k = p+1
    h = k
    l = q-1
    if list[p] > list[q]:
        list[p], list[q] = list[q], list[p]
    while k <= l: 
    # the last non-check index is l,as l+1 to top - 1 is the part III,              
    #where all elements > list[top] 
        if list[k] < list[p]:
            list[h], list[k] = list[k], list[h]
            #h is the first element of part II
            h += 1 
            #increase h by 1, for pointing to the first element of part II
            k += 1 
            #increase k by 1, because we have checked list[k]
        elif list[k] > list[q]:
        #l is the last element of part IV
            list[k], list[l] = list[l], list[k]
            #don't increase k, as we have not check list[l] yet
            l -= 1 
            #after swap, we should compare list[k] with list[p] and list[q] again
        else: k += 1
        # no swap, then the current k-th value is in part II, thus we plus 1 to k
    h -= 1#now,h is the last element of part I
    l += 1 #now, l is the first element of part III
    list[p], list[h] = list[h], list[p]
    list[q], list[l] = list[l], list[q]
    dual_pivot_sort(list, start, h-1)
    dual_pivot_sort(list, h+1, l-1)
    dual_pivot_sort(list, l+1, top)

The definition of part II/III and the explaintion of dual-pivot sort can refer to What's the difference of dual pivot quick sort and quick sort?

Community
  • 1
  • 1
Hooting
  • 1,681
  • 11
  • 20
  • That comes closer than mine, but still doesn't quite work: [23, 3454, 23, 54, 3, 6, 2, 674, 23454, 32, 5, 4] crashes it and 1-15-1 gets [1, 1, 2, 2, 3, 4, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 10, 11, 11, 7, 12, 12, 13, 13, 14, 14, 15]. Can you explain why comparing k to 1 works? I added a print k statement inside the loop and it increases; why doesn't it immediately break the loop as soon as it increments? – Isaac Middlemiss Aug 14 '15 at 10:28
  • The reason why has to increase k util l is that, list[k:l] has not checked yet, in other words, we have no idea which part(II/III/IV) do they belong to. – Hooting Aug 14 '15 at 15:32
  • i have updated my code, which can go through your given test cases – Hooting Aug 15 '15 at 04:59
  • Aaah, I see, that makes perfect sense. Thanks very much, I didn't catch on to the fact that once k got past l comparisons would be skewed. – Isaac Middlemiss Aug 15 '15 at 09:02