#!/usr/bin/env python # coding: utf-8 #
#
TP n°12 (tris) : Éléments de correction
# ## I. Création de listes-tests et temps d'exécution #
# Exercice 1 #
# In[1]: import random as rd # In[2]: def gen(n, N): return [rd.randint(0, N) for i in range(n)] # In[3]: gen(6, 4) #
# Exercice 2 #
# In[4]: from time import process_time as toc # In[5]: ping, pong, N = 0, 1, 10**8 t1 = toc() for k in range(N): ping, pong = pong, ping t2 = toc() print(t2 - t1) # ## II. Tris en place #
# Exercice 3 : tri par sélection #
# On écrit d'abord une fonction qui détermine l'indice du minimum de la liste ```L``` à partir de l'indice ```i```: # In[6]: def minpos(L, i): j = i m = L[i] for k in range(i + 1, len(L)): if L[k] < m: j = k m = L[k] return j #
Remarque : la recherche du minimum d'une liste et de l'indice correspondant est à connaître par cœur.
# In[7]: def select(L): n = len(L) for i in range(n - 1): j = minpos(L,i) L[i], L[j] = L[j], L[i] return None #
Remarque : le principe d'utiliser une fonction à l'intérieur d'une autre est très classique en informatique, et souvent recommandé !
# In[8]: L = gen(10, 20) print(L) select(L) print(L) # In[9]: N = 10**3 Tselect = [] for p in range(1, 5): n = 10**p L = gen(n, N) t1 = toc() select(L) t2 = toc() Tselect.append(t2 - t1) print(Tselect) #
# Exercice 4 : tri par insertion #
# Là encore, on écrit une fonction auxiliaire : # In[10]: def deplacer(L, k, i): """ Déplace l'élément k de la liste L entre L[i] et L[i+1] """ elt = L.pop(k) L.insert(i + 1, elt) return None # In[11]: def insertion(L): n = len(L) for k in range(1, n): i = k - 1 elt = L[k] while i >= 0 and elt < L[i]: i -= 1 deplacer(L,k,i) return None # In[12]: L = gen(10, 20) print(L) insertion(L) print(L) # In[13]: N = 10**3 Tinsert = [] for p in range(1, 5): n = 10**p L = gen(n, N) t1 = toc() insertion(L) t2 = toc() Tinsert.append(t2 - t1) print(Tinsert) #
# Exercice 5 : tri par insertion (sans insert) #
# Pour se passer la méthode ```insert```, on effectue des affectations successives en même temps que la recherche de l'indice d'insertion : # In[14]: def insertion(L): n = len(L) for k in range(1, n): i = k elt = L[k] while i > 0 and L[i - 1] > elt: L[i] = L[i - 1] i -= 1 L[i] = elt return L # In[15]: L = gen(10, 20) print(L) insertion(L) print(L) # In[16]: N = 10**3 Tinsertion = [] for p in range(1, 5): n = 10**p L = gen(n, N) t1 = toc() insertion(L) t2 = toc() Tinsertion.append(t2 - t1) print(Tinsertion) # C'est évidemment un peu moins efficace qu'avec l'utilisation de ```insert```... # ## III. Tris récursifs #
# Exercice 6 : tri fusion #
# In[17]: def fusion(A, B): if len(A) == 0: return B elif len(B) == 0: return A elif A[0] < B[0]: return [A[0]] + fusion(A[1:], B) else: return [B[0]] + fusion(A, B[1:]) # In[18]: def tri_fusion(L): n = len(L) if n <= 1: return L else: mil = n // 2 return fusion(tri_fusion(L[:mil]), tri_fusion(L[mil:])) # In[19]: L = gen(10, 20) print(L) print(tri_fusion(L)) # In[20]: N = 10**3 Tfusion = [] for p in range(1, 4): n = 10**p L = gen(n, N) t1 = toc() tri_fusion(L) t2 = toc() Tfusion.append(t2 - t1) print(Tfusion) # L'appel de ```tri_fusion``` avec une liste de taille supérieure provoque une erreur de récursivité : trop d'appels récursifs ont été effectués, et Python arrête l'éxécution de la fonction : #

What Causes RecursionError

#

# A RecursionError in Python is caused by a function calling itself recursively without a proper base case. Python has a limit on the number of times a function can call itself recursively. This is to ensure that the function does not execute indefinitely. If this limit is exceeded by a recursive function, a RecursionError is raised. #

