Tri et recherche dans Python

Imaginez que vous avez un morceau de papier dans votre main avec 1 000 noms répertoriés et que vous devez en trouver un, mais cette liste n'est pas par ordre alphabétique. Ce serait très frustrant, non? Bien qu'il fasse beaucoup de temps pour trier cette liste, cela facilite la recherche des noms. Donc, le trier des choses est notre désir naturel humain, et la recherche de listes triées est évidemment plus d'économie que la recherche de listes non ordonnées.

Dans le monde de l'ordinateur, la liste des recherches peut être très importante et même des ordinateurs rapides, les performances peuvent être affectées. Dans ce cas, un algorithme de tri et de recherche approprié serait la solution à de tels problèmes. Le tri est le processus de tri d'une liste de valeurs dans l'ordre, tandis que la recherche est le processus de recherche de la position des valeurs dans la liste.

Pour illustrer l'importance de cette question, permettez-moi de vous montrer ce que le grand informaticien américain Donald Knuth a dit:

Les fabricants d'ordinateurs dans les années 1960 ont estimé que, compte tenu de tous les clients, plus de 25% de leur temps d'exécution par ordinateur a été dépensé pour le tri. En fait, dans de nombreux cas d'installation, la tâche de tri représente plus de la moitié du temps de calcul. À partir de ces statistiques, nous pouvons conclure que (i) le tri a de nombreuses applications importantes, ou (ii) de nombreuses personnes trient quand elles ne devraient pas, ou (iii) des algorithmes de tri inefficaces ont été largement utilisés. —— "L'art de la programmation informatique" Volume 3: Trier et recherche, page 3

Dans ce tutoriel, je vais vous montrer comment implémenter l'algorithme de tri de sélection et l'algorithme de recherche linéaire.

Mais avant de commencer, si vous voulez juste trier et rechercher dans votre code Python, je vous montrerai la méthode intégrée.

Méthodes et fonctions de tri intégrées dans Python

Vous pouvez créer de nombreux algorithmes de tri à l'aide de Python. Il s'agit d'un bon exercice d'apprentissage, mais pour les applications de production, vous devez vous en tenir aux fonctions et méthodes stockées intégrées dans Python.

Python a une méthode list.sort() que vous pouvez utiliser pour trier la liste en place. L'algorithme de tri utilisé dans les coulisses de Python est appelé Timsort. Il s'agit d'un algorithme de tri hybride basé sur le tri des insert et le tri de fusion qui offre d'excellentes performances dans de nombreuses vies réelles. Voici un exemple de la façon d'utiliser ces deux fonctions et méthodes:

marks_a = [61, 74, 58, 49, 95, 88]
marks_b = [94, 85, 16, 47, 88, 59]

# [49, 58, 61, 74, 88, 95]
print(sorted(marks_a))

# None
print(marks_b.sort())

# [61, 74, 58, 49, 95, 88]
print(marks_a)

# [16, 47, 59, 85, 88, 94]
print(marks_b)

Vous pouvez remarquer certaines des situations du code ci-dessus. La fonction sorted() renvoie une nouvelle liste triée sans modifier la liste d'origine marks_a. Cependant, la liste originale reste la même. D'un autre côté, lorsque nous appelons la méthode marks_b sur sort(), il renvoie None.

Vous pouvez transmettre certains paramètres pour modifier le comportement de tri. Par exemple, transmettez une fonction au paramètre reverse, qui trie notre liste de mots par ordre alphabétique sans aucun paramètre. Dans le deuxième cas, nous utilisons sorted() pour inverser l'ordre des mots triés. reverse=True

Sélectionner l'algorithme de tri

Sélectionner le tri L'algorithme est basé sur la sélection continue de la valeur minimale ou maximale. Supposons que nous ayons une liste que nous voulons trier par ordre ascendant (petit à grand). Le plus petit élément sera au début de la liste et le plus grand élément sera à la fin de la liste.

Supposons que la liste originale ressemble à ceci:

| 7 | 5 | 3.5 | 4 | 3.1 |

