Python les bases en plus de 128 mots [Partie 2]

Cet article fait suite à la première partie qu’il est possible de consulter ici : https://128mots.com/index.php/2019/12/04/python-les-bases-capes-nsi-snt-en-plus-de-128-mots/

Comme pour le premier article, je traite ici des bases du langage Python pour l’apprendre rapidement. En France ces bases sont enseignées en lycée aux classes de seconde SNT, première et terminale NSI. Elles font également partie du programme de connaissance pour le CAPES NSI.

Priorité des opérateurs :

Je récapitule la priorité des opérateurs en Python, de la priorité la plus haute à la priorité la plus basse

  • Parenthèses () : groupement d’opérations
  • Exposant : x ** y
  • Multiplication, multiplication de matrice, division, division entière, modulo : *, @, /, //, %
  • Addition, soustraction : +, –

Fonctions mathématiques :

import math
  • math.ceil(2.6) entier supérieur
  • math.floor(-5.3) partie entière, donne ici -8.0.
  • math.sqrt : racine carrée.
  • math.pow(5, 5) : 5 puissance 5.
  • math.exp(2) : fonction exponentielle.
  • math.log(2) : fonction logarithme
  • math.log(3, 2) : log en base 2.
  • math.factorial(4) : factorielle
  • math.fsum(L) : somme des éléments d’une liste
  • math.sin, math.cos, math.tan : fonctions trigonométriques
  • math.pi : pi
  • math.degrees(y) : conversion de radians en degrés
  • math.radians(y) : conversion de degrés en radians

Expressions conditionnelles :

Python s’appuie sur l’indentation pour définir la portée du code.

x = 100
y = 23
if x > y:
  print("x plus grand que y")
elif a == b:
  print("égalité")
else:
  print("y plus grand que x")

Chaines de caractères formatées (f-strings) :

import math
print(f'La valeur de pi est {math.pi:.3f}.')

Listes à deux dimensions (matrices) :

matrix = [[1, 2, 3], [4,5, 6], [7, 8, 9]]
print(matrix[0][1])

Méthodes sur les listes :

list.append('n') #Ajoute un élément en fin de liste
list.insert(0,'a') #Ajoute un élément à la position spécifiée
liste.pop(1) #Enleve l'élément de la liste à la position spécifiée
liste.sort() #Trie la liste
liste.reverse() #Retourne la liste
liste.copy()   #retourne une copie de la liste

Python les bases en plus de 128 mots [Partie 1]

Voici mes notes pour apprendre très rapidement le langage python. En France ces bases sont enseignées en lycée aux classes de seconde SNT, première et terminale NSI. Elles font également partie du programme de connaissance pour le CAPES NSI.

Opérateurs logiques :

  • and : retourne True si les deux déclarations sont vraies
  • or : Renvoie True si l’une des déclarations est true
  • not : Inverser le résultat, renvoie False si le résultat est vrai

Opérateurs de comparaison :

  • == Égalité
  • != Non égal
  • > < Supérieur / Inférieur
  • <= >= Inférieur égal / Supérieur égal
  • != Différent

Mot clé pass :

Lorsque l’instruction pass est exécutée, rien ne se produit, mais vous évitez une erreur lorsque du code vide n’est pas autorisé.

x = 22
y = 150

if x > y:
  pass

Entrée utilisateur :

Utilisation de l’instruction input :

nom = input("Nom utilisateur :")
print("Username is: " + nom)

Boucle While :

La boucle while exécute un ensemble d’instructions tant qu’une condition est vraie. L’instruction break, permet d’arrêter la boucle même si la condition while est vraie.

x = 1
while x < 11:
  if x == 5:
    break
  x += 1 

Boucle For :

Une boucle for effectue une itération sur une séquence (une liste, un tuple, un dictionnaire, un ensemble ou une chaîne de caractère).

Une liste :

for x in [1, 2, 3]:
  print(x)

Une chaine de caractère :

for x in "hello":
  print(x)

Un tuple :

tupleObjet = ('Citroen', 2019, 'C4', 23000)
 
for elements in tupleObj:
    print(elements)

Un dictionnaire :

dico = {'couleur': 'vert', 'animal': 'chien', 'legume': 'epinard'}
for cle in dico:
    print(cle)

Fonction Range :

Pour boucler un nombre de fois spécifique, utilisez la fonction range ().

for x in range(10):
  print(x)

Les Listes :

Une liste est une collection qui est ordonnée et modifiable et qui permet les doublons.

