Как реализовать двоякую быструю сортировку в Python

Question

Итак, я пытался воспроизвести алгоритм Quicksort с двойным шарниром в Python 2.7; основной один побежал отлично:

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) 

Далее я перешел к двойному шарниру, и это было то, что я пробовал:

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) 

На попытке несколько списков, этот код может сортировать перевернутый список, но не может обрабатывать случайный или восходящий, а затем нисходящий список: пытается сортировать [1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 2, 1] дает [1, 1, 2, 3, 4, 5, 5, 6, 3, 4, 7, 2, 6, 7, 8, 8, 9]. Есть что-то простое, что мне не хватает?

Answer 1

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) 

Определение понятия части II/III и explaintion двойного шарнирного типа могут ссылаться на What's the difference of dual pivot quick sort and quick sort?