# -*- coding: utf-8 *-* ############################################################################### # Tri sélection ############################################################################### def bad_sort(l): """ Très mauvais algorithme de tri (en place) : quadratique dans tous les cas """ for i in range(0, len(l)): i_min = i for j in range(i+1, len(l)): if l[j] < l[i_min]: i_min = j (l[i], l[i_min]) = (l[i_min], l[i]) ############################################################################### # Tri à bulles ############################################################################### 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 fusion ############################################################################### def fusion(l): """ Tri fusion : nlog n dans tous les cas """ if len(l) <= 1: return l else: middle = len(l)/2 # On trie les deux moitiés de la liste l1 = fusion(l[0:middle]) l2 = fusion(l[middle:]) # Et on fusionne return merge(l1, l2) def merge(l1, l2): """ Fusion de deux listes triées """ # Préallocation de la liste fusionnée merged = [None] * (len(l1)+len(l2)) i = 0 # indice dans la liste l1 j = 0 # indice dans la liste l2 k = 0 # indice dans la liste fusionnée while i < len(l1) and j < len(l2): if l1[i] < l2[j]: merged[k] = l1[i] i += 1 else: merged[k] = l2[j] j += 1 k += 1 if i < len(l1): while i < len(l1): merged[k] = l1[i] i += 1 k += 1 else: while j < len(l2): merged[k] = l2[j] j += 1 k += 1 return l ############################################################################### # Tri rapide ############################################################################### def quicksort(table): """ Tri rapide: nlog n en moyenne, quadratique dans le cas le pire. Tri en place: c'est le tableau table passé en argument qui est trié et retourné. """ do_quicksort(table, 0, len(table)-1) return table 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 = first 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 ############################################################################### # Temps d'exécution ############################################################################### # Fonction qui prend en argument une fonction de tri (paramètre sort) 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 # Temps consacré au tirage d'une liste au hasard sort_time = 0 # Temps de tri (fonction sort()) while count < num_iter: # D'abord on tire une liste au hasard 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 # Ensuite on la tri before_sort = time.time() sort(test_list) after_sort = time.time() sort_time += after_sort - before_sort count += 1 # Toutes les 100 itérations on affiche un petit compte-rendu if count % 100 == 0: print "random = %.4f, sort = %.4f" % (random_time, sort_time) return (random_time, sort_time)