liste = ["pomme", "banane", "poire"]
print(liste[1])
print(liste[-1]) #Affiche le dernier élément de la liste
print(liste[2:3])#Lorsque vous spécifiez une plage, la valeur de retour sera une nouvelle liste avec les éléments spécifiés.
print(liste[2:3])#Lorsque vous spécifiez une plage, la valeur de retour sera une nouvelle liste avec les éléments spécifiés.
print(liste[:3])#En omettant la valeur initiale, la plage commencera au premier élément:
print(liste[1:])#En omettant la valeur de fin, la plage ira à la fin de la liste:
print(liste[-2:-1])#des index négatifs pour lancer la recherche à partir de la fin de la liste: Cet exemple renvoie les éléments de l'index -2 (inclus) à l'index -1 (exclu).

Tri fusion Python – implémentation de l’algorithme

Le tri fusion suit le paradigme diviser pour régner qui consiste à diviser la tâche initiale en deux tâches similaires plus petites. Cet article présente une implémentation du tri fusion python.

Le tri fusion suit le paradigme diviser pour régner qui consiste à diviser la tâche initiale en deux tâches similaires plus petites. Cet article présent une implémentation du tri fusion python.

Introduction

L’algorithme est le suivant :
Diviser en deux moitiés la liste à trier.
On trie chacune d’entre elles.
Fusionner les deux moitiés obtenues pour reconstituer la liste triée.

On applique récursivement cet algorithme c’est à dire jusqu’à ce que la liste à trier soit constituée d’un seul élément.

tri fusion python
Tri fusion (source : wikipedia)
#Tri fusion fonction de division du tableau
def tri_fusion(tableau):
    if  len(tableau) <= 1: 
        return tableau
    pivot = len(tableau)//2
    tableau1 = tableau[:pivot]
    tableau2 = tableau[pivot:]
    gauche = tri_fusion(tableau1)
    droite = tri_fusion(tableau2)
    fusionne = fusion(gauche,droite)
    return fusionne


#Tri fusion fonction de fusion de 2 listes
def fusion(tableau1,tableau2):
    indice_tableau1 = 0
    indice_tableau2 = 0    
    taille_tableau1 = len(tableau1)
    taille_tableau2 = len(tableau2)
    tableau_fusionne = []
    while indice_tableau1<taille_tableau1 and indice_tableau2<taille_tableau2:
        if tableau1[indice_tableau1] < tableau2[indice_tableau2]:
            tableau_fusionne.append(tableau1[indice_tableau1])
            indice_tableau1 += 1
        else:
            tableau_fusionne.append(tableau2[indice_tableau2])
            indice_tableau2 += 1
    while indice_tableau1<taille_tableau1:
        tableau_fusionne.append(tableau1[indice_tableau1])
        indice_tableau1+=1
    while indice_tableau2<taille_tableau2:
        tableau_fusionne.append(tableau2[indice_tableau2])
        indice_tableau2+=1
    return tableau_fusionne

tableau = [11, 222, 3, 899, 24, 5, 46, 67]
print(tableau)
tableau_trie = tri_fusion(tableau)
print(tableau_trie)

A propos de tri fusion

Enfin, Le tri fusion fonctionne par comparaison. La complexité de l’algorithme pour n entrée est n log n, donc asymptotiquement optimal.

La technique est de diviser pour régner. Et l’algorithme fait principalement une opération de fusion (deux listes triées peuvent être fusionnées en temps linéaire).

Tri fusion python : liens externes

https://www.geeksforgeeks.org/merge-sort/

http://lwh.free.fr/pages/algo/tri/tri_fusion.html

https://pixees.fr/informatiquelycee/n_site/isn_algo_diviser_pour_regner.html

https://fr.wikipedia.org/wiki/Tri_fusion

https://graal.hypotheses.org/tag/algorithme-de-wagner-fischer

https://fr.wikipedia.org/wiki/Algorithme_de_Wagner-Fischer

https://fr.wikipedia.org/wiki/Distance_de_Levenshtein

https://medium.com/@sddkal/wagner-fischer-algorithm-be0d96893f6d

https://www.python-course.eu/levenshtein_distance.php

Liens internes sur les algorithmes

https://128mots.com/index.php/category/python/

https://128mots.com/index.php/category/graphes/

https://128mots.com/index.php/2020/02/17/lalgorithme-de-dijkstra-dans-un-graphe-pondere-et-oriente-en-plus-de-128-mots/

Pour calculer la distance de Levenshtein avec un algorithme non récursif. On utilise une matrice qui contient les distances de Levenshtein. Alors Ce sont les distances entre tous les préfixes de la première chaîne et tous les préfixes de la seconde chaîne de caractères.

Parcours en profondeur python – algorithmes graphes

Implémentons le parcours en profondeur python d’un Graphe. Cela consiste à explorer le graphe en mémorisant les sommets visités et le chemin pour y arriver.

