[GO] Les débutants en Python organisent des tri rapides

Ceci est un mémorandum

J'oublierai vraiment

Site de devis

Cette fois, je voudrais vous présenter les sites que j'ai visités pour les organiser plus tôt.

• Référence de l'algorithme
• Référence Trace

Les algorithmes eux-mêmes sont légèrement différents pour chacun, mais comme ils sont du même tri rapide, nous les organiserons en fonction de l'algorithme de @ muijp.

programme

[Tri rapide de @ Muijp](https://qiita.com/muijp/items/257e8b9b49d891137d56#%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3% 82% BD% E3% 83% BC% E3% 83% 88-quick-sort) a un programme de tableau aléatoire et une sortie pour le débogage qui a été conseillé par @shiracamus l'autre jour.

q_sort.py

def qSort(a):
    print(a)#Pour le débogage
    if len(a) in (0, 1):
        return a

    p = a[-1]
    l = [x for x in a[:-1] if x <= p]
    r = [x for x in a[:-1] if x >  p]

    return qSort(l) + [p] + qSort(r)
a = r.sample(range(1,11),k=9)
qSort(a)
#production_____________________
[3, 7, 1, 6, 9, 8, 2, 10, 4]
[3, 1, 2]
[1]
[3]
[7, 6, 9, 8, 10]
[7, 6, 9, 8]
[7, 6]
[]
[7]
[9]
[]
>>[1, 2, 3, 4, 6, 7, 8, 9, 10]

Ouais, le programme est trop concis pour être compris.

Démonter et réfléchir

La première chose à remarquer return qSort(l) + [p] + qSort(r) Je pense que. C'est la partie où les petits nombres (arrangement) et les grands nombres (arrangement) sont placés à droite et à gauche du "pivot (cellule d'intérêt)" qui est une caractéristique de tri rapide.

Référence de trace Si vous regardez le gif sur ce site

1. Prenez le pivot du milieu
2. Permutez le petit nombre à gauche et le grand nombre à droite dans l'ordre de l'extérieur
3. Changez la plage de balayage du minimum au pivot et amenez le pivot au centre Vous pouvez voir que cela se répète.

Cependant, dans ce programme p = a[-1] Comme, en prenant le pivot jusqu'au dernier numéro Et l = [x for x in a[:-1] if x <= p] r = [x for x in a[:-1] if x > p] Donc, je l'ai divisé en un nombre plus grand que le pivot et un nombre plus petit que le pivot, et les ai joints avec return (appelant la fonction de récurrence).

la première if len(a) in (0, 1): return a Renvoie si le nombre de caractères est égal ou inférieur à un, il est renvoyé comme valeur de retour de la fonction récursive.

Retracer

Sur la base de ce qui précède, essayez de tracer avec le nombre aléatoire ci-dessus

#production_____________________
[3, 7, 1, 6, 9, 8, 2, 10, 4]
[3, 1, 2]
[1]
[3]
[7, 6, 9, 8, 10]
[7, 6, 9, 8]
[7, 6]
[]
[7]
[9]
[]
>>[1, 2, 3, 4, 6, 7, 8, 9, 10]

Séquence [3, 7, 1, 6, 9, 8, 2, 10, 4] Pivot p = 4 Petit tableau l = {3,1,2} Grand tableau r = {7,6,9,8,10} Et démonter

Relancez la petite séquence, p=2 l={1}、r={3} Et démontage Chacun a été démonté, alors confirmez

Si vous redémarrez la grande séquence, cette fois p est le maximum à 10, donc l={7,6,9,8} 、r={} Est démonté Puis subdivisez tous les nombres Renvoyé sous forme de données combinées Il est.

à la fin

Cette fois, c'était presque rond, mais j'ai réalisé à quel point je ne le comprenais pas. C'était vraiment agréable d'avoir une telle opportunité.