Manipulation des itérables en Python

Introduction #

On considère des données numériques. Trier ces données consiste à les ranger en ordre croissant ou décroissant. Une opération de tri consomme un temps de calcul important sur un ordinateur et il est donc nécessaire d'étudier la complexité temporelle des différents algorithmes de tri.

De plus, la recherche est une opération fondamentale dans un programme qui gère un ensemble de données. Elle participe souvent à l'élaboration des autres traitements, par exemple en localisant la donnée à afficher ou à modifier. La recherche traite deux informations distinctes, la clef et la donnée. La clef est l'information utilisée dans la recherche pour localiser la donnée.

Les algorithmes de recherche #

La recherche séquentielle

La recherche séquentielle d'un élément dans une liste consiste à vérifier si x se trouve dans une liste L. La méthode consiste à parcourir la liste et de chercher s'il existe un indice i tel que L[i] == x. La complexité en temps de la recherche séquentielle est en O(N).

def rechercheSeq (L,x):
    for i in range (len(L)):
        if L[i]== x:
            return True
    return False

La recherche dichotomique

L'algorithme qui suit renvoie également un booléen suivant si x est dans L, mais suppose également que la liste L est triée. Sa complexité est en O(log(N)).

def rechercheDicho (L,x):
    g=0
    d=len(L)
    while g<d:
        m=(g+d)//2
        if L[m]== x:
            return True
        elif L[m]<x:
            g=m+1
        else :
            d=m
    return False

Voici une solution récursive :

def rechercheDichoRec (L,x,g,d) :
    if g>d:
        return ( False )
    m =(g+d) //2
    if x==L[m]:
        return ( True )
    if x<L[m]:
        return rechercheDichoRec ( L, x , g , m -1)
    else :
        return rechercheDichoRec ( L, x , m+1, d )

En adoptant maintenant le paradigme "diviser pour régner", il est possible de rechercher récursivement l'élément dans la première moitié de la liste et dans la seconde, puis de combiner les résultats via l'opérateur logique or. En effet, l'élément recherché sera dans la liste s'il est dans la première moitié ou dans la seconde. La condition d'arrêt à la récursivité sera l'obtention d'une liste à un seul élément, car il est alors immédiat de conclure si l'élément recherché appartient à une telle liste ou non.

def recherche (L,x,g,d):
    if g == d:
        return L[d] == x
    m = (g+d) // 2
    return recherche (L,x,g,m) or recherche (L,x,m+1,d)

Les algorithmes de tri #

Tri par insertion

Le tri par insertion d'une liste à n éléments L = [l₀, ⋯, l_n-1] se fait comme suit :

• à l'étape numéro i, (i variant de 0 à n-1), on suppose que les données d'indice 0 jusqu'à i - 1 sont déjà triées et on considère alors la donnée d'indice i, c'est-à-dire l'élément l_i.
• on compare l_i aux données précédentes [l₀, ⋯, l_i-1], en commençant par l_i-1, puis l_i-2 jusqu'à trouver la bonne place pour l_i, c'est-à-dire entre deux données successives (qui sont déjà triées), l'une étant plus petite et l'autre plus grande que l_i, ou bien en tout premier si l_i est plus petite que toutes les données précédentes.
• au fur et à mesure de ces comparaisons, on décale d'une place vers la droite les données plus grandes que l_i.
• enfin, on met la valeur l_i à la bonne place et à l'issue de cette étape, les données d'indice 0 à i sont donc triées.

def triInsertion (L):
    for i in range (0, len(L)):
        x = L[i]
        j = i
        # décalage des éléments de la liste
        while j >0 and L[j -1] >x:
            L[j]=L[j -1]
            j = j -1
        # on insère l'élément à sa place
        L[j]=x

Tri par sélection

Le tri par sélection d'une liste à n éléments L = [l₀, ⋯, l_n-1] se fait comme suit :

• On cherche la plus petite donnée et on la place en première position, puis on cherche la plus petite donnée parmi les données restantes et on la place en deuxième position, et ainsi de suite.
• L'algorithme consiste donc à faire varier i de 0 à n - 2. Pour chaque itération de i, on recherche dans la tranche [l_i, ⋯, l_n-1] le plus petit élément et on l'échange avec l_i.

