Quicksort avec Python

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

Utilisation:

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

def partition(array, begin, end):
    pivot = begin
    for i in xrange(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)

Si je recherche "python implémentation rapide" dans Google, cette question est le premier résultat de la pop. Je comprends que la question initiale était "d'aider à corriger le code" mais il y a déjà beaucoup de réponses qui font fi de la demande: actuellement deuxième plus voté un, la terrible one-liner avec l'hilarant "Vous êtes viré" commentaire et, en général, de nombreuses implémentations qui ne sont pas en place (c'est à dire l'utilisation de la mémoire supplémentaire proportionnel à l'entrée de la taille de la liste). Cette réponse fournit une solution mais c'est pour python 2.x. Alors, ci-dessous suit mon interprétation de la solution de Rosetta Code qui fonctionnent très bien pour python 3 trop:

import random

def qsort(l, fst, lst):
    if fst >= lst: return

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

    while i <= j:
        while l[i] < pivot: i += 1
        while l[j] > pivot: j -= 1
        if i <= j:
            l[i], l[j] = l[j], l[i]
            i, j = i + 1, j - 1
    qsort(l, fst, j)
    qsort(l, i, lst)

Et si vous êtes prêt à renoncer à la propriété, ci-dessous est encore une autre version qui illustre le mieux les idées de base derrière quicksort. En dehors de lisibilité, son autre avantage est qu'il est stable (égal éléments apparaissent dans la liste triée dans le même ordre qu'ils ont dans la liste non triée). Cette stabilité de la propriété ne tient pas avec le moins de mémoire-faim en place la mise en œuvre décrite ci-dessus.

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

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

Quicksort avec Python

Dans la vraie vie, il faut toujours utiliser la builtin sorte fournis par Python. Cependant, la compréhension de la quicksort algorithme est instructif.

Mon but ici est de décomposer le sujet tel qu'il est facilement compréhensible et reproductible par le lecteur sans avoir à revenir à des matériaux de référence.

L'algorithme quicksort est essentiellement le suivant:

1. Sélectionnez un pivot point de données.
2. Déplacer tous les points de données de moins de (ci-dessous) le pivot d'une position en dessous du pivot - déplacer de plus de ou égal à (ci-dessus), le pivot d'une position au-dessus d'elle.
3. Appliquer l'algorithme pour les zones au-dessus et au-dessous du pivot

Si les données sont distribuées de façon aléatoire, en sélectionnant le premier point de données comme le pivot est équivalent à une sélection aléatoire.

Lisible exemple:

Tout d'abord, regardons lisible exemple qui utilise les commentaires et les noms de variables à point pour 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

À reformuler l'algorithme et le code démontré ici - on déplacer les valeurs au-dessus du pivot vers la droite, et les valeurs en dessous du pivot vers la gauche, puis de transmettre ces partitions à la même fonction pour être triés.

Ont joué au golf:

Cela peut être ont joué au golf à 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 rendre, prendre d'abord notre lisible par exemple, supprimer des commentaires et des docstrings, et de trouver 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

Maintenant trouver ci-dessous et au-dessus, au-lieu:

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'avant de l'élément si la valeur est false, sinon si c'est vrai, il évalue et retourne 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]]))

Depuis lambdas retourner une seule epression, et nous avons simplifié à une seule expression (même si elle est de plus en plus illisible) nous pouvons maintenant utiliser une 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 à réduire notre exemple, raccourcir la fonction et les noms de variable à une lettre, et d'éliminer 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]])

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

En place Quicksort, à l'aide de la Hoare schéma de Partitionnement

L'état de la mise en œuvre crée un grand nombre de supplémentaires inutiles listes. Si nous pouvons faire cela en place, nous allons éviter de perdre de l'espace.

Ci-dessous la mise en œuvre utilise le Hoare schéma de partitionnement, que vous pouvez en savoir plus sur wikipédia (mais nous avons apparemment enlevé jusqu'à 4 redondant de calculs par partition() appel à l'aide, tandis que la boucle de la sémantique au lieu de faire-tout et en déplaçant le rétrécissement étapes à la fin de la face externe de la boucle while.).

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

Ne sais pas si je l'ai testé en profondeur:

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 souvent enseigné dans les cours d'informatique et demandé sur des entrevues d'emploi. Il nous aide à réfléchir sur la récursivité et de diviser et conquérir.

Quicksort n'est pas très pratique en Python depuis notre builtin timsort algorithme est très efficace, et nous avons la récursivité des limites. Nous nous attendons à trier la liste en place avec liste.trier ou en créer de nouvelles listes triées avec triés - qui ont tous deux prendre une key et reverse argument.

de programmation fonctionnelle, l'approche

