Quicksort avec Python

Question

Je suis totalement novice en python et j'essaie d'y implémenter quicksort. Quelqu'un pourrait-il m'aider à compléter mon code ?

Je ne sais pas comment concaténer les trois tableaux et les imprimer.

def sort(array=[12,4,5,6,7,3,1,15]):
    less = []
    equal = []
    greater = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)
            sort(less)
            sort(pivot)
            sort(greater)

Answer 1

def sort(array=[12,4,5,6,7,3,1,15]):
    """Sort the array by using quicksort."""

    less = []
    equal = []
    greater = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            elif x == pivot:
                equal.append(x)
            elif x > pivot:
                greater.append(x)
        # Don't forget to return something!
        return sort(less)+equal+sort(greater)  # Just use the + operator to join lists
    # Note that you want equal ^^^^^ not pivot
    else:  # You need to handle the part at the end of the recursion - when you only have one element in your array, just return the array.
        return array

Answer 2

Tri rapide sans mémoire supplémentaire (en place)

Utilisation :

array = [97, 200, 100, 101, 211, 107]
quicksort(array)
print(array)
# array -> [97, 100, 101, 107, 200, 211]

def partition(array, begin, end):
    pivot = begin
    for i in range(begin+1, end+1):
        if array[i] <= array[begin]:
            pivot += 1
            array[i], array[pivot] = array[pivot], array[i]
    array[pivot], array[begin] = array[begin], array[pivot]
    return pivot

def quicksort(array, begin=0, end=None):
    if end is None:
        end = len(array) - 1
    def _quicksort(array, begin, end):
        if begin >= end:
            return
        pivot = partition(array, begin, end)
        _quicksort(array, begin, pivot-1)
        _quicksort(array, pivot+1, end)
    return _quicksort(array, begin, end)

Answer 3

Il existe une autre version concise et belle

def qsort(arr):
    if len(arr) <= 1:
        return arr
    else:
        return qsort([x for x in arr[1:] if x < arr[0]])
        + [arr[0]]
        + qsort([x for x in arr[1:] if x >= arr[0]])

Laissez-moi expliquer les codes ci-dessus pour plus de détails

1. choisir le premier élément du tableau arr[0] comme pivot

   [arr[0]]

2. qsort les éléments du tableau qui sont inférieurs au pivot avec List Comprehension

   qsort([x for x in arr[1:] if x < arr[0]])

3. qsort les éléments du tableau qui sont plus grands que le pivot avec List Comprehension

   qsort([x for x in arr[1:] if x >= arr[0]])

Answer 4

Cette réponse est un QuickSort in-place pour Python 2.x . Ma réponse est une interprétation de la solution in-place de Code Rosetta qui fonctionne pour Python 3 aussi :

import random

def qsort(xs, fst, lst):
    '''
    Sort the range xs[fst, lst] in-place with vanilla QuickSort

    :param xs:  the list of numbers to sort
    :param fst: the first index from xs to begin sorting from,
                must be in the range [0, len(xs))
    :param lst: the last index from xs to stop sorting at
                must be in the range [fst, len(xs))
    :return:    nothing, the side effect is that xs[fst, lst] is sorted
    '''
    if fst >= lst:
        return

    i, j = fst, lst
    pivot = xs[random.randint(fst, lst)]

    while i <= j:
        while xs[i] < pivot:
            i += 1
        while xs[j] > pivot:
            j -= 1

        if i <= j:
            xs[i], xs[j] = xs[j], xs[i]
            i, j = i + 1, j - 1
    qsort(xs, fst, j)
    qsort(xs, i, lst)

Et si vous êtes prêt à renoncer à la propriété "in-place", vous trouverez ci-dessous une autre version qui illustre mieux les idées de base de Quicksort. Outre la lisibilité, son autre avantage est qu'elle est stable (les éléments égaux apparaissent dans la liste triée dans le même ordre qu'ils avaient dans la liste non triée). Cette propriété de stabilité ne se vérifie pas avec l'implémentation in-place moins gourmande en mémoire présentée ci-dessus.

def qsort(xs):
    if not xs: return xs # empty sequence case
    pivot = xs[random.choice(range(0, len(xs)))]

    head = qsort([x for x in xs if x < pivot])
    tail = qsort([x for x in xs if x > pivot])
    return head + [x for x in xs if x == pivot] + tail

Answer 5

Quicksort avec Python

Dans la vie réelle, nous devrions toujours utiliser le tri intégré fourni par Python. Cependant, la compréhension du quicksort est instructif.

Mon objectif ici est de décomposer le sujet de manière à ce qu'il soit facilement compréhensible et reproductible par le lecteur sans avoir à revenir à des documents de référence.

L'algorithme de quicksort est essentiellement le suivant :

1. Sélectionnez un point de données pivot.
2. Déplacez tous les points de données inférieurs (au-dessous) du pivot vers une position inférieure au pivot - déplacez ceux qui sont supérieurs ou égaux (au-dessus) au pivot vers une position supérieure à celui-ci.
3. Appliquer l'algorithme aux zones situées au-dessus et en dessous du pivot

Si les données sont distribuées de manière aléatoire, la sélection du premier point de données comme pivot est équivalente à une sélection aléatoire.

Exemple lisible :