Introduction

Le principe et d’explorer le graphe à partir d’un sommet donné et on explore tous ses voisins en allant le plus profond possible (càd en répétant l’opération de sommet visité en sommet visité jusqu’à ce qu’on soit coincé, on revient alors via le chemin emprunté jusqu’au point de départ).

Le parcours en profondeur permet de trouver l’arbre couvrant du graphe qui n’est pas le même en général que l’arbre couvrant trouvé via le parcours en largeur du graphe.

L’algorithme en résumé :

Phase de descente :

Partir du sommet choisi pour démarrer et le marquer.

Tant que c’est possible :

  • Aller vers un voisin non visité et le marquer.
  • Mémoriser l’arrête ou l’arc par lequel on est passé.
  • Si tous les voisins sont déjà visités :
    • Revenir vers le sommet par lequel il a été découvert (backtrack phase : de remontée)

Si tous les sommets du graphe sont visités (sont dans l’arbre couvrant) alors le graphe est connexe sinon le graphe n’est pas connexe.

Exemple Python avec 3 graphes :

Implémentons le parcours en profondeur python d'un Graphe. Cela consiste à explorer le graphe en mémorisant les sommets visités et le chemin pour y arriver.
Exemple de graphe connexe
Implémentons le parcours en profondeur python d'un Graphe. Cela consiste à explorer le graphe en mémorisant les sommets visités et le chemin pour y arriver.
Exemple de graphe non connexe
Implémentons le parcours en profondeur python d'un Graphe. Cela consiste à explorer le graphe en mémorisant les sommets visités et le chemin pour y arriver.
Exemple de graphe connexe

Module Python pour le parcours en profondeur :

#Parcours en profondeur d'un graphe
# Algorithme récursif : Le principe est d'explorer le graphe et de revenir sur ses pas lorsuqu'on est coincé.
def parcours_en_profondeur(graphe, sommet_en_cours:str, sommets_visites:[]):
	print('Essai d explorer le sommet :' + str(sommet_en_cours))
	if sommet_en_cours not in sommets_visites:
		sommets_visites.append(sommet_en_cours) #Ajoute le sommet en cours au noeud visité
		print('Exploration du sommet :' + str(sommet_en_cours))
	sommets_voisins_non_visites = []
	for sommet_voisin in graphe[sommet_en_cours]:
		if sommet_voisin not in sommets_visites:
			sommets_voisins_non_visites.append(sommet_voisin) # Constitue la liste des sommets voisins non encore visité

	for sommet in sommets_voisins_non_visites:
		#pour tout les sommets voisins non visités on effectue un parcours en profondeur
		parcours_en_profondeur(graphe, sommet, sommets_visites)

#Fonction de test si le graphe est connexe suite à un parcours en profondeur
def est_un_graphe_connexe(graphe, sommets_visites):
	if len(sommets_visites) == len(graphe):
		print("Le graphe est connexe")
		print(20 * "-")
	else:
		print("Le graphe n'est pas connexe")
		print(20 * "-")


#Liste d'ajacence du graphe
graphe = {
	'A': ['B','C'],
	'B': ['A','C', 'D'],
	'C': ['D'],
	'D': ['C','A']
}

sommets_visites = []
parcours_en_profondeur(graphe,'A',sommets_visites)
est_un_graphe_connexe(graphe,sommets_visites)

#Exemple de graphe non connexe : Le sommet D n'est pas connecté au graphe
graphe = {
	'A': ['B','C'],
	'B': ['A','C'],
	'C': ['A'],
	'D': []
}

sommets_visites = []
parcours_en_profondeur(graphe,'A',sommets_visites)
est_un_graphe_connexe(graphe,sommets_visites)

#Autre exemple
graphe = {
	'A': ['B','D'],
	'B': ['A','C'],
	'C': [],
	'D': ['A']
}

sommets_visites = []
parcours_en_profondeur(graphe,'A',sommets_visites)
est_un_graphe_connexe(graphe,sommets_visites)

#en fin de parcours si tout les sommets sont dans les sommets visités alors le graphe est connexe

#Note
#J'ai rencotré l'erreur IndentationError: unindent does not match any outer indentation level
#Je l'ai simplement résolu en reprenant toute l'indentation en debut de ligne
#et en la remplaçant par des Tabulation plutot que des espaces
https://128mots.com/index.php/en/2021/01/13/quantum-sort-algorithm/

https://128mots.com/index.php/category/non-classe/

Parcours en profondeur python : Liens externes :

https://fr.wikipedia.org/wiki/Th%C3%A9orie_des_graphes

https://www.kartable.fr/ressources/mathematiques/cours/les-graphes/4795