# In[21]: n = 10**4 N = 10**4 L = gen(n, N) tri_fusion(L) #
# Exercice 7 : tri rapide #
# In[22]: def quicksort(L): n = len(L) if n <= 1: return L else: pivot = L[0] G = [l for l in L[1:] if l <= pivot] D = [l for l in L[1:] if l > pivot] return quicksort(G) + [pivot] + quicksort(D) # Les listes par compréhension, c'est bien, mais ici ça fait parcourir 2 fois la liste ```L[1:]```. On peut l'éviter de la manière suivante : # In[23]: def quicksort(L): n = len(L) if n < 2: return L else: pivot = L[0] G, D = [], [] for elt in L[1:]: if elt > pivot: D.append(elt) else: G.append(elt) return quicksort(G) + [pivot] + quicksort(D) # In[24]: L = gen(10, 20) print(L) print(quicksort(L)) # In[25]: N = 10**3 Trapide = [] for p in range(1, 5): n = 10**p L = gen(n, N) t1 = toc() quicksort(L) t2 = toc() Trapide.append(t2 - t1) print(Trapide) #
Remarque : c'est extrêmement rapide. Une amélioration classique consiste à prendre comme pivot un élément aléatoire de la liste L.
# ## IV. Autres algorithmes de tri #
# Exercice 8 : tri par comptage #
# In[26]: def comptage(L, N): """ Les entiers de la liste L doivent être compris entre 0 et N """ n = len(L) T = (N + 1) * [0] for elt in L: T[elt] += 1 # reconstruction de la liste ordonnée : R= [] for elt in range(N+1): for j in range(T[elt]): R.append(elt) return R # On peut écrire la reconstruction de la liste ordonnée en utilisant des listes par compréhension : # In[27]: def comptage(L, N): """ Les entiers de la liste L doivent être compris entre 0 et N """ n = len(L) T = (N + 1) * [0] for elt in L: T[elt] += 1 # le retour des listes par compréhension !! L = [[elt] * T[elt] for elt in range(N + 1) if T[elt] > 0] return [j for elt in L for j in elt] # In[28]: L = gen(10, 20) print(L) print(comptage(L,20)) # In[29]: N = 10**3 Tcomptage = [] for p in range(1, 4): n = 10**p L = gen(n, N) t1 = toc() for k in range(N): comptage(L,N) t2 = toc() Tcomptage.append(t2 - t1) print(Tcomptage) #
# Exercice 9 : tri bulle #
# In[30]: def bulle(L): for i in range(len(L) - 1, 0, -1): for j in range(i): if L[j+1] < L[j]: L[j], L[j + 1] = L[j + 1], L[j] return None # In[31]: L = gen(10, 20) print(L) bulle(L) print(L) # In[32]: N = 10**3 Tbulle = [] for p in range(1, 5): n = 10**p L = gen(n, N) t1 = toc() bulle(L) t2 = toc() Tbulle.append(t2 - t1) print(Tbulle) #
# Exercice 10 : tri par paquets #
# In[33]: def paquets(L): """ L est une liste de flottants compris entre 0 et 1 """ n = len(L) P = [[] for k in range(n)] # les paquets for elt in L: k = int(n * elt) # la partie entière P[k].append(elt) for k in range(n): insertion(P[k]) # on trie le paquet return [j for elt in P for j in elt] # In[34]: n = 10 L = [rd.random() for i in range(n)] print(paquets(L)) # Dans le cas où la liste $L$ est constituée de flottants compris de $[a,b[$, on peut procéder ainsi : # # # - Créer $n$ listes $P_0, \ldots, P_{n-1}$ appelées paquets. Le paquet $P_k$ est associé à l'intervalle $I_k=\left[a+k(b-a) / n, a+(k+1)(b-a) / n\right[$. # - Pour chaque élément $L[i]$ : # - Calculer l'intervalle $I_k$ dans lequel il se trouve : $k=\left\lfloor n(L[i]-a) /(b-a)\right\rfloor$ # - Ajouter $L[i]$ à $P_k$. # - Trier chaque liste $P_k$, par exemple avec un tri par insertion. # - Renvoyer la concaténation des listes $P_0, \ldots, P_{n-1}$.