Tout d'abord, examinons un exemple lisible qui utilise des commentaires et des noms de variables pour indiquer des valeurs intermédiaires :

def quicksort(xs):
    """Given indexable and slicable iterable, return a sorted list"""
    if xs: # if given list (or tuple) with one ordered item or more: 
        pivot = xs[0]
        # below will be less than:
        below = [i for i in xs[1:] if i < pivot] 
        # above will be greater than or equal to:
        above = [i for i in xs[1:] if i >= pivot]
        return quicksort(below) + [pivot] + quicksort(above)
    else: 
        return xs # empty list

Pour reformuler l'algorithme et le code présentés ici, nous déplaçons les valeurs au-dessus du pivot vers la droite, et les valeurs en dessous du pivot vers la gauche, puis nous transmettons ces partitions à la même fonction pour un tri supplémentaire.

Golfé :

Ce dernier peut être golfé jusqu'à 88 caractères :

q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])

Pour voir comment nous y arrivons, prenons d'abord notre exemple lisible, supprimons les commentaires et les docstrings, et trouvons le pivot sur place :

def quicksort(xs):
    if xs: 
        below = [i for i in xs[1:] if i < xs[0]] 
        above = [i for i in xs[1:] if i >= xs[0]]
        return quicksort(below) + [xs[0]] + quicksort(above)
    else: 
        return xs

Trouvez maintenant le dessous et le dessus, en place :

def quicksort(xs):
    if xs: 
        return (quicksort([i for i in xs[1:] if i < xs[0]] )
                + [xs[0]] 
                + quicksort([i for i in xs[1:] if i >= xs[0]]))
    else: 
        return xs

Maintenant, sachant que and renvoie l'élément précédent s'il est faux, sinon s'il est vrai, il évalue et renvoie l'élément suivant, nous avons :

def quicksort(xs):
    return xs and (quicksort([i for i in xs[1:] if i < xs[0]] )
                   + [xs[0]] 
                   + quicksort([i for i in xs[1:] if i >= xs[0]]))

Puisque les lambdas renvoient une seule expression, et que nous avons simplifié à une seule expression (même si cela devient de plus en plus illisible) nous pouvons maintenant utiliser un lambda :

quicksort = lambda xs: (quicksort([i for i in xs[1:] if i < xs[0]] )
                        + [xs[0]] 
                        + quicksort([i for i in xs[1:] if i >= xs[0]]))

Et pour revenir à notre exemple, raccourcissez les noms de fonctions et de variables à une lettre, et éliminez les espaces qui ne sont pas nécessaires.

q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])

Notez que cette lambda, comme la plupart des golfs de code, est plutôt de mauvais style.

Tri rapide sur place, utilisant le schéma de partitionnement de Hoare.

L'implémentation précédente crée beaucoup de listes supplémentaires inutiles. Si nous pouvons faire cela en place, nous éviterons de gaspiller de l'espace.

L'implémentation ci-dessous utilise le schéma de partitionnement de Hoare, que vous pouvez utiliser dans le cadre de votre projet. Pour en savoir plus, consultez wikipedia (mais nous avons apparemment supprimé jusqu'à 4 calculs redondants par partition() en utilisant la sémantique de la boucle while au lieu de do-while et en déplaçant les étapes de rétrécissement à la fin de la boucle while externe).

def quicksort(a_list):
    """Hoare partition scheme, see https://en.wikipedia.org/wiki/Quicksort"""
    def _quicksort(a_list, low, high):
        # must run partition on sections with 2 elements or more
        if low < high: 
            p = partition(a_list, low, high)
            _quicksort(a_list, low, p)
            _quicksort(a_list, p+1, high)
    def partition(a_list, low, high):
        pivot = a_list[low]
        while True:
            while a_list[low] < pivot:
                low += 1
            while a_list[high] > pivot:
                high -= 1
            if low >= high:
                return high
            a_list[low], a_list[high] = a_list[high], a_list[low]
            low += 1
            high -= 1
    _quicksort(a_list, 0, len(a_list)-1)
    return a_list

Je ne suis pas sûr de l'avoir testé assez minutieusement :

def main():
    assert quicksort([1]) == [1]
    assert quicksort([1,2]) == [1,2]
    assert quicksort([1,2,3]) == [1,2,3]
    assert quicksort([1,2,3,4]) == [1,2,3,4]
    assert quicksort([2,1,3,4]) == [1,2,3,4]
    assert quicksort([1,3,2,4]) == [1,2,3,4]
    assert quicksort([1,2,4,3]) == [1,2,3,4]
    assert quicksort([2,1,1,1]) == [1,1,1,2]
    assert quicksort([1,2,1,1]) == [1,1,1,2]
    assert quicksort([1,1,2,1]) == [1,1,1,2]
    assert quicksort([1,1,1,2]) == [1,1,1,2]

Conclusion

Cet algorithme est fréquemment enseigné dans les cours d'informatique et demandé lors des entretiens d'embauche. Il nous aide à réfléchir à la récursion et à la méthode "diviser pour régner".

La fonction Quicksort n'est pas très pratique en Python, car notre module intégré timsort L'algorithme est assez efficace, et nous avons des limites de récursion. Nous nous attendrions à trier les listes in-place avec list.sort ou créer de nouvelles listes triées avec sorted - qui prennent tous deux un key y reverse argument.