/
Tri insertion1.ipynb.txt
195 lines (195 loc) · 6.21 KB
/
Tri insertion1.ipynb.txt
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"name": "Copie de Bienvenue dans Colaboratory",
"provenance": [],
"collapsed_sections": []
},
"kernelspec": {
"display_name": "Python 3",
"name": "python3"
}
},
"cells": [
{
"cell_type": "markdown",
"metadata": {
"colab_type": "text",
"id": "5fCEDCU_qrC0"
},
"source": [
"#Algorithmes de tris :\n",
"Étant donné une liste d’entiers, il faut la trier dans l’ordre croissant.On peut bien entendu l’étendre à autre chose que des entiers...Bien que les listes aient une méthode prédéfinie pour trier (ma_liste.sort()), il est intéressant de faire soit même des algorithmes de tris.<BR>\n",
"Exemples de tris:<BR>\n",
"[Simulation de différents tris](https://isn-icn-ljm.pagesperso-orange.fr/tri2/index.html)\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"colab_type": "text",
"id": "GJBs_flRovLc"
},
"source": [
"## <strong>Tri insertion</strong>\n",
"\n"
]
},
{
"cell_type": "code",
"metadata": {
"colab_type": "code",
"id": "gJr_9dXGpJ05",
"outputId": "d2b18238-1a61-41c3-d978-92342b57a60b",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 336
}
},
"source": [
"%%html\n",
"<iframe width=\"560\" height=\"315\" src=\"https://www.youtube.com/embed/ROalU379l3U\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen></iframe>"
],
"execution_count": 0,
"outputs": [
{
"output_type": "display_data",
"data": {
"text/html": [
"<iframe width=\"560\" height=\"315\" src=\"https://www.youtube.com/embed/ROalU379l3U\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen></iframe>"
],
"text/plain": [
"<IPython.core.display.HTML object>"
]
},
"metadata": {
"tags": []
}
}
]
},
{
"cell_type": "markdown",
"metadata": {
"colab_type": "text",
"id": "2fhs6GZ4qFMx"
},
"source": [
"Exercice 1: double cliquer dans la cellule et complétez:\n",
"_________________________\n",
"\n",
"Compléter le texte.Au début on compare le ..... et le ..... en les ....................... si ..........................Puis on compare le ...... avec le ...... en les échangeant si c’est nécessaire, si l’échange aeu lieu on compare le ...... avec le ...... en les échangeant si nécessaireEt ainsi de suite.Au bout d’un certain ’temps’ on considère lekèmeélément de la liste, il faut le compareret l’échanger avec ses prédécesseurs tant qu’..............................................................................."
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "dQ2s3_3WXBqN",
"colab_type": "text"
},
"source": [
"Algorithme en langage pseudo-naturel:\n",
"_____________________________________________________________________\n",
"\n",
"fonction tri_insertion(L) <br>\n",
"Données :<br>\n",
"L←liste d’entiers<br>\n",
"n←taille de la liste<br>\n",
"Pourk allant de 1 à n-1faire<br>\n",
" j←k<br>\n",
" Tant que<br>\n",
" j > 0 et L[j-1] > L[j]faire<br>\n",
" On échange L[j-1] et L[j]<br>\n",
" j←j−1<br>\n",
"retourner L"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "3xCzL8IgX89H",
"colab_type": "text"
},
"source": [
"Exercice 2: double-cliquez dans la cellule pour répondre<BR>\n",
"_______\n",
"Pourquoi : Pour k allant de 1 à n−1?\n",
"<BR><BR><BR><BR>"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "xVKJJUbdYoo7",
"colab_type": "text"
},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "G4Tr2DA1YaOl",
"colab_type": "text"
},
"source": [
"Exercice 3: double cliquez dans la cellule pour répondre:\n",
"_______\n",
"Étudier la terminaison de cet algorithmeBoucle bornée :. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Boucle tant que : Variant de boucle :....... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . "
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "eJbtWTCKXvRx",
"colab_type": "text"
},
"source": [
"Exercice 4:\n",
"____\n",
"Utilisez la cellule de code ci-dessous pour tapez la fonction tri_insertion en Python"
]
},
{
"cell_type": "code",
"metadata": {
"id": "Rf2b7fjQXufL",
"colab_type": "code",
"colab": {}
},
"source": [
""
],
"execution_count": 0,
"outputs": []
},
{
"cell_type": "markdown",
"metadata": {
"id": "Az7jBB09YqnV",
"colab_type": "text"
},
"source": [
"Exercice 5 : \n",
"___\n",
"Modifier le programme précédent, pour qu’il retourne la liste triée dans l’ordre décrois-sant."
]
},
{
"cell_type": "code",
"metadata": {
"id": "KFAheZzsY6RZ",
"colab_type": "code",
"colab": {}
},
"source": [
""
],
"execution_count": 0,
"outputs": []
}
]
}