def posMin (L):
    p=0
    for i in range (1, len(L)):
        if L[i]<L[p]:
            p=i
    return p

def triSelection (L):
    for i in range (0, len(L)):
        p= posMin (L[i:])
        L[i],L[p+i]=L[p+i],L[i]

Tri à bulles

Avec l'algorithme du tri à bulles, on permet seulement l'échange de deux éléments consécutifs de la liste à trier. L'algorithme se fait comme suit :

• on parcourt la liste et si deux éléments consécutifs sont rangés dans le désordre, on les échange ;
• si un échange a eu lieu, on recommence l'opération ;
• sinon, la liste est triée, on arrête les calculs.

def triBulle (L):
    n=len(L)
    while 1:
        permutation = False
        for i in range (1,n):
            if L[i]<L[i -1] :
                L[i],L[i -1]= L[i -1] ,L[i]
                permutation = True
        if permutation == False :
            break
        n=n -1

Le tri Shaker

Dans le tri à bulles, les gros éléments initialement placés dans la gauche de la liste ont tendance à remonter vite vers la droite, alors que les petits éléments situés à droite ne se déplacent que d'un cran vers la gauche au plus à chaque passage de boucle while. C'est dû au fait que le tri à bulles utilise comme boucle interne un parcours de la liste de gauche à droite : for i in range(1, n) avec la comparaison de L[i] et L[i-1].

L'idée du tri Shaker est simple : alterner des parcours de la gauche vers la droite avec des parcours de la droite vers la gauche. De même que le tri à bulles, si dans un parcours on ne fait aucun échange cela signifie que la liste est triée et on s'arrête.

Écrire une fonction Python nommée TriShaker(L) prenant en entrée une liste L à trier selon le principe du tri Shaker.

def triShaker (L):
    permutation ,sens ,i = True ,1 ,1
    debut ,fin = 1,len (L) -1
    while permutation == True :
        permutation = False
        while (i<fin and sens ==1) or (i> debut and sens == -1) :
            # Test si echange
            if L[i -1] > L[i]:
                permutation = True
                # On echange les deux elements
                L[i -1] ,L[i] = L[i],L[i -1]
            i = i + sens
        # On change le sens du parcours
        if sens ==1 :
            fin = fin - 1
        else :
            debut = debut + 1
        sens = -sens

Le tri par comptage

Le tri par comptage ne fonctionne que sur des entiers compris entre 0 et N, N étant connu à l'avance, contrairement aux tris précédents qui s'appliquent à tous les types de données. Il est basé sur le comptage du nombre d'occurrences des valeurs à trier.

On commence à initialiser une liste compteurs à 0. Une deuxième boucle compte les occurrences de chaque donnée à trier et range le résultat dans la liste compteurs à l'indice indiqué par l'entier à trier (étape 1). Si l'entier 12 est rencontré deux fois, la valeur 2 est rangée à la case d'indice 12 de la liste compteurs. À la fin de cette boucle, la liste compteurs contient le nombre d'occurrences pour chacun des entiers.

Une troisième boucle le transforme pour qu'il indique, pour chaque entier, l'ordre de rangement dans la liste triée (étape 2). Pour cela, chaque case de la liste compteurs est augmentée du contenu de la case précédente.

Une quatrième boucle range les entiers dans une liste temporaire selon l'ordre indiqué par compteurs (étape 3). Ainsi, l'entier 4 contenu dans la case 1 de la liste L est en troisième position (position indiquée par la case 4 de compteurs). Il doit être rangé dans la case 2 de la liste temp, pour tenir compte de la numérotation des indices commençant à 0.

Pour gérer les occurrences multiples, à chaque fois qu'un entier est rangé dans la liste triée, le contenu de la case qui lui correspond dans compteurs est diminué de 1. Ainsi, la case 4 de compteurs contenait la valeur 3 ; après le rangement de la première occurrence de la valeur 4 dans temp, elle passe à 2.

Quand l'entier 4 est de nouveau rencontré, il est rangé en deuxième position (valeur de la case 4 de compteurs), soit dans la case 1 de temp. Ainsi, tous les entiers contenus dans L sont rangés dans l'ordre dans temp, grâce à la liste compteurs. La dernière boucle recopie temp dans L.