http://math.univ-lyon1.fr/irem/Formation_ISN/formation_parcours_graphes/graphe/1_notion_graphe.html

Edu python – Tutorial pour apprendre le Python

Edu python tutorial pour apprendre le python : En python tout est objet. Un objet est un morceau de code qui est caractérisé par :Des données, des Méthodes : Ce sont des mécanismes pour manipuler les données.

Edu python

Introduction Edupython

Création de l’objet

Un objet de type chaine de caractère est créé dans l’espace des objets via le caractère ” ou ‘.

Les appels de méthode se font via un point :

'hello'.upper()

Un nom de variable permet de stocker une référence à l’objet :

compteur = 1

La variable qui s’appelle compteur référence l’objet 1

En python le nom de variable contient des lettres et des chiffres mais ne peut commencer par un chiffre. Une bonne pratique est de donner un bon nom de variable.

Exemple :

ma_variable = 5

Déréférencement :

ma_variable = 'HELLO'

Python est langage à typage fort, le type est lié à l’objet et non à la variable.

del ma_variable

La commande del supprime la variable de l’espace des variables. Si l’objet n’a plus de référence un mécanisme de libération de la mémoire s’active : le garbage collector.

Edu python – Liens internes :

https://128mots.com/index.php/category/python/

https://128mots.com/index.php/2021/01/19/levenshtein-python/

edu python – Liens externes :

https://www.python.org/

https://openclassrooms.com/fr/courses/4262331-demarrez-votre-projet-avec-python

Exemple d’alorithme python :

Voici l’implémentation en python de l’algorithme de Wagner & Fischer (Wagner-Fischer). Il permet de calculer la distance de Levenshtein (distance entre deux chaines de caractères).

Premièrement le but de l’algorithme est de trouver le coût minimal. Coût minimal pour transformer une chaîne en une autre. Alors une fonction récursive permet de retourner le nombre minimal de transformation. Et pour transformer une sous-chaine de A avec n caractères en une sous-chaine de B avec le même nombre de caractères. La solution est donnée. Il faut calculer la distance entre les 2 lettres à la même position dans la chaine A et B. Alors Soit les lettres et la lettre précédentes sont identiques. Soit il y a une différence et dans ce cas on calcule 3 côuts. Alors le premier est de supprimer une lettre le la chaine A. Et d’insérer une lettre dans la chaine A pour substituer une lettre de la chaine A. Alors On peut alors trouver le cout minimal.

import numpy as np
def levenshtein(chaine1, chaine2):
    taille_chaine1 = len(chaine1) + 1
    taille_chaine2 = len(chaine2) + 1
    levenshtein_matrix = np.zeros ((taille_chaine1, taille_chaine2))
    for x in range(taille_chaine1):
        levenshtein_matrix [x, 0] = x
    for y in range(taille_chaine2):
        levenshtein_matrix [0, y] = y
    for x in range(1, taille_chaine1):
        for y in range(1, taille_chaine2):
            if chaine1[x-1] == chaine2[y-1]:
                levenshtein_matrix [x,y] = min(
                    levenshtein_matrix[x-1, y] + 1,
                    levenshtein_matrix[x-1, y-1],
                    levenshtein_matrix[x, y-1] + 1
                )
            else:
                levenshtein_matrix [x,y] = min(
                    levenshtein_matrix[x-1,y] + 1,
                    levenshtein_matrix[x-1,y-1] + 1,
                    levenshtein_matrix[x,y-1] + 1
                )
    return (levenshtein_matrix[taille_chaine1 - 1, taille_chaine2 - 1])
print("distance de levenshtein = " + str(levenshtein("Lorem ipsum dolor sit amet", "Laram zpsam dilir siy amot")))

Le langage Python en moins de 128 mots

Python est un langage de programmation qui est caractérisé par :

  • sa lisibilité : La syntaxe du langage est articulé sur la présentation (importance de l’indentation)
  • Pragmatique : L’objectif est de faire des programmes efficaces qui contiennent le moins de lignes de code possible.

Il est également facile d’accès, on peut ainsi facilement échanger avec d’autre programmeur.

La première version de python date de 1994, Python 3 date de 2008. Le langage est stable puisque les anciennes versions du langages continuent d’être maintenue (mise à jour).

Python est portable, il fonctionne sur la plupart des plateformes (mobile, PC, MAC, Linux …), il y a beaucoup de librairies disponibles.

Python est sous licence PSF, le débat sur les évolutions est démocratique et sont soumises au créateur du langage Guido Van Rossum.

PageRank Python – Implémentation de l’algorithme en python

PageRank python est un algorithme utilisé par Google Search pour classer les sites Web dans les résultats de leurs moteurs de recherche. PageRank est un moyen de mesurer l’importance des pages de site Web.

