108 lines
2.0 KiB
Python
108 lines
2.0 KiB
Python
|
#!/usr/bin/env python3
|
||
|
|
import random
|
||
|
|
|
||
|
|
|
||
|
|
def tab_alea(n, mini=0, maxi=1e6):
|
||
|
|
return [random.randint(mini, maxi) for _ in range(n)]
|
||
|
|
|
||
|
|
|
||
|
|
def tri_bulle(l):
|
||
|
|
t = l[::]
|
||
|
|
perm = True
|
||
|
|
n = len(t)
|
||
|
|
while perm:
|
||
|
|
perm = False
|
||
|
|
for j in range(0, n-1):
|
||
|
|
if t[j] > t[j+1]:
|
||
|
|
t[j], t[j+1] = t[j+1], t[j]
|
||
|
|
perm = True
|
||
|
|
return t
|
||
|
|
|
||
|
|
|
||
|
|
def indice_mini(m, i, j):
|
||
|
|
im = i
|
||
|
|
for k in range(i, j):
|
||
|
|
if m[k] < m[im]:
|
||
|
|
im = k
|
||
|
|
return im
|
||
|
|
|
||
|
|
|
||
|
|
def tri_selection(l):
|
||
|
|
t = l[::]
|
||
|
|
n = len(t)
|
||
|
|
for i in range(n):
|
||
|
|
im = indice_mini(t, i, n)
|
||
|
|
t[i], t[im] = t[im], t[i]
|
||
|
|
return t
|
||
|
|
|
||
|
|
|
||
|
|
def place(x, m):
|
||
|
|
ind = 0
|
||
|
|
n = len(m)
|
||
|
|
while ind<n and x>m[ind]:
|
||
|
|
ind += 1
|
||
|
|
return ind
|
||
|
|
|
||
|
|
|
||
|
|
def tri_insertion(l):
|
||
|
|
t = l[::]
|
||
|
|
n = len(t)
|
||
|
|
triee = []
|
||
|
|
for i in range(0, n):
|
||
|
|
k = place(t[i], triee)
|
||
|
|
triee = triee[:k] + [t[i]] + triee[k:]
|
||
|
|
return triee
|
||
|
|
|
||
|
|
def tri_insertion_en_place(l):
|
||
|
|
t = l[::]
|
||
|
|
n = len(t)
|
||
|
|
for i in range(0, n):
|
||
|
|
k = 0
|
||
|
|
while k<i and t[i]>t[k]:
|
||
|
|
k+=1
|
||
|
|
for j in range(i-1, k-1, -1):
|
||
|
|
t[j+1], t[j] = t[j], t[j+1]
|
||
|
|
return t
|
||
|
|
|
||
|
|
|
||
|
|
def fusionne(t1, t2):
|
||
|
|
w = []
|
||
|
|
n1 = len(t1)
|
||
|
|
n2 = len(t2)
|
||
|
|
ind1 = ind2 = 0
|
||
|
|
while ind1 < n1 and ind2 < n2:
|
||
|
|
if t1[ind1] < t2[ind2]:
|
||
|
|
w.append(t1[ind1])
|
||
|
|
ind1 += 1
|
||
|
|
else:
|
||
|
|
w.append(t2[ind2])
|
||
|
|
ind2 +=1
|
||
|
|
for el in t1[ind1:]+t2[ind2:]:
|
||
|
|
w.append(el)
|
||
|
|
return w
|
||
|
|
|
||
|
|
def tri_fusion(t):
|
||
|
|
n = len(t)
|
||
|
|
if n <= 1:
|
||
|
|
return t
|
||
|
|
else:
|
||
|
|
return fusionne(tri_fusion(t[:n//2]), tri_fusion(t[n//2:]))
|
||
|
|
|
||
|
|
def quicksort(t):
|
||
|
|
n = len(t)
|
||
|
|
if n <= 1:
|
||
|
|
return t
|
||
|
|
else:
|
||
|
|
pivot = t[0]
|
||
|
|
tg, t_pivots, td = [], [], []
|
||
|
|
for i in range(n):
|
||
|
|
if t[i] < pivot:
|
||
|
|
tg.append(t[i])
|
||
|
|
elif t[i] == pivot:
|
||
|
|
t_pivots.append(t[i])
|
||
|
|
else:
|
||
|
|
td.append(t[i])
|
||
|
|
return quicksort(tg) + t_pivots + quicksort(td)
|
||
|
|
|
||
|
|
|