Python >> Tutoriel Python >  >> Python

Comment écrire un algorithme Quicksort en Python

Bien qu'il existe des bibliothèques disponibles pour tous les langages de programmation qui offrent la possibilité de trier des listes, des tableaux et des collections, il est important de savoir comment cela est réalisé.

Apprendre à écrire soi-même un algorithme de tri rapide permet de mieux comprendre le langage de programmation de votre choix et d'optimiser le code lorsque cela est possible.

Aujourd'hui, nous allons explorer l'écriture d'un algorithme de tri rapide dans le langage de programmation Python.

Commençons par définir une liste d'entiers qui ne sont clairement pas dans l'ordre :

unordered = [97, 200, 100, 101, 211, 107]

Ensuite, nous devons créer une fonction, que nous appellerons quicksort qui abritera notre algorithme. Nous lui donnerons notre liste non triée et il renverra une liste triée une fois terminé.

# Create a function with 3 arguments
# `list` = an unsorted list
# `start` = index where to start sorting
# `end` = index where to end sorting
def quicksort(list, start=0, end=None):
    if end is None:
        end = len(list) - 1

    # an internal recursion function to do all the work
    def _quicksort(list, start, end):
        if start >= end: return
        pivot = partition(list, start, end)
        _quicksort(list, start, pivot-1)
        _quicksort(list, pivot+1, end)
        return list
    
    # call our internal function and return
    return _quicksort(list, start, end)

Nous n'avons pas encore tout à fait terminé, nous devons encore écrire notre partition fonction qui renverra un nouveau point pivot à chaque exécution.

# Create another function with 3 arguments
# `list` = a list
# `start` = starting index
# `end` = ending index
def partition(list, start, end):
    # start by setting our pivot point at the start
    pivot = start
    for i in range(start+1, end+1):
        if list[i] <= list[start]:
            pivot += 1

            # swap loop index and pivot around
            list[i], list[pivot] = list[pivot], list[i]

    # swap pivot and start values around
    list[pivot], list[start] = list[start], list[pivot]

    # return our new pivot
    return pivot

Maintenant, rassemblons tout et essayons !

# Create a function with 3 arguments
# `list` = an unsorted list
# `start` = index where to start sorting
# `end` = index where to end sorting
def quicksort(list, start=0, end=None):
    if end is None:
        end = len(list) - 1

    # an internal recursion function to do all the work
    def _quicksort(list, start, end):
        if start >= end: return
        pivot = partition(list, start, end)
        _quicksort(list, start, pivot-1)
        _quicksort(list, pivot+1, end)
        return list
    
    # call our internal function and return
    return _quicksort(list, start, end)


# Create another function with 3 arguments
# `list` = a list
# `start` = starting index
# `end` = ending index
def partition(list, start, end):
    # start by setting our pivot point at the start
    pivot = start
    for i in range(start+1, end+1):
        if list[i] <= list[start]:
            pivot += 1

            # swap loop index and pivot around
            list[i], list[pivot] = list[pivot], list[i]

    # swap pivot and start values around
    list[pivot], list[start] = list[start], list[pivot]

    # return our new pivot
    return pivot

Qu'obtenons-nous lorsque nous l'appelons avec notre liste non triée d'avant ?

unsorted = [97, 200, 100, 101, 211, 107]

print(quicksort(unsorted))

# [97, 100, 101, 107, 200, 211]

Ah, adorable, nous avons maintenant une liste triée d'entiers complimentant notre quicksort fonction python !


Post précédent