Scribd
Importer
95 vues3 pages

Algorithmes de tri en Python CPGE

Le document présente trois algorithmes de tri en Python : le tri par insertion, le tri rapide et le tri par fusion. Chaque algorithme est accompagné d'exemples de code et de résultats de tri sur des tableaux générés aléatoirement. Les méthodes sont expliquées de manière concise, illustrant leur fonctionnement et leur efficacité.

Transféré par

Abdelkader Barraj
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Thèmes abordés

  • tri hors place,
  • tri efficace,
  • tri hybride,
  • Python,
  • tri par insertion binaire,
  • algorithmes récursifs,
  • tri de tableaux,
  • méthodes de tri,
  • complexité algorithmique,
  • optimisation
95 vues3 pages

Algorithmes de tri en Python CPGE

Le document présente trois algorithmes de tri en Python : le tri par insertion, le tri rapide et le tri par fusion. Chaque algorithme est accompagné d'exemples de code et de résultats de tri sur des tableaux générés aléatoirement. Les méthodes sont expliquées de manière concise, illustrant leur fonctionnement et leur efficacité.

Transféré par

Abdelkader Barraj
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Thèmes abordés

  • tri hors place,
  • tri efficace,
  • tri hybride,
  • Python,
  • tri par insertion binaire,
  • algorithmes récursifs,
  • tri de tableaux,
  • méthodes de tri,
  • complexité algorithmique,
  • optimisation

Python pour CPGE scientifiques Documentation, Version 1

5.6 Tris

5.6.1 Tri par insertion

In [1]: def tri_insertion(tab):


...: for i in range(1,len(tab)):
...: val = tab[i]
...: pos = i
...: while pos > 0 and tab[pos - 1] > val:
...: tab[pos] = tab[pos-1]
...: pos -= 1
...: tab[pos] = val
...:

In [2]: from [Link] import randint

In [3]: tab = randint(100, size=20)

In [4]: tab
Out[4]:
array([18, 62, 15, 54, 39, 40, 94, 28, 42, 79, 12, 56, 85, 32, 94, 77, 13,
9, 15, 97])

In [5]: tri_insertion(tab)

In [6]: tab
Out[6]:
array([ 9, 12, 13, 15, 15, 18, 28, 32, 39, 40, 42, 54, 56, 62, 77, 79, 85,
94, 94, 97])

5.6.2 Tri rapide

In [7]: def tri_rapide(tab):


...: if tab == []:
...: return []

On pourrait penser à calculer le déterminant via la formule qui l’exprime en fonction des coefficients de la matrice ou à l’aide d’un développement
par rapport à une ligne ou une colonne mais on verra dans le chapitre ??? que c’est nettemment moins efficace que le pivot de Gauss

5.6. Tris 65
Python pour CPGE scientifiques Documentation, Version 1

...: else:
...: pivot = tab[0]
...: t1, t2 = [], []
...: for x in tab[1:]:
...: if x < pivot:
...: [Link](x)
...: else:
...: [Link](x)
...: return tri_rapide(t1) + [pivot] + tri_rapide(t2)
...:

In [8]: from [Link] import randint

In [9]: tab = randint(100, size=20)

In [10]: tab
Out[10]:
array([12, 69, 31, 90, 14, 60, 50, 56, 61, 0, 87, 30, 36, 42, 89, 80, 67,
15, 19, 56])

In [11]: tri_rapide(tab)
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
˓→[0, 12, 14, 15, 19, 30, 31, 36, 42, 50, 56, 56, 60, 61, 67, 69, 80, 87, 89, 90]

5.6.3 Tri par fusion

In [12]: def tri_fusion(tab):


....: if len(tab) < 2:
....: return tab
....: else:
....: m = len(tab)//2
....: return fusion(tri_fusion(tab[:m]), tri_fusion(tab[m:]))
....:

In [13]: def fusion(t1, t2):


....: i1, i2, n1, n2 = 0, 0, len(t1), len(t2)
....: t=[]
....: while i1 < n1 and i2 < n2:
....: if t1[i1] < t2[i2]:
....: [Link](t1[i1])
....: i1 += 1
....: else:
....: [Link](t2[i2])
....: i2 += 1
....: if i1 == n1:
....: [Link](t2[i2:])
....: else:
....: [Link](t1[i1:])
....: return t
....:

In [14]: from [Link] import randint

In [15]: tab = randint(100, size=20)

66 Chapitre 5. Algorithmes classiques


Python pour CPGE scientifiques Documentation, Version 1

In [16]: tab
Out[16]:
array([58, 48, 6, 96, 0, 44, 28, 1, 49, 90, 19, 46, 78, 52, 70, 0, 62,
8, 69, 98])

In [17]: tri_fusion(tab)
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
˓→[0, 0, 1, 6, 8, 19, 28, 44, 46, 48, 49, 52, 58, 62, 69, 70, 78, 90, 96, 98]

5.6. Tris 67

Vous aimerez peut-être aussi