############################################################################### # Tri par insertion : temps quadratique dans tous les cas sauf ceux vraiment # favorables ############################################################################### def insertion(table): for i in range(0, len(table)): # Invariant de boucle : les cellules avant i sont triées, il s'agit # maintenant d'insérer table[i] à sa place t_i = table[i] j = i-1 while j >= 0 and table[j] > t_i: # Invariant de boucle : les cellules après j sont triées et plus # grandes que t_i table[j+1] = table[j] j -= 1 table[j+1] = t_i return table ############################################################################### # Tri par sélection : temps quadratique dans tous les cas ############################################################################### def selection(table): for i in range(0, len(table)-1): # Invariant de boucle : les cellules avant i sont triées et contiennent # les i plus petits éléments de table for j in range(i+1, len(table)): # Invariant de boucle : table[i] contient le plus petit élément des # cellules comprises entre i (inclus) et j (exclus) if table[j] < table[i]: table[i], table[j] = table[j], table[i] return table ############################################################################### # Tri à bulle : quadratique dans le cas le pire ############################################################################### def bubble(table): last = len(table)-1 while last > 0: # invariant de boucle : toutes les cellules après last (exclus) sont # déjà triées et contiennent les n - last plus grands éléments de table bubble = 0 for i in range(0, last): # invariant de boucle : table[i] contient le plus grand élément de # toutes les cellules avant i ; bubble contient la dernière bulle, # c'est à dire la dernière cellule que l'on a modifiée if table[i] > table[i+1]: table[i], table[i+1] = table[i+1], table[i] bubble = i+1 last = bubble return table ############################################################################### # Tri rapide : quasilinéaire en moyenne, quadratique dans le cas le pire ############################################################################### def quicksort(table): # Fonctions auxilliaires (le programme est après les définitions de # fonctions auxiliaires) def do_quicksort(table, first, last): """La fonction principale de tri : implémente la stratégie divide and conquer""" # print("---->", first, last, table[first:last+1]) pivot = choose_pivot(table, first, last) pivot = partition(table, first, last, pivot) # print(pivot, "<--", first, last, table[first:last+1]) if first < pivot-1: do_quicksort(table, first, pivot-1) if pivot+1 < last: do_quicksort(table, pivot+1, last) def partition(table, first, last, pivot): """Partitionne table en mettant au début les éléments < table[pivot], à la fin ceux >= table[pivot] et enfin table[pivot] entre les deux ; retourne la nouvelle position du pivot""" # On commence par mettre le pivot dans la première cellule table[first], table[pivot] = table[pivot], table[first] i, j = first+1, last if i > j: # first+1 > last : cette table a un seul élément return first elif i == j: # first+1 == last : cette table a deux éléments if table[i] < table[first]: table[first], table[i] = table[i], table[first] return i else: return first # Si on arrive ici c'est que i < j ; on fait une boucle a priori # infinie mais heureusement des sorties (par appel à return) sont # prévues dans le corps de boucle while True: # Invariant de boucle : les cellules avant i (exclus) contiennent # des valeurs <= table[first] et table[first] est le plus grand # d'entre eux ; les cellules après j (exclus) contiennent des # valeurs >= table[first] # On va au premier élément après i (inclus) qui est > table[first], # mais attention à ne pas dépasser j while table[i] <= table[first]: # Invariant de boucle : toutes les cellules avant i (inclus) # ont des valeurs <= table[first] i = i+1 if i == j: if table[i] > table[first]: i = i-1 table[first], table[i] = table[i], table[first] return i # Si on arrive ici c'est que on a encore i < j : on va au premier # élément avant j (inclus) qui est < j, mais attention à ne pas # passer avant i while table[j] >= table[first]: # Invariant de boucle : toutes les cellules après j (inclus) # ont des valeurs >= table[first] j = j-1 if i == j: table[first], table[i-1] = table[i-1], table[first] return i-1 # Si on arrive ici alors on a : i < j ; tous les éléments avant i # (exclus) sont <= table[first] mais table[i] > table[first] ; tous # les éléments après j (exclus) sont >= table[first] mais table[j] # < table[first]. table[i], table[j] = table[j], table[i] i, j = i+1, j-1 # Vérification que i et j ne se sont pas croisés if i > j: table[first], table[i-1] = table[i-1], table[first] return i-1 elif i == j: if table[i] > table[first]: i = i-1 table[first], table[i] = table[i], table[first] return i def choose_pivot(table, first, last): """Choix du pivot""" # On se contente de retourner la première cellule return first # Lancement du programme do_quicksort(table, 0, len(table)-1) return table ############################################################################### # Tri fusion : quasilinéaire mais contrairement aux précédents il ne s'agit pas # d'un tri "en place" c'est à dire que les éléments triés sont placés dans une # nouvelle liste, le tableau original n'est pas modifié ############################################################################### def fusion(table): # fonction principale : encore une fois on fait du divide and conquer def do_fusion(table, first, length): if length <= 1: return table[first:first+length] else: half = length//2 table1 = do_fusion(table, first, half) table2 = do_fusion(table, first+half, length-half) return merge(table1, table2) def merge(table1, table2): """table1 et table2 sont des tablees triées : retourne une nouvelle table contenant les éléments de table1 et table2 dans l'ordre""" len1 = len(table1) len2 = len(table2) i = j = 0 table = [] while True: # invariant de boucle : i < len1, j < len2, les éléments de table1 # avant i et les éléments de table2 avant j sont triés dans table if table1[i] <= table2[j]: table.append(table1[i]) i = i+1 if i == len1: # On est au bout de table1 ; on copie la fin de table2 dans # table while j < len2: table.append(table2[j]) j = j+1 return table else: table.append(table2[j]) j = j+1 if j == len2: # On est au bout de table2 ; on copie la fin de table1 dans # table while i < len1: table.append(table1[i]) i = i+1 return table return do_fusion(table, 0, len(table)) def benchmarks(sort, list_size, num_iter = 10000): import time import random print("list size = ", list_size) test_list = [None] * list_size count = 0 random_time = 0 sort_time = 0 while count < num_iter: before_random = time.time() for i in range(0, list_size): test_list[i] = random.randint(0, 100) after_random = time.time() random_time += after_random - before_random before_sort = time.time() sort(test_list) after_sort = time.time() sort_time += after_sort - before_sort count += 1 if count % 100 == 0: print("random = %.4f, sort = %.4f" % (random_time, sort_time)) return (random_time, sort_time)