Tri insertion

In [7]:
#entrée : un tableau T
#sortie : permutation triée de T (en place)
#algo en O(|T|^2)
def triInsertion(T):
    
    #entrée : un tableau T avec T[0, ..., i-1] trié
    #sortie : le tableau T est tq T[0, ..., i] contienne les même éléments mais est trié ; T[i+1, ...] est inchangé.
    def inserer(T, i):
        j = i
        while j>0 and T[j-1]>T[j]:
            T[j-1],T[j] = T[j],T[j-1]
            j = j-1

    for i in range(len(T)):
        inserer(T, i)
    return T
In [8]:
import random

#entrée : un entier n
#sortie : un tableau de taille n de nombres aléatoires
def genererTableauAleatoire(n):
    return [random.randint(1,10000) for i in range(n)]
In [13]:
triInsertion( genererTableauAleatoire(10) )
Out[13]:
[941, 1141, 1215, 2166, 2365, 2863, 4382, 4510, 4547, 7713]

Tri fusion

In [9]:
#entrée : un tableau T
#sortie : permutation triée de T
#algorithme du tri fusion concis, mais inefficace à cause des recopies de tableaux
def triFusion(T):
    def fusion(A, B):
        if len(A) == 0: return B
        if len(B) == 0: return A
        if A[0] < B[0]:
            return [A[0]] + fusion(A[1:], B)
        else:
            return [B[0]] + fusion(A, B[1:])
        
    if len(T) <= 1:
        return T
    else:
        m = len(T) // 2
        return fusion(triFusion(T[:m]), triFusion(T[m:]))
In [14]:
triFusion( genererTableauAleatoire(10) )
Out[14]:
[52, 462, 2458, 3479, 4094, 4356, 4436, 6692, 7638, 9236]
In [10]:
#entrée : un tableau T
#sortie : permutation triée de T
#algorithme du tri fusion en O(|T| log |T|)
def triFusion2(T):
    #entrée : tableaux A et B, un tableau T de taille |A| + |B|
    #sortie : T est trié et contient maintenant les éléments de A et B (en place pour T)
    #complexité en O(|T|)
    def fusion(T, A, B):
        i = 0
        j = 0
        k = 0
        while i < len(A) and j < len(B):
            if A[i] < B[j]:
                T[k] = A[i]
                i = i + 1
            else:
                T[k] = B[j]
                j = j + 1
            k = k + 1
 
        while i < len(A):
            T[k] = A[i]
            i = i + 1
            k = k + 1
 
        while j < len(B):
            T[k] = B[j]
            j = j + 1
            k = k + 1
        
    if len(T) <= 1:
        return T
    else:
        m = len(T) // 2
        fusion(T, triFusion2(T[:m]), triFusion2(T[m:]))
        return T
In [ ]:
triFusion2( genererTableauAleatoire(100) )