La première chose que nous devons faire est de trouver la valeur

minimum dans la liste, dans ce cas . 3.1

Lorsque la valeur minimale est trouvée, échangez la valeur minimale avec le premier élément de la liste

. Autrement dit, échange avec . La liste ressemblera maintenant à ceci: 3.1 7

| 3.1 | 5 | 3.5 | 4 | 7 | Maintenant que nous déterminons la position correcte du premier élément de la liste, nous répétons les étapes ci-dessus (trouvons la valeur minimale) du deuxième élément

de la liste. Nous pouvons constater que la valeur minimale dans la liste (à partir du deuxième élément) est

. Nous allons donc maintenant échanger avec . La liste devient maintenant: 3.5 3.5 5

À ce stade, nous nous assurons que le premier élément et le deuxième élément sont dans leur position correcte. | 3.1 | 3.5 | 5 | 4 | 7 |

Maintenant, nous vérifions la valeur minimale dans le reste de la liste, c'est-à-dire en commençant par le troisième élément

. La valeur minimale dans le reste de la liste est

, avec laquelle nous échangeons maintenant

. Par conséquent, la liste devient: 5 4 5

Par conséquent, nous déterminons maintenant que les trois premiers éléments | 3.1 | 3.5 | 4 | 5 | 7 | sont dans la bonne position et que le processus se poursuit de cette manière.

Voyons comment implémenter l'algorithme de tri de sélection dans Python (basé sur Isai Damier):

Testons l'algorithme en ajoutant l'instruction suivante à la fin du script ci-dessus:

marks_a = [61, 74, 58, 49, 95, 88]
marks_b = [94, 85, 16, 47, 88, 59]

# [49, 58, 61, 74, 88, 95]
print(sorted(marks_a))

# None
print(marks_b.sort())

# [61, 74, 58, 49, 95, 88]
print(marks_a)

# [16, 47, 59, 85, 88, 94]
print(marks_b)

Dans ce cas, vous devriez obtenir la sortie suivante:

def selectionSort(aList):
    for i in range(len(aList)):
        least = i
        for k in range(i+1, len(aList)):
            if aList[k] < aList[least]:
                least = k

        swap(aList, least, i)

def swap(A, x, y):
    temp = A[x]
    A[x] = A[y]
    A[y] = temp

Algorithme de recherche linéaire

[4.6, 4.7, 5.76, 7.3, 7.6, 25.3, 32.4, 43.5, 52.3, 55.3, 86.7]

Recherche linéaire

L'algorithme est un algorithme simple dans lequel chaque élément de la liste est vérifié (à partir du premier élément) jusqu'à ce que l'élément souhaité soit trouvé ou que la fin de la liste soit atteinte.

L'algorithme de recherche linéaire est implémenté dans Python comme suit (basé sur Python School):

Testons le code. Entrez l'instruction suivante à la fin du script Python ci-dessus:

Lorsque vous entrez

my_list = [5.76,4.7,25.3,4.6,32.4,55.3,52.3,7.6,7.3,86.7,43.5]
selectionSort(my_list)
print(my_list)

, assurez-vous qu'il se situe entre les citations simples ou doubles (c'est-à-dire

). Par exemple, si vous tapez

, vous devriez obtenir la sortie suivante:

def linearSearch(item,my_list):
    found = False
    position = 0
    while position < len(my_list) and not found:
        if my_list[position] == item:
            found = True
        position = position + 1
    return found

input 'pencil' 'pencil' Et si vous entrez

comme entrée, vous obtiendrez la sortie suivante:

Oops, your item seems not to be in the bag

Conclusion

Comme nous l'avons vu, Python se prouve à nouveau en tant que langage de programmation facile à programmer le concept d'algorithmes, tout comme nous traitons ici des algorithmes de tri et de recherche.

Il convient de noter qu'il existe d'autres types d'algorithmes de tri et de recherche. Si vous souhaitez approfondir ces algorithmes à l'aide de Python, vous pouvez vous référer au manuel de programmation orienté objet Python gratuit.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!