Bonjour à toute et à tous,
j'ai écrit un script qui donne le temps que mettent deux algorithmes de tri (à savoir le tri à bulle et le tri rapide) pour trier une liste.
La liste (générée aléatoirement) contient 20 000 entiers et se trouve dans le fichier donnee.py donnees.py.zip
Mon problème est le suivant :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 import time from donnee import * def quick_sort(liste): if len(liste) <= 1: return liste else: i = 1; j = len(liste) - 1 while i < j: while i < j and liste[i] <= liste[0]: i += 1 while i < j and liste[j] >= liste[0]: j -= 1 if i-j != 0: liste[i],liste[j] = liste[j],liste[i] i += 1; j -= 1 if liste[i] <= liste[0]: return quick_sort(liste[1:i+1])+[liste[0]]+ quick_sort(liste[i+1:len(liste)]) else: return quick_sort(liste[1:i])+[liste[0]]+ quick_sort(liste[i:len(liste)]) def tri_a_bulle(liste): permutation = True while permutation == True: permutation = False for i in range(0,len(liste)-1): if liste[i] > liste[i+1]: liste[i],liste[i+1] = liste[i+1],liste[i] permutation = True return liste T = [quick_sort,tri_a_bulle] for func in T: debut = time.time() func(liste) fin= time.time() print("{} secondes pour la fonction {}".format(fin-debut,func.__name__))
- Si dans le code ci-dessus je remplace T = [quick_sort,tri_a_bulle] par T = [tri_a_bulle] (càd si je veux juste le temps mis par le tri_a_bulle), il me renvoie un temps de 14s
- Si je laisse T = [quick_sort,tri_a_bulle], il me renvoie un temps de 0.03s pour le tri rapide et de 9s pour le tri à bulle !! (le tri à bulle est accéléré )
- Si je remplace T = [quick_sort,tri_a_bulle] par T = [tri_a_bulle, quick_sort], le temps renvoyé pour le tri à bulle est de 14s mais le programme plante pour le quicksort et renvoie un "RuntimeError: maximum recursion depth exceeded in comparison" (le tri rapide est un algorithme récursif)
Pourquoi le comportement des deux fonctions change-t-il suivant l'ordre d'appel ? il n'y a à priori aucune intéraction entre les deux.
J'ai bien sur essayé avec d'autres listes générées aléatoirements. Le problème de dépassement de pile se pose d'ailleurs à partir d'une taille de liste de 1000 éléments, alors que lancé tout seul, le quick_sort supporte aisément des listes à 1 000 000 d'entrée !
Quelqu'un pourrait m'éclairer ?
Partager