#!/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}$.