smaller = lambda xs, y: filter(lambda x: x <= y, xs)
larger = lambda xs, y: filter(lambda x: x > y, xs)
qsort = lambda xs: qsort(smaller(xs[1:],xs[0])) + [xs[0]] + qsort(larger(xs[1:],xs[0])) if xs != [] else []

print qsort([3,1,4,2,5]) == [1,2,3,4,5]

Partition - division d'un tableau par un pivot que les plus petits éléments se déplacer vers la gauche et une plus grande elemets déplacer vers la droite ou vice versa. Un pivot peut être un élément aléatoire à partir d'un tableau. Pour faire de cet algorithme, nous avons besoin de savoir ce qui est de début et de fin de l'index d'un tableau et où est un point de pivot. Placez ensuite deux auxiliaires pointeurs L, R.

Nous avons donc un tableau de l'utilisateur[...,commencer,...,fin,...]

La position de départ de L et les R de pointeurs

[...,commencer,ensuite,...,fin,...]

     N       L

alors que L < fin

  1. Si un utilisateur[pivot] > utilisateur[L], puis déplacez R par un et swap de l'utilisateur[R] avec l'utilisateur[L]

  2. déplacer L par un

Après tout swap de l'utilisateur[R] avec l'utilisateur[pivot]

tri Rapide - Utiliser la partition de l'algorithme jusqu'à ce que chaque partie suivante de la division par un pivot devra commencer indice supérieur ou égal que la fin de l'index.

def qsort(user, begin, end):
if begin >= end:
return
# partition
# pivot = begin
L = begin+1
R = begin
while L < end:
if user[begin] > user[L]:
R+=1
user[R], user[L] = user[L], user[R]
L+= 1
user[R], user[begin] = user[begin], user[R]
qsort(user, 0, R)
qsort(user, R+1, end)
tests = [
{'sample':[1],'answer':[1]},
{'sample':[3,9],'answer':[3,9]},
{'sample':[1,8,1],'answer':[1,1,8]},
{'sample':[7,5,5,1],'answer':[1,5,5,7]},
{'sample':[4,10,5,9,3],'answer':[3,4,5,9,10]},
{'sample':[6,6,3,8,7,7],'answer':[3,6,6,7,7,8]},
{'sample':[3,6,7,2,4,5,4],'answer':[2,3,4,4,5,6,7]},
{'sample':[1,5,6,1,9,0,7,4],'answer':[0,1,1,4,5,6,7,9]},
{'sample':[0,9,5,2,2,5,8,3,8],'answer':[0,2,2,3,5,5,8,8,9]},
{'sample':[2,5,3,3,2,0,9,0,0,7],'answer':[0,0,0,2,2,3,3,5,7,9]}
]
for test in tests:
sample = test['sample'][:]
answer = test['answer']
qsort(sample,0,len(sample))
print(sample == answer)

Ceci est une version de la quicksort à l'aide de Hoare schéma de partition et avec moins de swaps et des variables locales

def quicksort(array):
qsort(array, 0, len(array)-1)
def qsort(A, lo, hi):
if lo < hi:
p = partition(A, lo, hi)
qsort(A, lo, p)
qsort(A, p + 1, hi)
def partition(A, lo, hi):
pivot = A[lo]
i, j = lo-1, hi+1
while True:
i += 1
j -= 1
while(A[i] < pivot): i+= 1
while(A[j] > pivot ): j-= 1
if i >= j: 
return j
A[i], A[j] = A[j], A[i]
test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
print quicksort(test)

Ou si vous préférez un one-liner qui illustre aussi le Python équivalent de C/C++ varags, les expressions lambda, et si les expressions:

qsort = lambda x=None, *xs: [] if x is None else qsort(*[a for a in xs if a<x]) + [x] + qsort(*[a for a in xs if a>=x])

def Partition(A,p,q):
i=p
x=A[i]
for j in range(p+1,q+1):
if A[j]<=x:
i=i+1
tmp=A[j]
A[j]=A[i]
A[i]=tmp
l=A[p]
A[p]=A[i]
A[i]=l
return i
def quickSort(A,p,q):
if p<q:
r=Partition(A,p,q)
quickSort(A,p,r-1)
quickSort(A,r+1,q)
return A

L'algorithme a 4 étapes simples:

1. Diviser le tableau en 3 parties différentes: à gauche, le pivot et le droit, lorsque le pivot n'aura qu'un seul élément. Laissez-nous choisir ce pivot élément comme le premier élément du tableau
2. Ajouter des éléments à la partie en les comparant à pivot élément. (explication dans les commentaires)
3. Recurse cet algorithme jusqu'à ce que tous les éléments du tableau ont été triés
4. Enfin, rejoignez gauche+pivot+droit de pièces