pagerank python

Introduction :

Ce n’est pas le seul algorithme utilisé par Google pour ordonner les résultats des moteurs de recherche, mais c’est le premier algorithme utilisé par la société, il est le plus connu.

Le PageRank d’une page est calculé à partir de la somme du PageRank des pages avec un lien entrant à la page calculée que l’on divise par le nombre de pages sortantes de cette dernière, on applique un facteur d’atténuation pour symboliser la probabilité que l’utilisateur surfe sur une autre page.

Implémentation pagerank python :

J’installe networkx, c’est un package Python pour la création, la manipulation et l’étude de la structure, de la dynamique et des fonctions de réseaux complexes.

Networkx fournit des structures de données et des méthodes pour stocker des graphes que j’utilise pour l’algorithme pagerank.

import networkx as nx
import numpy as np

graphe=nx.DiGraph()

tableauPages = ["A","B","C"] #Exemple de page rank avec 3 pages
graphe.add_nodes_from(tableauPages) #Ajout des sommets du graphe

#on ajoute des arcs, on a :
#la page A a un lien vers B 
#la page B a un lien vers C
#la page C a un lien vers B
#la page C a un lien vers A
# la page B a 2 lien entrant
# la page C a un lien entrant 2 liens sortant
# la page A a un lien entrant un lien sortant
graphe.add_edges_from([('A','B'), ('C','A'),('B','C'), ('C','B')])
print("Sommets du graphe : ")
print(graphe.nodes())
print("Arrêtes du graphe : ")
print(graphe.edges())
#Si on considere un facteur d'attenuation de 0.85 = d
# la formule du page rank est :
#PR(p) = (1-d)/n + d * Somme de toutes les pages(PR(i) des lien entrants à p/nombre de lien sortant de la page qui reference p)
# PR(A) = (1-0,85)/3 + 0,85 * (PR(C)/2)
# PR(B) = (1-0,85)/3 + 0,85 * (PR(A)/1 + PR(C)/2)
# PR(C) = (1-0,85)/3 + 0,85 * (PR(B)/1)

pagerank = nx.pagerank(graphe)
print(pagerank)

Pagerank python liens externes :

https://fr.wikipedia.org/wiki/M%C3%A9thode_des_k_plus_proches_voisins

https://www.python.org/

https://www.educative.io/blog/python-algorithms-coding-interview

Liens internes :

https://128mots.com/?s=dijkstra

Tri par tas Python – implémentation de l’algorithme en Python

L’algorithme du tri par tas est un algorithme de tri par comparaison. Cet article vous done le code du tri par tas python.

L'algorithme du tri par tas python est un algorithme de tri par comparaison. Cet article vous done le code du tri par tas python.

Le principe de l’algorithme du tri par tas python est le suivant :

  1. Alors on recherche le père du dernier nœud de l’arbre et on le tamise : le père d’un noeud dans un arbre binaire corresponds à l’arrondi inférieur de (i-1)/2 avec i la position du noeud dans le tableau qui stocke l’arbre.
  2. Le tamisage d’un noeud consiste à visiter son fils droit et son fils gauche et permuter la racine avec le plus grand des deux.
  3. Et il faut tamiser l’arbre jusqu’à arriver à la racine, le plus grand nombre de l’arbre se retrouve alors en position de racine au début du tableau.
  4. On permute la racine qui est le plus grand nombre avec la dernière feuille (soit la position n du tableau qui stocke l’arbre de taille n). On considère alors que ce nombre est bien ordonné (càd il est en dernière position et c’est le plus grand)
  5. Enfin, l’opération de tamisage et permutation est réitérée en considérant le sous arbre qui va de la racine à n-1 (pour ne pas déplacer le nombre qui a été correctement ordonné) jusqu’à ce qu’on arrive au fils gauche de la racine (l’indice 1)

Voir le lien wikipedia : https://fr.wikipedia.org/wiki/Tri_par_tas

from math import *
#128mots.com
def indice_fils_gauche(noeud_pere:int):
	return (noeud_pere * 2)+ 1

def indice_fils_droit(noeud_pere:int):
	return (noeud_pere * 2) + 2
#Retourne l'indice du noeud pere si il existe (noeud doit être > 0)
def indice_noeud_pere(noeud):
	#Si il existe il s'agit de l'arrondi inférieur de (noeud-1)/2
	return floor((noeud - 1)/2)

