QUICKSORT SANS RECURSION

#------------------------------------------------------------------------------
"""
   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