Code pour l'algorithme en python:

def my_sort(A):
p=A[0]                                       #determine pivot element. 
left=[]                                      #create left array
right=[]                                     #create right array
for i in range(1,len(A)):
#if cur elem is less than pivot, add elem in left array
if A[i]< p:
left.append(A[i])         
#the recurssion will occur only if the left array is atleast half the size of original array
if len(left)>1 and len(left)>=len(A)//2:          
left=my_sort(left)                            #recursive call
elif A[i]>p: 
right.append(A[i])                                #if elem is greater than pivot, append it to right array
if len(right)>1 and len(right)>=len(A)//2:        # recurssion will occur only if length of right array is atleast the size of original array
right=my_sort(right)
A=left+[p]+right                                        #append all three part of the array into one and return it
return A
my_sort([12,4,5,6,7,3,1,15])

Continuer avec cet algorithme récursivement avec les parties gauche et droite.

Pour La Version Python 3.x: une fonctionnelle de style à l'aide de operator module, principalement pour améliorer la lisibilité.

from operator import ge as greater, lt as lesser
def qsort(L): 
if len(L) <= 1: return L
pivot   = L[0]
sublist = lambda op: [*filter(lambda num: op(num, pivot), L[1:])]
return qsort(sublist(lesser))+ [pivot] + qsort(sublist(greater))

et est testé comme

print (qsort([3,1,4,2,5]) == [1,2,3,4,5])

L'algorithme contient deux limites, l'une ayant des éléments de moins que le pivot (suivis par l'indice "j") et l'autre ayant des éléments plus grand que le pivot (suivis par l'indice "i").

À chaque itération, un nouvel élément est traité par incrémentation j.

Invariant:-

1. tous les éléments entre pivot et j'ai moins de pivot, et
2. tous les éléments entre i et j sont plus grands que le pivot.

Si l'invariant est violé, ith et jth éléments sont inversés, et je
est incrémenté.

Après tous les éléments ont été traitées, et tout ce qui est après le pivot
a été partitionné, le pivot de l'élément est échangé avec le dernier élément
plus petit que lui.

Le pivot de l'élément va maintenant être à sa place dans la séquence. L'
les éléments avant de il sera de moins que lui et les uns après il sera
plus grand qu'elle, et ils seront triés.

def quicksort(sequence, low, high):
if low < high:    
pivot = partition(sequence, low, high)
quicksort(sequence, low, pivot - 1)
quicksort(sequence, pivot + 1, high)
def partition(sequence, low, high):
pivot = sequence[low]
i = low + 1
for j in range(low + 1, high + 1):
if sequence[j] < pivot:
sequence[j], sequence[i] = sequence[i], sequence[j]
i += 1
sequence[i-1], sequence[low] = sequence[low], sequence[i-1]
return i - 1
def main(sequence):
quicksort(sequence, 0, len(sequence) - 1)
return sequence
if __name__ == '__main__':
sequence = [-2, 0, 32, 1, 56, 99, -4]
print(main(sequence))

De la sélection d'un pivot

Un "bon" pivot sera résultat en deux sous-séquences d'à peu près la même
taille. De façon déterministe, un pivot de l'élément peut être sélectionné dans une
naïf manière ou par le calcul de la médiane de la séquence.

Une implémentation naïve de la sélection d'un pivot sera le premier ou le dernier
de l'élément. Le pire cas d'exécution dans ce cas lorsque l'entrée
la séquence est déjà trié ou l'inverse triés, comme l'un des sous-séquences
sera vide qui va causer un seul élément à être enlevé par
appel récursif.

Parfaitement équilibré split est atteint lorsque le pivot est la médiane
élément de la séquence. Il y a un nombre égal d'éléments plus
que et moins que cela. Cette approche garantit une amélioration d'ensemble de l'
temps d'exécution, mais est beaucoup plus de temps.

Un non-déterministe ou aléatoire façon de sélectionner le pivot serait de choisir
un élément uniformément au hasard. C'est un simple et léger
approche qui permettra de réduire au minimum le scénario du pire et aussi conduire à une
à peu près équilibrées split. Cela permettra également de fournir un équilibre entre l'approche naïve et la médiane à l'approche de la sélection du pivot.

def quick_sort(l):
if len(l) == 0:
return l
pivot = l[0]
pivots = [x for x in l if x == pivot]
smaller = quick_sort([x for x in l if x < pivot])
larger = quick_sort([x for x in l if x > pivot])
return smaller + pivots + larger

def is_sorted(arr): #check if array is sorted
for i in range(len(arr) - 2):
if arr[i] > arr[i + 1]:
return False
return True
def qsort_in_place(arr, left, right): #arr - given array, #left - first element index, #right - last element index
if right - left < 1: #if we have empty or one element array - nothing to do
return
else:
left_point = left #set left pointer that points on element that is candidate to swap with element under right pointer or pivot element
right_point = right - 1 #set right pointer that is candidate to swap with element under left pointer
while left_point <= right_point: #while we have not checked all elements in the given array
swap_left = arr[left_point] >= arr[right] #True if we have to move that element after pivot
swap_right = arr[right_point] < arr[right] #True if we have to move that element before pivot
if swap_left and swap_right: #if both True we can swap elements under left and right pointers
arr[right_point], arr[left_point] = arr[left_point], arr[right_point]
left_point += 1
right_point -= 1
else: #if only one True we don`t have place for to swap it
if not swap_left: #if we dont need to swap it we move to next element
left_point += 1
if not swap_right: #if we dont need to swap it we move to prev element
right_point -= 1
arr[left_point], arr[right] = arr[right], arr[left_point] #swap left element with pivot
qsort_in_place(arr, left, left_point - 1) #execute qsort for left part of array (elements less than pivot)
qsort_in_place(arr, left_point + 1, right) #execute qsort for right part of array (elements most than pivot)
def main():
import random
arr = random.sample(range(1, 4000), 10) #generate random array
print(arr)
print(is_sorted(arr))
qsort_in_place(arr, 0, len(arr) - 1)
print(arr)
print(is_sorted(arr))
if __name__ == "__main__":
main()

Cet algorithme n'utilise pas de fonctions récursives.

Laisser N être une liste de nombres avec len(N) > 0. Ensemble K = [N] et exécuter le programme suivant.

Note: Ceci est un stable algorithme de tri.

def BinaryRip2Singletons(K, S):
K_L = []
K_P = [ [K[0][0]] ] 
K_R = []
for i in range(1, len(K[0])):
if   K[0][i] < K[0][0]:
K_L.append(K[0][i])
elif K[0][i] > K[0][0]:
K_R.append(K[0][i])
else:
K_P.append( [K[0][i]] )
K_new = [K_L]*bool(len(K_L)) + K_P + [K_R]*bool(len(K_R)) + K[1:]
while len(K_new) > 0:
if len(K_new[0]) == 1:
S.append(K_new[0][0])
K_new = K_new[1:]
else: 
break
return K_new, S
N = [16, 19, 11, 15, 16, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1]
K = [ N ]
S = []
print('K =', K, 'S =', S)
while len(K) > 0:
K, S = BinaryRip2Singletons(K, S)
print('K =', K, 'S =', S)

PROGRAMME DE LA SORTIE:

K = [[16, 19, 11, 15, 16, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1]] S = []
K = [[11, 15, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1], [16], [16], [19]] S = []
K = [[10, 4, 10, 5, 2, 3, 4, 7, 1], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[4, 5, 2, 3, 4, 7, 1], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[2, 3, 1], [4], [4], [5, 7], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[5, 7], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = [1, 2, 3, 4, 4]
K = [[15, 12, 14], [16], [16], [19]] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11]
K = [[12, 14], [15], [16], [16], [19]] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11]
K = [] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11, 12, 14, 15, 16, 16, 19]

