Qu’est-ce que le tri ?

Le tri fait référence au processus de classement des données dans un ordre spécifique, généralement par ordre croissant ou décroissant, sur la base d'une relation linéaire entre les éléments de données.

Pourquoi avons-nous besoin de trier ?

Le tri est crucial lorsque vous travaillez avec des données structurées, car il permet une récupération efficace des données, simplifie l'analyse des données et améliore la gestion globale des données.

Algorithmes de tri

Cet article couvre les algorithmes de tri suivants : tri à bulles, tri par sélection, tri par insertion, tri par fusion et tri rapide.

Tri à bulles

Bubble Sort parcourt le tableau à plusieurs reprises, en comparant les éléments adjacents et en les échangeant s'ils sont dans le mauvais ordre. Ce processus se poursuit jusqu'à ce que le tableau soit trié, les éléments plus gros « bouillonnant » jusqu'à la fin.

Algorithme

Étape 1 : Commencer
Étape 2 : je = 0
Étape 3 : si i Étape 4 : j = 0
Étape 5 : si j Étape 6 : si array[j] > array[j 1], passez à l'étape 7 ; sinon, passez à l'étape 8
Étape 7 : Échanger le tableau[j] et le tableau[j 1]
Étape 8 : incrémenter j ; passer à l'étape 5
Étape 9 : incrémenter i ; passer à l'étape 3
Étape 10 : Fin

Code

def bubble_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr)):
        for j in range(len(arr)-i-1):
            if arr[j] > arr[j 1]:
                arr[j], arr[j 1] = arr[j 1], arr[j]

    print("Array After Sorting: ", end='')
    print(arr)

# Main
bubble_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])

Complexité temporelle

Meilleur cas : O(n)
Cas moyen : O(n^2)
Pire des cas : O(n^2)

Tri de sélection

Le tri par sélection recherche la plus petite valeur dans la partie non triée du tableau et la place au début de cette partie.

Algorithme

Étape 1 : Commencer
Étape 2 : i = 0
Étape 3 : si i Étape 4 : minimum_value = i ; j = je 1
Étape 5 : si j Étape 6 : si array[minimum_value] > array[j], passez à l'étape 7 ; sinon, passez à l'étape 8
Étape 7 : valeur_minimale = j
Étape 8 : incrément j; passer à l'étape 5
Étape 9 : échangez le tableau[minimum_value] et le tableau[i]
Étape 10 : incrémenter i ; passer à l'étape 3
Étape 11 : Fin

Code

def selection_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr) - 1):
        min_val = i
        for j in range(i   1, len(arr)):
            if arr[j] 




  
  
  Complexité temporelle


Meilleur cas : O(n^2)

Cas moyen : O(n^2)

Pire des cas : O(n^2) 


  
  
  Tri par insertion


Le tri par insertion construit le tableau trié un élément à la fois en prenant chaque élément de la partie non triée et en l'insérant à la position correcte dans la partie triée.


  
  
  Algorithme


Étape 1 : Commencer

Étape 2 : i = 1

Étape 3 : si i 
Étape 4 : clé = arr[i]

Étape 5 : j = i - 1

Étape 6 : si j >= 0 et arr[j] > clé, passez à l'étape 7 ; sinon, passez à l'étape 10

Étape 7 : arr[j 1] = arr[j]

Étape 8 : décrémenter j de 1

Étape 9 : passez à l'étape 6

Étape 10 : arr[j 1] = clé

Étape 11 : incrémenter i de 1 ; passer à l'étape 3

Étape 12 : Fin


  
  
  Code




def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j   1] = arr[j]
            j -= 1

        arr[j   1] = key

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
insertion_sort(arr)
print("Array After Sorting:", arr)





  
  
  Complexité temporelle


Meilleur cas : O(n)

Cas moyen : O(n^2)

Pire des cas : O(n^2) 


  
  
  Fusionner le tri


Merge Sort est un algorithme diviser pour régner qui divise de manière récursive le tableau en sous-tableaux plus petits, les trie, puis les fusionne à nouveau.


  
  
  Algorithme


Algorithme de tri par fusion


Étape 1 : Commencer

Étape 2 : Si length(array) 
Étape 3 : mid_point = length(array) // 2

Étape 4 : half_gauche = array[:mid_point]

Étape 5 : right_half = array[mid_point:]

Étape 6 : sorted_left = merge_sort(left_half)

Étape 7 : sorted_right = merge_sort(right_half)

Étape 8 : retourner la fusion (sorted_left, sorted_right)

Étape 9 : Fin

Fonction de fusion


Étape 1 : Commencer

Étape 2 : sorted_merge = []

Étape 3 : l = 0, r = 0

Étape 4 : si l 
Étape 5 : si left[l] 
Étape 6 : ajoutez left[l] à sorted_merge ; incrémenter l de 1

Étape 7 : ajoutez right[r] à sorted_merge ; incrémenter r de 1

Étape 8 : passez à l'étape 4

Étape 9 : si l 
Étape 10 : ajoutez left[l] à sorted_merge ; incrémenter l de 1 

Étape 11 : passez à l'étape 9

Étape 12 : si r 
Étape 13 : ajoutez right[r] à sorted_merge ; incrémenter r de 1

Étape 14 : passez à l'étape 12

Étape 15 : Renvoyer sorted_merge

Étape 16 : Fin


  
  
  Code




def merge(left, right):
    sorted_merge = []
    l = r = 0
    while l 




  
  
  Complexité temporelle


Meilleur cas : O(n log n)

Cas moyen : O(n log n)

Pire des cas : O(n log n) 


  
  
  Tri rapide


Quick Sort est un algorithme de tri efficace sur place qui utilise une approche diviser pour régner. Il sélectionne un élément pivot et divise le tableau autour du pivot de sorte que les éléments inférieurs au pivot soient à sa gauche et les éléments supérieurs au pivot soient à sa droite. Ce processus est ensuite appliqué de manière récursive aux sous-tableaux.


  
  
  Algorithme


Tri rapide


Étape 1 : Commencer

Étape 2 : Si faible 
Étape 3 : pivot_index = partition(arr, low, high)

Étape 4 : tri rapide (arr, low, pivot_index - 1)

Étape 5 : tri rapide (arr, pivot_index 1, high)

Étape 6 : Fin 

Fonction de partition


Étape 1 : Commencer

Étape 2 : pivot = arr[high]

Étape 3 : gauche = bas, droite = haut - 1

Étape 4 : si gauche 
Étape 5 : si arr[left] > pivot et arr[right] 
Étape 6 : si arr[left] 
Étape 7 : si arr[right] >= pivot, décrémenter à droite

Étape 8 : passez à l'étape 4

Étape 9 : échangez arr[left] et arr[high]

Étape 10 : revenir à gauche

Étape 11 : Fin 


  
  
  Code




def partition(arr, low, high):
    pivot = arr[high]
    left = low
    right = high - 1
    while left  pivot and arr[right] = pivot:
            right -= 1
    arr[left], arr[high] = arr[high], arr[left]
    return left

def quicksort(arr, low, high):
    if low 




  
  
  Complexité temporelle


Meilleur cas : O(n log n)

Cas moyen : O(n log n)

Pire des cas : O(n^2)