def triComptage (L):
    n=len(L)
    temp =[0]* n
    N=max(L) # Calculer le plus grand entier de L
    compteurs =[0]*( N+1) # Initialiser compteurs par (N+1)
                         # cases tous nulles
    
    # Boucle de calcul des occurrences
    for x in L:
        compteurs [x ]+=1
    
    # Calcul des occurences cumulées
    for i in range (1,N+1):
        compteurs [i]+= compteurs [i -1]
        
    # rangement des données triées dans temp
    for x in L:
        compteurs [x] -=1
        temp [ compteurs [x]]= x
        
    # copier temp dans L
    L. clear ()
    [L. append (x) for x in temp ]

Tri par fusion

Le tri par fusion utilise le principe "diviser pour régner". L'algorithme se décrit simplement de manière récursive :

• si la liste a 0 ou 1 élément, elle est déjà triée,
• si la liste a plus d'un élément, on la partage en deux listes et on applique le tri fusion sur chacune des deux listes,
• on fusionne les résultats.

Pour fusionner deux listes triées, on compare les éléments de chacune des deux listes et on déplace le plus petit dans une nouvelle liste. Quand une des deux listes est vide, on déplace les éléments restants de la seconde liste.

def fusion (liste1 , liste2 ):
    liste =[]
    i,j=0 ,0
    while i<len( liste1 )and j<len( liste2 ):
        if liste1 [i]<= liste2 [j]:
            liste . append ( liste1 [i])
            i+=1
        else :
            liste . append ( liste2 [j])
            j+=1
    while i<len( liste1 ):
        liste . append ( liste1 [i])
        i+=1
    while j<len( liste2 ):
        liste . append ( liste2 [j])
        j+=1
    return liste

def tri_fusion ( liste ):
    if len ( liste ) <2:
        return liste [:]
    else :
        milieu =len ( liste )//2
        liste1 = tri_fusion ( liste [: milieu ])
        liste2 = tri_fusion ( liste [ milieu :])
        return fusion (liste1 , liste2 )

Tri Shell

Le tri Shell est une variante de tri par insertion, présentée par Donald L. Shell en 1959. Cet algorithme trie séparément des suites de valeurs, issues de la liste initiale des données, constituées des éléments distants les uns des autres d'un facteur h. On dit que la suite contient les h^ièmes éléments. La valeur h diminue à chaque passage de la boucle de traitement, pour produire une nouvelle suite de données. D.L. Shell propose, de manière empirique, une série d'incréments h qui évoluent selon la règle suivante :

h_n+1 = 3·h_n + 1    et    h₁ = 1

La série des valeurs de h est ordonnée en sens inverse de manière à commencer par l'inversion de données éloignées, et finir par le traitement de données adjacentes. C'est la principale qualité de ce tri.

Ainsi, au premier passage de la boucle, les données situées aux positions 0, h, h+h, ⋯ sont triées. Quand la valeur h est importante, les données sont éloignées, et la liste est triée "grossièrement". Au deuxième passage, la valeur h est plus petite, on trie des données plus proches. Au dernier passage, h vaut 1, on trie des données adjacentes. À chaque passage, on dit que la liste est h-triée. L'intérêt de cet algorithme est que chaque passage ordonne par "petites touches" la liste, ce qui diminue le nombre d'échanges pour le passage suivant.

Sur les entiers 12, 4, 11, 9, 2, 6, 5, 10, 7, 13, 18, 14, 1, 0, 3, la série des incréments h utilisée est 13, 4 et 1. La boucle utilisant le compteur i parcourt les cases situées de la valeur h jusqu'à la fin de la liste. Pour chaque case pointée par i, on regarde si son contenu peut être remonté vers le début de la liste (principe du tri par insertion), aux positions i - h, puis i - (2 × h), etc. Pour cela, on utilise un deuxième compteur j, initialisé à i, qui remonte la liste de h cases à la fois. Si la valeur contenue dans la case i est inférieure à la case j, on inverse les cases.

def triInsertion (L, h, debut ):
    for i in range (h + debut ,len(L),h):
        x = L[i]
        j = i
        while j >0 and L[j-h]>x:
            L[j]=L[j-h]
            j = j-h
        L[j]=x

def triShell (L):
    for h in [13 ,4 ,1]:
        # Pour chaque sous-liste
        for debut in range (0,h):
            # on fait un tri par insertion
            triInsertion (L,h, debut )