#permute 2 éléments d'un tableau et incrément la variable globale compteur_permutation à initialiser dans le main
def permute(tableau, indice1: int, indice2:int):
	print("Permutation de l'élément " + str(indice1) + " avec l'element " + str(indice2))
	print("**Avant permutation : " + str(tableau))
	global compteur_permutation
	if(indice1 != indice2):
	#on sauvegarde la valeur de l'indice 1 dans une variable temporaire
		tmp = tableau[indice1]
		tableau[indice1] = tableau[indice2]
		tableau[indice2] = tmp
		compteur_permutation += 1
	print("**Apres permutation : " + str(tableau))

#Tamise un arbre binaire à partir d'un noeud en parametre
#1. on compare le noeud avec le fils droit et le fils gauche (si ils existent)
#2. on permute avec la plus grande valeur
#128mots.com
def tamise(arbre,noeud,longueur):
	#On visite le fils droit et le fils gauche
	print("++Tamisage de " + str(noeud) + " arbre: " + str(arbre))	
	indiceFilsDroit   = indice_fils_droit(noeud)
	indiceFilsGauche  = indice_fils_gauche(noeud)
	print("indiceFilsDroit>>" + str(indiceFilsDroit))
	print("indiceFilsGauche>>" + str(indiceFilsGauche))


	if(indiceFilsDroit < longueur): # si le fils droit existe
		if(arbre[indiceFilsDroit] > arbre[indiceFilsGauche]): #Si le fils droit est plus grand que le fils gauche
			if(arbre[indiceFilsDroit] > arbre[noeud]): #Si le fils droit est plus grand que le noeud tamisé
				permute(arbre,indiceFilsDroit,noeud)
		elif(arbre[indiceFilsGauche] > arbre[noeud]): #Si le fils gauche est supérieur au noeud tamisé alors on permute
			permute(arbre,indiceFilsGauche,noeud)
	elif(indiceFilsGauche < longueur): #Si le fils gauche existe
		if(arbre[indiceFilsGauche] > arbre[noeud]): #Si le fils gauche est supérieur au noeud tamisé alors on permute
			permute(arbre,indiceFilsGauche,noeud)
	print("++Apres tamisage : " + str(arbre))			
#128mots.com

compteur_permutation = 0
arbre = [11, 222, 3, 24, 5, 46, 67, 899] #On écrit un arbre sous forme de tableau
print("démarrage arbre : " + str(arbre))

#128mots.com
#Tamisage initial
#on prend le dernier élément de l'arbe qui est une feuille et on recherche son père
indiceDuNoeudPere = indice_noeud_pere(len(arbre)-1) 
#on tamise càd on compare le noeud pere avec le fils droit et le fils gauche
#puis on permute avec la plus grande valeur
for i in range(indiceDuNoeudPere,-1,-1): #On tamise jusqu'à la racine
	tamise(arbre,i,len(arbre))

permute(arbre,len(arbre)-1,0) #on permute le premier element et le dernier 
#suite au tamisage c'est la plus grande valeur on la place donc à la fin du tableau

#on répete le tamisage
for i in range(len(arbre)-1,1,-1): 
	indiceDuNoeudPereDeI = indice_noeud_pere(i-1) #on prend l'élément i de l'arbe qui est une feuille et on recherche son père
	for j in range(indiceDuNoeudPereDeI,-1,-1): #On tamise jusqu'à la racine
		tamise(arbre,j,i)
	permute(arbre,i-1,0)

print("resultat final du tri : " + str(arbre))
print("nombre de permutation : " + str(compteur_permutation))

Conclusion

En conclusion, L’algorithme est utilisé pour trier sur place les éléments d’un tableau en un temps de l’ordre de n log ⁡ n.

Et l’étape qui coûte le plus dans cet algorithme est la seconde boucle (extraction des éléments du tas).

Enfin, et algorithme a l’avantage de consommer peu de mémoire par rapport à d’autres algorithme de tri.

Tri pas tas python : liens externes

https://fr.wikipedia.org/wiki/Tri_par_tas

https://fr.wikipedia.org/wiki/Smoothsort

https://wiki.inria.fr/sciencinfolycee/Le_tri_par_tas

http://perso.numericable.fr/jules.svartz/prepa/IPT_spe/TP_tris_efficaces_tas.pdf

https://www.prepabellevue.org/index.php?module=Site&voir=document&id_document=589

Liens internes sur les algorithmes

https://128mots.com/index.php/2021/01/13/algorithme-tri-quantique/

https://128mots.com/index.php/category/python/

https://128mots.com/index.php/category/graphes/

if __name__ == ‘__main__’ dans les scripts Python en moins de 128 mots

Lorsqu’on écrit un module Python il n’y a pas de méthode main, par exemple le script stade.py

def joueurs():
    print("Allez les bleus")
 
joueurs()

Si on démarre le script “python stade.py” on obtient “Allez les bleus” la fonction est démarrée.

Si je crée un script championnat.py qui importe stade.py

