Tri fusion Python – Apprendre l’algorithme

Le tri de fusion suit le paradigme diviser pour conquérir, qui divise la tâche initiale en deux tâches plus petites similaires. Cet article présente l’implémentation du tri par fusion en python.

Introduction

L’algorithme est le suivant: Divisez la liste triée en deux moitiés. Nous avons trié tout le monde. Les deux moitiés obtenues sont fusionnées pour reconstruire la liste triée.

Cet algorithme est appliqué de manière récursive, c’est-à-dire jusqu’à ce que la liste à trier soit constituée d’un seul élément.

Tri fusion Python - Apprendre l'algorithme

Tri fusion (source : wikipedia)

#Tri fusion fonction de division du tableau
def tri_fusion_fonction_recursive(tableau):
    if  len(tableau) <= 1: 
        return tableau
    pivot = len(tableau)//2
    tableau1 = tableau[:pivot]
    tableau2 = tableau[pivot:]
    gauche = tri_fusion_fonction_recursive(tableau1)
    droite = tri_fusion_fonction_recursive(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)
le_tableau_trie = tri_fusion_fonction_recursive(tableau)
print(le_tableau_trie)

Enfin, le tri par fusion est effectué par comparaison. La complexité de l’algorithme pour n entrées est n log n, il est donc asymptotiquement optimal.

La technologie divise et conquiert. L’algorithme effectue principalement une opération de fusion (deux listes triées peuvent être fusionnées en temps linéaire). Les algorithmes sont capables de fusionner en un “binaire” pour chacune des deux listes et de créer également la liste souhaitée qui est ensuite triée en plusieurs listes consécutives. Chaque représentation binaire (dans l’ordre) est un ensemble de valeurs. Après avoir créé une représentation binaire, nous devons générer un vecteur à l’aide de l’algorithme. En conséquence, nous obtenons une représentation binaire. Ensuite, nous devons faire un calcul pour chaque matrice dans l’ordre. Le message principal du message principal de notre algorithme est que nous pourrions générer un certain nombre de vecteurs avec de nombreuses opérations à notre disposition. C’est l’algorithme utilisé ici.

A propos d’algorithme

Utiliser les algorithmes présentés ici est beaucoup plus facile maintenant que nous avons une bibliothèque d’algorithmes grande et complexe qui prend en charge les vecteurs, les listes, les tuples, les listes avec toutes les opérations possibles que nous pouvons écrire, qui sont toutes définies dans le langage C et peuvent être utilisé pour effectuer des opérations sur des vecteurs, des listes et des tuples. Tout ce dont nous avons besoin pour cela est un moyen de définir un vecteur avec beaucoup d’opérations, mais nous pouvons simplement utiliser la représentation C d’un vecteur:

Tri fusion Python - Apprendre l'algorithme

La représentation du vecteur en tant que vecteur est très simplifiée car il n’a pas de type valeur, la seule différence est qu’il a une normale, qui n’est en réalité qu’un vecteur sans objet régulier. Puisque nous commençons avec un vecteur ordinaire, le vecteur (t), qui est une fonction de notre propre

Tri fusion python : liens externes

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

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

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)

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

Vous trouverez ici des liens intéressants sur les algorithmes, la programmation python et plus encore. Voici quelques excellentes ressources, ainsi que quelques articles qui expliquent les algorithmes à tous les niveaux.

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

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

“Le Web à son meilleur” sur Wikipédia est une excellente ressource pour les utilisateurs débutants et expérimentés. Il contient plus de 1000 articles avec des informations et des recommandations précieuses. Le site est également une excellente source d’informations sur le monde actuel du Web, qui comprend des informations sur les meilleurs algorithmes, les techniques Web et plus encore.

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

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

Si vous aimez la technologie et que vous êtes inspiré par les défis auxquels le monde du Web est confronté, c’est un site formidable auquel faire partie, surtout si vous consultez certains de leurs tutoriels et ressources.

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

Vous trouverez ici des liens intéressants sur les algorithmes, la programmation python, les outils, les langages de programmation, l’apprentissage automatique et bien plus encore. Si vous êtes intéressé mais que vous ne savez pas ce qu’est une approche d’apprentissage automatique, vous devriez consulter ces tutoriels!

De plus, comme le tutoriel se termine par quelques statistiques intéressantes (vous pouvez le voir pour la première fois sur leur page. 🙂

Articles Similaires

Pour ceux d’entre vous qui aiment consulter le reste de mon blog:

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

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

https://128mots.com/index.php/2019/12/03/le-tri-fusion-et-implementation-python-en-moins-de-128-mots/

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.

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/

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.

Tri par sélection Python – Implémentation de l’algorithme

Tri par sélection python : Implémentation de l’algorithme exemple complet avec code source.

tri par sélection python
tab = [111, 34, 22, 55, 4, 2, 1, 77]

for i in range(0,len(tab)-1):
	min = i
	for j in range(i+1,len(tab)):
		if tab[j]<tab[min]:
			min = j
	if (min != i):
		tmp = tab[i]
		tab[i] = tab[min]
		tab[min] = tmp

print(tab)

Introduction :

Si on considère l’opération de comparaison “if tab[j]<tab[min]” et n la taille du tableau.

Si i = 0 ==> (n-1) comparaisons

Si i = 1 ==> (n-2) comparaisons

… Si i = n-2 ==> 1 comparaison

soit n * (n-1) comparaisons

Donc la boucle for i in range(0,len(tab)-1): s’exécute n-1 fois

La boucle for j in range(i+1,len(tab)): s’exécute (n-(i+1) + 1) fois

La complexité en nombre de comparaison est égale à la somme des n-1 termes suivants (i = 1, …i = n-1)

C = (n-2)+1 + (n-3)+1 +…..+1+0 = (n-1)+(n-2)+…+1 = n.(n-1)/2 (c’est la somme des n-1 premiers entiers).

La complexité en nombre de comparaison est de de l’ordre de n², on écrit O(n²).

Tri par sélection python liens externes :

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

https://www.python.org/

Liens internes :

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