def quick_sort(list):
if len(list) ==0:
return []
return  quick_sort(filter( lambda item: item < list[0],list)) + [v for v in list if v==list[0] ]  +  quick_sort( filter( lambda item: item > list[0], list))

inlace sorte

def qsort(a, b=0, e=None):
# partitioning
def part(a, start, end):
p = start
for i in xrange(start+1, end):
if a[i] < a[p]:
a[i], a[p+1] = a[p+1], a[i]
a[p+1], a[p] = a[p], a[p+1]
p += 1
return p
if e is None:
e = len(a)
if e-b <= 1: return
p = part(a, b, e)
qsort(a, b, p)
qsort(a, p+1, e)

sans récursivité:

deq = collections.deque()
deq.append((b, e))
while len(deq):
el = deq.pop()
if el[1] - el[0] > 1:
p = part(a, el[0], el[1])
deq.append((el[0], p))
deq.append((p+1, el[1]))

Je vais faire quicksort utilisation de numpy bibliothèque. Je pense qu'il est vraiment utile de la bibliothèque. Ils ont déjà mis en place le tri rapide méthode, mais vous pouvez implment aussi votre méthode personnalisée.

import numpy
array = [3,4,8,1,2,13,28,11,99,76] #The array what we want to sort
indexes = numpy.argsort( array , None, 'quicksort', None)
index_list = list(indexes)
temp_array = []
for index in index_list:
temp_array.append( array[index])
array = temp_array
print array #it will show sorted array