import stade

def equipe():
    print("Equipe")
 
equipe()

On obtient en démarrant “python championnat.py”

python championnat.py 
Allez les bleus
Equipe

On constaez ici que la fonction joueurs() du module stade est démarrée.

Pour éviter cela on peut modifier le script stade.py :

def joueurs():
    print("Allez les bleus")
if __name__ == '__main__' 
	joueurs()

Tri rapide en Python en moins de 128 mots

Le tri rapide (QuickSort) choisir aléatoirement un élément (appelé pivot) et de le positionner à sa place définitive, en permutant tous les éléments pour que ceux qui sont inférieurs au pivot soient à sa gauche et que ceux qui sont supérieurs au pivot soient à sa droite.

L’opération est appelée le partitionnement. Pour chacune des sous-listes (ou sous-tableaux), on choisit aléatoirement un nouveau pivot et on répète l’opération de partitionnement. Ce processus est répété récursivement, jusqu’à ce que tous les éléments soit trié.

Le partitionnement consiste à :

  • permuter le pivot avec le dernier élément du sous-tableau
  • placer en début du sous-tableau les éléments inférieurs au pivot
  • déplacer le pivot à droite du dernier élément déplacé en début de tableau (les autres éléments étant supérieur au pivot).
Exemple d’une itération de partitionnement (source wikipedia) : Ici le pivot est 5
from random import randint 


#Choix d'un pivot aléatoirement
#128mots.com
def choix_pivot(tableau,premier: int,dernier: int):
	pivot = randint(premier,dernier) 
	print("La sous-liste non triée est : " + str(tableau[premier:dernier+1]))
	print("Le pivot choisi aleatoirement est l'indice " + str(pivot) + " de valeur =" + str(tableau[pivot]))
	return pivot

#Fonction pour effectuer le partitionnement du tableau
#Permutation de tous les éléments pour que ceux qui sont inférieurs au pivot
# soient à sa gauche et que tous ceux qui sont supérieurs au pivot 
#soient à sa droite. 
#128mots.com
def partitionner(tableau, debut: int, fin: int, pivot: int):
	#Etape 1 : on positionne le pivot à la fin de la sous-liste arbitrairement	
		#On permute le pivot et le dernier element
	print("Partitionnement de la sous-liste = " + str(tableau[debut:fin+1]))
	print("---Placement du pivot à la fin la sous-liste")
	permute(tableau, pivot, fin)
	print("---")

	j = debut #indice d'avancement dans le début de la sous-liste
	#Pour i du début de la sous-liste à la fin
	for i in range(debut,fin):	
	#Tous les élément inférieur au pivot sont placés au début de la sous-liste
		if(tab[i] <= tab[fin]):
		#Si la valeur est inférieure on déplace au début du tableau
		#Et que la valeur n'est pas déjà bien placée alors on déplace au début du tableau
			permute(tableau,i,j)
			j+=1	
	#On place le pivot à la bonne place en permuttant l'élément après le dernier trouvé comme inférieur au pivot
	print("**permutation du pivot")
	permute(tableau,fin,j)
	#on retourne la position de j qui est alors la nouvelle position du pivot dans le tableau
	return j	


#Fonction de permutation de deux élément d'un tableau
#128mots.com
def permute(tableau, indice1: int, indice2:int):
	print("Permutation de l'élément " + str(indice1) + " avec l'element " + str(indice2))
	print("**Avant permutation : " + str(tab))
	global compteur_permutation
	if(indice1 != indice2):
	#on sauvegarde la valeur de l'indice 1 dans une variable temporaire
		tmp = tableau[indice1]
		tableau[indice1] = tableau[indice2]
		tableau[indice2] = tmp
		compteur_permutation += 1
	print("**Apres permutation : " + str(tab))

#Fonction de tri rapide d'une sous-liste d'un tableau
#128mots.com
def  tri_rapide(tableau,debut: int,fin: int):
	# Si on a une sous-liste qui contient au moins 2 éléments
	if debut < fin :
		#on choisit un pivot dans la sous-liste
		pivot = choix_pivot(tableau,debut,fin)
		#on déplace tout les élément inférieur au pivot à gauche du pivot
		pivot = partitionner(tableau,debut,fin,pivot)
		#recursion pour refaire l'algorithme sur la sous-liste à gauche du pivot trouvé
		tri_rapide(tableau,debut,pivot - 1)
		#recursion pour refaire l'algorithme sur la sous-liste à droite du pivot trouvé
		tri_rapide(tableau,pivot + 1,fin)


compteur_permutation = 0
tab = [111, 34, 22, 55, 4, 2, 1, 77]
tri_rapide(tab,0,len(tab)-1)
print("resultat final du tri : " + str(tab))
print("nombre de permutation : " + str(compteur_permutation))

