TP : algorithmique, tris, complexité algorithmique

Parcours séquentiel d’une liste

On utilise un algorithme qui permet de retrouver la valeur maximale au sein d’une liste. Cette dernière est non triée. On effectue la mesure du temps qu’il met pour trouver le maximum au sein d’une liste de 10 000 éléments. Combien lui faudra-t-il pour une liste de 20 000 valeurs ?

1. Le même temps si le maximum se trouve dans la première moitié de la liste.

2. Avec 10 000 valeurs en plus, l’algorithme mettra 10 000 fois plus de temps pour s’exécuter.

3. Le temps d’exécution doublera.

4. Il est difficile de savoir où se trouve le maximum donc difficile d’estimer le temps d’exécution.
   Réponse : 3

Recherche dichotomique

Lorsque l’on compare la recherche séquentielle (RS) d’un élément dans une liste à la recherche dichotomique (RD) dans une liste triée, on observe que :

1. La RD est toujours plus rapide

2. La RD est en moyenne plus rapide

3. La RD ne donne pas toujours le bon résultat
   Réponse : 2

Algorithmes de tri

1. Quel est le coût en temps dans le pire cas du tri par insertion ?
   O(n²)
   complexité quadratique
   si double taille données je multiplie par 4 le temps d'exécution.

2. Quel est le coût en temps dans le pire cas du tri par sélection (pour une liste de taille n) ?
   O(n²) quadratique

3. QU’est-ce qu’un tri stable ?
   Un tri stable conserve l'ordre d'apparition des éléments égaux.

4. Lequel des deux algorithmes suivants est considéré comme un tri stable :

a. Le tri par insertion

b. Le tri par sélection
Réponse : a

Rechercher un élément dans une liste

1. Implémenter la fonction trouve(liste,X) qui renvoie vrai si l’élément X se trouve dans la liste liste ou faux sinon.

def trouve(liste, x):
    for i in range(len(liste)):
        if liste[i]==x:
            return("vrai")
    return("faux")
print(trouve([1,2,3,4,5],8))

2. Proposer un jeu de données pour tester cette fonction. Justifier votre choix.
   Exemples :
   si : trouve([1,2,3,4,5],8) ; renvoie : "faux"
   si : trouve([1,2,3,4,5],3) ; renvoie : "vrai"

Vérifier qu’une liste est triée

1. Implémenter la fonction liste_triee(liste) qui renvoie vrai ou faux selon que la liste est triée par ordre croissant ou décroissant.

def liste_triee(liste):
    a=0
    b=0
    for i in range(len(liste)-1):
        if liste[i]<=liste[i+1]:
            a=a+1
        elif liste[i]>=liste[i+1]:
            b=b+1
    if a==len(liste)-1:
        return("croissant")
    elif b==len(liste)-1:
        return("décroissante")
    else:
        return("ni croissante ni décroissante")
print(liste_triee([5,4,3,2,1]))
print(liste_triee([1,2,3,4,5]))

2. Proposer un jeu de données pour tester cette fonction. Justifier votre choix.
   si : liste_triee([5,4,3,2,1] ; renvoie : "décroissante"
   si : liste_triee([1,2,3,4,5] ; renvoie : "croissante"
   si : liste_triee([5,2,3,2,4] ; renvoie : "ni croissante ni décroissante"

Calcul de la médiane au sein d’une liste triée

1. Définir ce qu’est une médiane
   La médiane est la valeur qui sépare la moitié inférieure de la moitié supérieure d'un ensemble
2. Implémenter la fonction mediane(liste) qui renvoie la médiane d’une liste triée.

def mediane(liste):
    mediane=0
    if (len(liste))%2==0:
        a=liste[int((len(liste))/2)]
        b=liste[int((len(liste)/2)-1)]
        mediane=(a+b)/2
    elif (len(liste))%2!=0:
        mediane=liste[int((len(liste))/2)]
    return(mediane)
print(mediane([1,2,3,4,5,6,7,8]))

3. Proposer un jeu de données pour tester cette fonction. Justifier votre choix.
   si : mediane([1,2,3,4,5,6,7,8]) ; renvoie : "4.5"
   si : mediane([1,5,9,20]) ; renvoie : "7.0"

Recherche dichotomique au sein d’une liste triée

1. Implémenter une fonction trouver_dichotomique(liste, X) qui permet de chercher X au sein d’une liste triée.

def dichotomie(liste, v):
    a = 0
    b = len(liste) - 1
    while a <= b:
        m = (a + b) // 2
        if liste[m] == v:
            return True
        elif liste[m] < v:
            a = m + 1
        else:
            b = m - 1
    return False
print(dichotomie([1,2,3,4,5,6],4))

2. Proposer un jeu de données pour tester cette fonction.
   si : dichotomie([1,2,3,4,5,6],4) ; renvoie : "true"
   si : dichotomie([1,2,3,4,5,6],64) ; renvoie : "false"
   si : dichotomie([1,2,3,4,5,6],2) ; renvoie : "true"

Évaluer le nombre de valeurs à déplacer lors de l’exécution d’une fonction de tri

1. Effectuer une recherche pour trouver un exemple de tri par sélection.

def tri_selection(tab):
   for i in range(len(tab)):
      # Trouver le min
       min = i
       for j in range(i+1, len(tab)):
           if tab[min] > tab[j]:
               min = j
                
       tmp = tab[i]
       tab[i] = tab[min]
       tab[min] = tmp
   return tab

2. Déterminer, pour liste de taille n, le nombre de déplacements ou de permutations à effectuer pour trier toute la liste.
   Pour une liste de taille n le nombre de permutations est de 3n complexité linéaire.

3. Réaliser le même travail pour le tri par insertion.

def sort_numbers(s):
    for i in range(1, len(s)):
        val = s[i]
        j = i - 1
        while (j >= 0) and (s[j] > val):
            s[j+1] = s[j]
            j = j - 1
        s[j+1] = val

def main():
    x = eval(input("Enter numbers to be sorted: "))
    x = list(x)
    sort_numbers(x)
    print(x)

Le nombre de permutations est de n².
4. Comparer les deux algorithmes de tri.
Le tri par insertion est plus long que le premier et fait beaucoup plus de permutations prenant ainsi beaucoup plus d'espace.