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
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__))
Mon problème est le suivant :
  • 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 ?