La sortie du programme est la suivante :

La sous-liste non triée est : [111, 34, 22, 55, 4, 2, 1, 77]
Le pivot choisi aleatoirement est l'indice 6 de valeur =1
Partitionnement de la sous-liste = [111, 34, 22, 55, 4, 2, 1, 77]
---Placement du pivot à la fin la sous-liste
Permutation de l'élément 6 avec l'element 7
**Avant permutation : [111, 34, 22, 55, 4, 2, 1, 77]
**Apres permutation : [111, 34, 22, 55, 4, 2, 77, 1]
---
**permutation du pivot
Permutation de l'élément 7 avec l'element 0
**Avant permutation : [111, 34, 22, 55, 4, 2, 77, 1]
**Apres permutation : [1, 34, 22, 55, 4, 2, 77, 111]
La sous-liste non triée est : [34, 22, 55, 4, 2, 77, 111]
Le pivot choisi aleatoirement est l'indice 5 de valeur =2
Partitionnement de la sous-liste = [34, 22, 55, 4, 2, 77, 111]
---Placement du pivot à la fin la sous-liste
Permutation de l'élément 5 avec l'element 7
**Avant permutation : [1, 34, 22, 55, 4, 2, 77, 111]
**Apres permutation : [1, 34, 22, 55, 4, 111, 77, 2]
---
**permutation du pivot
Permutation de l'élément 7 avec l'element 1
**Avant permutation : [1, 34, 22, 55, 4, 111, 77, 2]
**Apres permutation : [1, 2, 22, 55, 4, 111, 77, 34]
La sous-liste non triée est : [22, 55, 4, 111, 77, 34]
Le pivot choisi aleatoirement est l'indice 4 de valeur =4
Partitionnement de la sous-liste = [22, 55, 4, 111, 77, 34]
---Placement du pivot à la fin la sous-liste
Permutation de l'élément 4 avec l'element 7
**Avant permutation : [1, 2, 22, 55, 4, 111, 77, 34]
**Apres permutation : [1, 2, 22, 55, 34, 111, 77, 4]
---
**permutation du pivot
Permutation de l'élément 7 avec l'element 2
**Avant permutation : [1, 2, 22, 55, 34, 111, 77, 4]
**Apres permutation : [1, 2, 4, 55, 34, 111, 77, 22]
La sous-liste non triée est : [55, 34, 111, 77, 22]
Le pivot choisi aleatoirement est l'indice 4 de valeur =34
Partitionnement de la sous-liste = [55, 34, 111, 77, 22]
---Placement du pivot à la fin la sous-liste
Permutation de l'élément 4 avec l'element 7
**Avant permutation : [1, 2, 4, 55, 34, 111, 77, 22]
**Apres permutation : [1, 2, 4, 55, 22, 111, 77, 34]
---
Permutation de l'élément 4 avec l'element 3
**Avant permutation : [1, 2, 4, 55, 22, 111, 77, 34]
**Apres permutation : [1, 2, 4, 22, 55, 111, 77, 34]
**permutation du pivot
Permutation de l'élément 7 avec l'element 4
**Avant permutation : [1, 2, 4, 22, 55, 111, 77, 34]
**Apres permutation : [1, 2, 4, 22, 34, 111, 77, 55]
La sous-liste non triée est : [111, 77, 55]
Le pivot choisi aleatoirement est l'indice 5 de valeur =111
Partitionnement de la sous-liste = [111, 77, 55]
---Placement du pivot à la fin la sous-liste
Permutation de l'élément 5 avec l'element 7
**Avant permutation : [1, 2, 4, 22, 34, 111, 77, 55]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
---
Permutation de l'élément 5 avec l'element 5
**Avant permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
Permutation de l'élément 6 avec l'element 6
**Avant permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**permutation du pivot
Permutation de l'élément 7 avec l'element 7
**Avant permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
La sous-liste non triée est : [55, 77]
Le pivot choisi aleatoirement est l'indice 6 de valeur =77
Partitionnement de la sous-liste = [55, 77]
---Placement du pivot à la fin la sous-liste
Permutation de l'élément 6 avec l'element 6
**Avant permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
---
Permutation de l'élément 5 avec l'element 5
**Avant permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**permutation du pivot
Permutation de l'élément 6 avec l'element 6
**Avant permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
resultat final du tri : [1, 2, 4, 22, 34, 55, 77, 111]
nombre de permutation : 10

Le nombre de permutation est 10 pour un tableau de 8 éléments.

La complexité moyenne du tri rapide est Θ(n log n) soit 7.22 pour un tableau de 8 éléments.