forked from menault/TD4_DEV51_Qualite_Algo
64 lines
1.8 KiB
Python
64 lines
1.8 KiB
Python
|
|
||
|
|
def Trie_Tableau_Double(tab) : # complexitée O(n(m²+n))
|
||
|
|
sorted_dico = {}
|
||
|
|
|
||
|
|
print(tab[0])
|
||
|
|
|
||
|
|
# n^(m+m*((m(m+1))/2))+n((m(m+1))/2)
|
||
|
|
|
||
|
|
for sub_tab in tab : # n
|
||
|
|
val = 0
|
||
|
|
sub_tab2 = []
|
||
|
|
for elt in sub_tab : # m
|
||
|
|
val += elt
|
||
|
|
|
||
|
|
for i in range(len(sub_tab)): # m
|
||
|
|
if i == 0 :
|
||
|
|
sub_tab2.append(sub_tab[i])
|
||
|
|
else :
|
||
|
|
for j in range(len(sub_tab2)+1): # (m(m+1))/2
|
||
|
|
if j >= len(sub_tab2):
|
||
|
|
sub_tab2.append(sub_tab[i])
|
||
|
|
else :
|
||
|
|
if sub_tab[i] <= sub_tab2[j] :
|
||
|
|
sub_tab2.insert(j,sub_tab[i])
|
||
|
|
break
|
||
|
|
|
||
|
|
sorted_dico[val] = sub_tab2
|
||
|
|
|
||
|
|
tab = []
|
||
|
|
index_tab = []
|
||
|
|
|
||
|
|
# n*(m(m+1))/2
|
||
|
|
|
||
|
|
for clef,valeur in sorted_dico.items() : # n
|
||
|
|
if index_tab == [] :
|
||
|
|
tab.append(valeur)
|
||
|
|
index_tab.append(clef)
|
||
|
|
else :
|
||
|
|
for j in range(len(index_tab)+1): # (m(m+1))/2
|
||
|
|
if j >= len(index_tab):
|
||
|
|
tab.append(valeur)
|
||
|
|
index_tab.append(clef)
|
||
|
|
else :
|
||
|
|
if clef <= index_tab[j] :
|
||
|
|
tab.insert(j,valeur)
|
||
|
|
index_tab.insert(j,clef)
|
||
|
|
break
|
||
|
|
|
||
|
|
return tab
|
||
|
|
|
||
|
|
|
||
|
|
def Trie_Tableau_Double_bySort(tab) : # complexitée O(n*m * log(m))
|
||
|
|
|
||
|
|
tab.sort() # n log(n)
|
||
|
|
|
||
|
|
for sub_tab in tab : # n
|
||
|
|
sub_tab.sort() # m log(m)
|
||
|
|
|
||
|
|
return tab
|
||
|
|
|
||
|
|
|
||
|
|
Tableau_test = [[0,3,2], [9,4,5], [4,1,3]]
|
||
|
|
|
||
|
|
print(Trie_Tableau_Double(Tableau_test))
|