À partir d'un livre que les programmeurs peuvent apprendre ... (Python): À propos du tri

Dernière fois Question pour trouver la valeur maximale ** pour une valeur donnée en tant que recherche conditionnelle (Il y a une réponse, mais (suer) est étudiée en Python Je l'ai écrit plus tard, mais cette fois *** tri *** est expliqué et le code C ++ est écrit, je pensais que c'était Python comme d'habitude, mais je ne pouvais pas le réparer moi-même, il a été posté par google En mémoire du code qui est.

Problème: tri rapide Code de réponse C ++

int compareFunc(const void * voidA, const void * voidB) {
    int * intA = (int *)(voidA);
    int * intB = (int *)(voidB);
return *intA - *intB;
}

const int ARRAY_SIZE = 10;
int intArray[ARRAY_SIZE] = {87,28,100,78,84,98,75,70,81,68};
qsort(intArray, ARRAY_SIZE, sizeof(int), compareFunc);

Il a été implémenté avec la fonction qsort.

Self (code emprunté) Python qui trie et renvoie le tableau donné par tri rapide

Site de référence → Tri rapide

test35.py

#!/usr/bin/env python
#coding:utf-8

def quicksort(seq):             
    if len(seq) < 1:             #Renvoie lui-même si la séquence seq donnée est inférieure à un
        return seq

    pivot = seq[0]               #tableau seq pour faire pivoter[0]Remplacez le th * Lorsqu'il est récursé, le tableau le plus à gauche th est affecté au pivot
    left = []                    #arrangement de gauche "Je me demande si la compréhension ici est différente" à faire pour accumuler de plus en plus
    right = []                   #tableau de droite même

    for x in range(1, len(seq)): #Répétez pour la longueur de 1 à l'exclusion de 0 dans la séquence seq
        if seq[x] <= pivot:      #Première séquence séquentielle[1]Est plus petit que pivot?
            left.append(seq[x])  #S'il est petit, stockez-le dans le tableau à droite et à gauche du tableau au centre du pivot
        else:
            right.append(seq[x]) #S'il est volumineux, stockez-le dans le tableau gauche droit du tableau au centre du pivot.

    left = quicksort(left)       ###Assigner le tableau de gauche stocké à la variable de gauche
    right = quicksort(right)     ###Comme ci-dessus
    foo = [pivot]                ###* Le problème est ici, mais pivot est un tableau appelé récursivement.[0]Puisqu'il s'agit de la deuxième valeur, est-ce une collection de celle-ci? ??
    return left + foo + right

seq = [87,28,100,78,84,98,75,70,81,68]
mx = quicksort(seq)
print(mx)

・ ・ ・(Résultat d'exécution du terminal)
>>> from test35 import quicksort
[28, 68, 70, 75, 78, 81, 84, 87, 98, 100]
>>> 

Comme c'était trop difficile à comprendre, je vérifierai l'intérieur avec une instruction d'impression dans la partie affectation pivot, changerai la partie retour *** ***, l'exécuterai et vérifierai ce qui est retourné

Retour à gauche uniquement

test35.py

#!/usr/bin/env python
#coding:utf-8

def quicksort(seq):
    if len(seq) < 1:
        return seq
    pivot = seq[0]
    print(pivot)
    left = []
    right = []
    for x in range(1, len(seq)):
        if seq[x] <= pivot:
            left.append(seq[x])
        else:
            right.append(seq[x])
    left = quicksort(left)
    right = quicksort(right)
    foo = [pivot]
    #return left + foo + right
    return left

seq = [87,28,100,78,84,98,75,70,81,68]
mx = quicksort(seq)
print(mx)

・ ・ ・(Résultat d'exécution)
>>> from test35 import quicksort
87
28
78
75
70
68
84
81
100
98
[]
>>> 
Ouais pourquoi? ?? Je suis sûr que je ne le stocke pas sur la gauche[87,28,100 ...]Etc
Je m'y attendais. La partie pivot est imprimée en premier, mais je peux la comprendre d'une manière ou d'une autre.
le pivot est de la séquence donnée[0]Puisque le deuxième élément est attribué, il sort tel quel.

J'ai pensé que c'était étrange et j'ai essayé de changer avec return foo + right, mais Résultats seulement

・ ・ ・(Résultat d'exécution)
>>> from test35 import quicksort
[87, 100]
>>> 
Oh, peut-être que la dernière séquence donnée est de retour? Qu'est-ce que le pivot? Le mystère est.

Enfin, quand j'essaye avec return foo, Résultats seulement

>>> from test35 import quicksort
[87]
>>> 
Ouais, après toute la dernière séquence donnée[0]Seul le deuxième élément est renvoyé.

Cela a été expliqué ainsi sur le site de référence.

Ceci est un exemple de mise en œuvre de l'organisation de la liste par ordre croissant. Le pivot est le premier élément de la liste, les éléments avec des valeurs inférieures sont stockés dans la liste de gauche, les éléments avec des valeurs plus élevées sont stockés dans la liste de droite, et la liste est finalement combinée autour du pivot.

J'ai compris le résultat de sortie comme indiqué dans le commentaire. Je suis désolé pour toutes les questions.