Share
Si on vous donnait une feuille de papier avec une liste de 1 000 noms et qu'on vous demandait de trouver un nom, mais que cette liste n'était pas dans un ordre quelconque (par exemple, un ordre alphabétique), ce serait très frustrant, n'est-ce pas? Remettre cette liste en ordre, bien que cela prenne beaucoup de temps, facilite beaucoup la recherche du nom. Ainsi, avoir des choses en ordre est un désir naturel chez nous, et rechercher cette liste demanderait manifestement moins d'effort que de rechercher une liste non ordonnée..
Passons maintenant au monde de l'informatique, où les listes que l'on peut être amené à rechercher sont très importantes et où les performances peuvent être affectées, même avec des ordinateurs rapides. Dans ce cas, avoir un le tri et la recherche algorithme serait une solution à un tel problème. Tandis que tri est sur le point de mettre une liste de valeurs dans l'ordre, recherche est le processus de recherche de la position d'une valeur dans une liste.
Pour bien comprendre à quel point cette question peut être critique, laissez-moi vous montrer ce que Donald Knuth, un informaticien, mathématicien et professeur émérite américain, a mentionné dans L'art de la programmation informatique, vol.3, Tri et recherche, page 3:
Les fabricants d’ordinateurs des années 1960 estimaient que plus de 25% du temps d’utilisation de leur ordinateur était consacré au tri, l’ensemble des clients étant pris en compte. En fait, de nombreuses installations dans lesquelles la tâche de tri était responsable de plus de la moitié du temps de calcul. À partir de ces statistiques, nous pouvons conclure que soit (i) il existe de nombreuses applications importantes du tri, soit (ii) beaucoup de gens trient quand ils ne le devraient pas, ou (iii) des algorithmes de tri inefficaces ont été utilisés couramment..
Dans ce tutoriel, je décrirai spécifiquement les Tri de sélection algorithme (tri) et le Recherche linéaire algorithme (recherche).
le Tri de sélection L'algorithme est basé sur la sélection successive de minima ou de maxima. Supposons que nous ayons une liste que nous voulons trier par ordre croissant (de plus petite à plus grande). Le plus petit élément sera au début de la liste et le plus grand à la fin..
Disons que la liste originale ressemble à ceci:
| 7 | 5 | 3,5 | 4 | 3.1 |
La première chose que nous faisons est de trouver le le minimum valeur dans la liste, qui est dans notre cas 3.1.
Après avoir trouvé la valeur minimale, échanger cette valeur minimale avec le premier élément de la liste. C'est-à-dire, échange 3.1 avec 7. La liste va maintenant ressembler à ceci:
| 3.1 | 5 | 3,5 | 4 | 7 |
Maintenant que nous sommes certains que le premier élément se trouve à la bonne position dans la liste, répétons l’étape ci-dessus (recherche de la valeur minimale) à partir de la seconde élément dans la liste. Nous pouvons trouver que la valeur minimale dans la liste (à partir du deuxième élément) est 3,5. Nous échangeons donc maintenant 3,5 avec 5. La liste devient maintenant la suivante:
| 3.1 | 3,5 | 5 | 4 | 7 |
À ce stade, nous sommes certains que le premier et le deuxième élément sont dans la bonne position..
Maintenant, nous vérifions la valeur minimale dans le reste de la liste, c'est-à-dire à partir du troisième élément 5. La valeur minimale dans le reste de la liste est 4, et nous échangeons maintenant avec 5. La liste devient alors la suivante:
| 3.1 | 3,5 | 4 | 5 | 7 |
Nous sommes donc maintenant certains que le premier Trois les éléments sont dans les bonnes positions, et le processus se poursuit ainsi.
Voyons comment l’algorithme Selection Sort est implémenté en Python (basé sur Isai Damier):
def selectionSort (aList): pour i dans la plage (len (aList)): minimum = i pour k dans la plage (i + 1, len (aList)): si 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
Testons l'algorithme en ajoutant les instructions suivantes à la fin du script ci-dessus:
my_list = [5.76,4.7,25.3,4.6,32.4,55.3,52.3,7.6,7.3,86.7,43.5] selectionTrier (ma_list) imprimer ma_list
Dans ce cas, vous devriez obtenir le résultat suivant:
[4.6, 4.7, 5.76, 7.3, 7.6, 25.3, 32.4, 43.5, 52.3, 55.3, 86.7]
le Recherche linéaire algorithm est un algorithme simple, dans lequel chaque élément de la liste (à partir du premier élément) est examiné jusqu'à ce que l'élément requis 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):
def linearSearch (item, my_list): found = False position = 0 tant que position < len(my_list) and not found: if my_list[position] == item: found = True position = position + 1 return found
Testons le code. Entrez l'instruction suivante à la fin du script Python ci-dessus:
Accentsconagua
bag = ['livre', 'crayon', 'stylo', 'carnet de notes', 'taille-crayon', 'caoutchouc'] item = input ('Quel article voulez-vous vérifier dans le sac?') itemFound = linearSearch (article, sac) si itemFound: print 'Oui, l'article est dans le sac' sinon: print 'Oups, votre article ne semble pas être dans le sac'Lorsque vous entrez dans le contribution, assurez-vous qu'il est entre guillemets simples ou doubles (c'est-à-dire. 'crayon'). Si vous entrez 'crayon', Par exemple, vous devriez obtenir le résultat suivant:
Oui, l'article est dans le sac
Considérant que si vous entrez 'règle' en entrée, vous obtiendrez la sortie suivante:
Oups, votre article ne semble pas être dans le sac
Comme nous pouvons le constater, Python s’avère à nouveau être un langage de programmation qui facilite la programmation de concepts algorithmiques comme nous l’avons fait ici. tri et recherche algorithmes.
Il est important de noter qu'il existe d'autres types d'algorithmes de tri et de recherche. Si vous voulez approfondir ces algorithmes en utilisant Python, vous pouvez vous référer à cette page.
