-
Notifications
You must be signed in to change notification settings - Fork 1
/
tris2.py
114 lines (101 loc) · 3.69 KB
/
tris2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
# coding=UTF-8
# =============================================================================
# titre :tris2.py
# description :Exemples de tris (Fusion et Rapide)
# author :Louis Marchand
# date :20150406
# version :1.0
# usage :import tris2
# notes :
# python_version :3.4.0
# =============================================================================
def fusionner(tableau1, tableau2):
"""
Effectue la fusion de tableau1 et tableau2 de manière
à retourner une liste trié contenant tous les éléments
de `tableau1' et de `tableau2'.
"""
n = len(tableau1)
m = len(tableau2)
i = 0
j = 0
resultat = []
while i < n and j < m:
if tableau1[i] <= tableau2[j]:
resultat.append(tableau1[i])
i = i + 1
else:
resultat.append(tableau2[j])
j = j + 1
while i < n:
resultat.append(tableau1[i])
i = i + 1
while j < m:
resultat.append(tableau2[j])
j = j + 1
return resultat
def tri_fusion(tableau):
"""
Effectue le tris du tableau en utilisant l'algorithme du tri fusion et
retourne le tableau trié.
"""
n = len(tableau)
resultat = []
if n <= 1:
resultat = tableau
else:
sous_tableau1 = tableau[: int(n / 2)]
sous_tableau2 = tableau[int(n / 2):]
sous_tableau_trie1 = tri_fusion(sous_tableau1)
sous_tableau_trie2 = tri_fusion(sous_tableau2)
resultat = fusionner(sous_tableau_trie1, sous_tableau_trie2)
return resultat
def choix_pivot(tableau, premier, dernier):
"""
Retourne l'index du pivot à utiliser dans `tableau' considérant
que le début du tableau à trié est à l'index `premier' et que
la fin est à l'index `dernier'
"""
return premier
def partitionner(tableau, premier, dernier, pivot):
"""
Modifier les éléments du `tableau' de manière à ce que tous les
éléments de valeur inférieurs ou égals de l'élément pivot
(`tableau[pivot]') soit avec un index inférieur à celui-ci et
les éléments de valeur supérieur aient un index supérieur. Retourne
l'index de l'élément pivot à la fin des déplacements. Les index
inférieurs à `premier' et supérieurs à `dernier' sont ignorés.
"""
element_pivot = tableau[pivot]
tableau[pivot] = tableau[dernier]
tableau[dernier] = element_pivot
j = premier
for i in range(premier, dernier):
if tableau[i] <= element_pivot:
temp = tableau[i]
tableau[i] = tableau[j]
tableau[j] = temp
j = j + 1
tableau[dernier] = tableau[j]
tableau[j] = element_pivot
return j
def tri_rapide_recursion(tableau, premier, dernier):
"""
Effectue le tris en place du `tableau' en utilisant l'algorythme du
tri rapide. Le tableau à trié ce trouve à partir de l'index
`premier' jusqu'Ã l'index dernier.
"""
if premier < dernier:
pivot = choix_pivot(tableau, premier, dernier)
pivot = partitionner(tableau, premier, dernier, pivot)
print("Liste: " + str(tableau) + " Premier: " + str(premier) +
" Dernier: " + str(dernier) + " Pivot: " + str(pivot))
tri_rapide_recursion(tableau, premier, pivot - 1)
tri_rapide_recursion(tableau, pivot + 1, dernier)
def tri_rapide(tableau):
"""
Effectue le tris en place du `tableau' en utilisant l'algorythme du
tri rapide.
"""
n = len(tableau)
tri_rapide_recursion(tableau, 0, n - 1)