Comment obtenir la sortie dans mon algorithme quicksort

Question

J'essaye d'implémenter la récursion et la compréhension de liste dans mon algorithme de quicksort. Mais je ne peux pas voir de sortie. Puis-je obtenir de l'aide, quelles lignes dois-je ajouter pour voir la sortie. Ma logique semble être correcte, et la rétroaction est appréciée.

def partition_list(A): 
    n = len(A) 
    m = A[n - 1] 
    #print m 
    A_left = [x for x in A if x <= m] 
    A_right = [x for x in A if x > m] 
    #if len(A_left) >= 2: 
    # return partition_list(A_left) 

    Anew = A_left + A_right 
    ind = Anew.index(m) 
    return Anew,ind 

Cette fonction partition_list est appelée dans la fonction suivante.

def quick_sort_helper(A): 
    if len(A) > 1: 
     Anew,m1 = partition_list(A) 
     print Anew 
     Aleft = Anew[0:m1] 
     Aright = Anew[m1 + 1:len(A)] 
     quick_sort_helper(Aleft) 
     print Aleft 
     quick_sort_helper(Aright) 
    else: 
     return A 

Answer 1

Quicksort trie en place. Cela signifie que vous devez vous assurer que lorsque votre routine de partitionnement trouve la position finale du pivot de votre choix, vous modifiez (si nécessaire) la liste en place. La routine de partitionnement est essentielle pour le tri rapide. Je vois que vous utilisez la construction Python comme liste des compositions, mais en faisant cela, vous semblez oublier comment fonctionne quicksort. C'est bon pour les débutants pour exiger plus d'espace, mais vous devriez vraiment écrire la routine de partition qui partitionne la liste donnée en place.

Votre fonction récursive quick_sort_helper() prête également à confusion. Dans le cas non récursif, il renvoie un tableau, alors que dans le cas récursif, il ne renvoie rien. Python, étant (le soi-disant) lâchement tapé langue, ne vous empêche pas de le faire.

J'ai essayé de corriger ces lacunes dans votre code tout en gardant vos choix en grande partie intacts et cela semble fonctionner. Cela ne fonctionne pas quand la liste contient des éléments en double et cela reste un exercice :-).

#!/usr/bin/env python 


def partition_list(A, loIn, hiEx): 
    """ 
    Partitions the given list between given indexes such that the pivot is in its final sorted location. 
    Note: uses additional space. 
    :param A: the list of integers 
    :param loIn: low index, inclusive 
    :param hiEx: high index, exclusive 
    :return: index pi of pivot = (A[hiEx- 1]) in the sorted sequence, thus after the function returns, A[pi] = pivot and loIn <= pi < hiEx 
    """ 
    # print "partition call: loIn = %d, hiEx = %d" % (loIn, hiEx) 
    n = hiEx - loIn 
    pivot = A[hiEx - 1] # pivot is fixed, last element of the given array 
    # print "pivot: %d" % pivot 
    slice = A[loIn:hiEx] 
    A_left = [x for x in slice if x <= pivot] 
    A_right = [x for x in slice if x > pivot] 
    Anew = A_left + A_right 
    # print Anew 
    # copy it back, defeating the purpose of quicksort 
    for i in xrange(n): 
     A[loIn + i] = Anew[i] 
    index = A.index(pivot, loIn, hiEx) 
    # print "partition index: %d, element: %d" % (index, A[index]) 
    return index 


def quick_sort_helper(A, loIn, hiEx): 
    """ 
    Implements quicksort recursively. Call this as: quick_sort_helper(a, 0, len(a)) 
    :param A: the list to sort 
    :param loIn: low index, inclusive 
    :param hiEx: high index, exclusive 
    :return: nothing, sorts list in place. 
    """ 
    if hiEx - loIn > 1: 
     m1 = partition_list(A, loIn, hiEx) # A[m1] is in its final sorted position 
     quick_sort_helper(A, loIn, m1) 
     quick_sort_helper(A, m1 + 1, hiEx) 

a = [43, 2, 52, 23, 1, 0, 10, 7, 3] 
quick_sort_helper(a, 0, len(a)) 
print "sorted: ", a # prints: sorted: [0, 1, 2, 3, 7, 10, 23, 43, 52]