123 lines
2.7 KiB
Python
123 lines
2.7 KiB
Python
import numpy as np
|
|
import matplotlib.pyplot as plt
|
|
import matplotlib.animation as animation
|
|
import matplotlib.colors as colors
|
|
import time
|
|
def p(e):
|
|
print(e)
|
|
return e
|
|
|
|
def alealiste(n,M):
|
|
return np.array(np.random.random((n,))*M,dtype=int)
|
|
|
|
def ytrinsertion(L):
|
|
if len(L)<=1:
|
|
return L
|
|
out = np.empty((len(L),),dtype=int)
|
|
out[0] = L[0]
|
|
out[1:] = yield from ytrinsertion(L[1:])
|
|
for i in range(len(out)-1):
|
|
if out[i+1]>=L[0]:
|
|
out[i]=L[0]
|
|
return out
|
|
out[i] = out[i+1]
|
|
out[i+1] = L[0]
|
|
yield out
|
|
out[-1]=L[0]
|
|
yield out
|
|
|
|
def triRapideEnPlace(l,a=None,b=None):
|
|
"""
|
|
Trie la liste l entre a et b
|
|
"""
|
|
if a==None: a = 0
|
|
if b==None: b = len(l)
|
|
|
|
if b-a==0:
|
|
return l
|
|
if b-a==1:
|
|
return l
|
|
n = a+(b-a)//2
|
|
pivot = l[n]
|
|
i = n
|
|
maxindex = b
|
|
minindex = a
|
|
while maxindex != minindex:
|
|
# On souhaite ranger l'élément i dans la bonne moitié
|
|
# On suppose que i n'est pas dans les parties rangées
|
|
if l[i] < pivot or (l[i]==pivot and np.random.randint(0,2)==1):
|
|
l[i],l[minindex] = l[minindex],l[i]
|
|
minindex += 1
|
|
else:
|
|
l[i],l[maxindex-1] = l[maxindex-1],l[i]
|
|
maxindex -= 1
|
|
yield l
|
|
# On prend un i pas dans les parties triées
|
|
i = (maxindex-minindex)//2 + minindex
|
|
yield from triRapideEnPlace(l,a,maxindex)
|
|
yield from triRapideEnPlace(l,maxindex,b)
|
|
|
|
|
|
def triFusionRec(l,index):
|
|
if len(l)==0:
|
|
return l
|
|
if len(l)==1:
|
|
return l
|
|
n = len(l)//2
|
|
l1,l2 = triFusionRec(l[:n],0),triFusionRec(l[n:],n)
|
|
out = []
|
|
i,j = 0,0
|
|
while i<len(l1) or j<len(l2):
|
|
if j>=len(l2) or (i<len(l1) and l1[i]<=l2[j]):
|
|
out.append(l1[i])
|
|
i+=1
|
|
else:
|
|
out.append(l2[j])
|
|
j+=1
|
|
V[index:index+len(out+l1[i:]+l2[j:])] = np.array(out+l1[i:]+l2[j:])
|
|
print(V)
|
|
update()
|
|
return out
|
|
|
|
def update():
|
|
time.sleep(1)
|
|
|
|
N = 100
|
|
v = 100
|
|
X = np.linspace(0,N-1,N,dtype=int)
|
|
L = np.arange(N)
|
|
np.random.shuffle(L)
|
|
|
|
|
|
|
|
fig=plt.figure()
|
|
|
|
#trieur = triFusionRec(L)
|
|
V = L.copy()
|
|
barcollection = plt.bar(X,L,width=1.0)
|
|
|
|
def animate(i):
|
|
y = V
|
|
for i, b in enumerate(barcollection):
|
|
b.set_height(y[i])
|
|
b.set_color(colors.hsv_to_rgb((y[i]/v,1.0,1.0)))
|
|
|
|
import threading
|
|
class Foo (threading.Thread):
|
|
def __init__(self):
|
|
threading.Thread.__init__(self)
|
|
def run (self):
|
|
ytrinsertion(V,0)
|
|
|
|
Foo().start()
|
|
|
|
anim=animation.FuncAnimation(fig,animate,repeat=False,blit=False, interval=1)
|
|
|
|
plt.show()
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|