Quicksort sans recursion

Commenter

Contenu du snippet

Bonjour,

Voici un code qu'y m'est pratique : le tri par quicksort.
Habituellement ce tri est effectué par récursivité mais, en python (comme avec un autre langage d'ailleurs) cela peut poser problème sur de grands ensembles car la pile d'appel des fonctions explose (out of memory).

J'ai donc mis "à plat" le quicksort de manière à enlever la récursivité de l'algorithme, la pile n'est donc plus directement mise à contribution.

a+
gil

Source / Exemple : 


#------------------------------------------------------------------------------
"""
   Quicksort sans recursivite

   Auteur : gnetwb
   Date   : 12/07/2006
   Licence: GNU GPL
"""
#------------------------------------------------------------------------------

def partition(array, start, end, compare):
    while start < end:
        # au debut de cette boucle, notre element permettant la partition 
        # est a la valeur 'start'
        while start < end:
            if compare(array[start], array[end]):
                (array[start], array[end]) = (array[end], array[start])
                break
            end = end - 1
        # au debut de cette boucle, notre element permettant la partition 
        # est a la valeur 'end'
        while start < end:
            if compare(array[start], array[end]):
                (array[start], array[end]) = (array[end], array[start])
                break
            start = start + 1
    return start
 
def quicksortPlat(array, compare=lambda x, y: x > y, start=None, end=None):
    """Le plus rapide des tris par echanges pour la plupart des usages."""
    if start is None: start = 0
    if end is None: end = len(array)
    
    indiceStack = [start,end]
    
    while len(indiceStack)>=2:
        end = indiceStack.pop()
        start = indiceStack.pop()
        i = partition(array, start, end-1, compare)

        # quicksort(array, compare, start, i)
        if start < i:
            indiceStack.append(start)
            indiceStack.append(i)

        # quicksort(array, compare, i+1, end)
        if end > (i+1):
            indiceStack.append(i+1)
            indiceStack.append(end)

#------------------------------------------------------------------------------
if __name__ == '__main__':
    listEssai = [1,8,9,7,1,3,5,7,91,3,57,69,71,38,7,23,9,4,3,347,9,341,6,14,89,1,31,8947]
    print listEssai
    quicksortPlat(listEssai)
    print listEssai

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.