Algorithmes de tri en Python

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 je < length(array) - 1, passez à l'étape 4 ; sinon, passez à l'étape 10
Étape 4 : j = 0
Étape 5 : si j < length(array) - i - 1, passez à l'étape 6 ; sinon, passez à l'étape 3
Étape 6 : si array[j] > array[j + 1], passez à l'étape 7 ; sinon, passez à l'étape 8
Étape 7 : Échangez le tableau[j] et le tableau[j + 1]
Étape 8 : incrémenter j ; passez à l'étape 5
Étape 9 : incrémenter i ; passez à 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 trouve 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 je < length(array) - 1, passez à l'étape 4 ; sinon, passez à l'étape 10
Étape 4 : minimum_value = i ; j = je + 1
Étape 5 : si j < longueur (tableau), passez à l'étape 6 ; sinon, passez à l'étape 9
Étape 6 : si tableau[valeur_minimum] > array[j], passez à l'étape 7 ; sinon, passez à l'étape 8
Étape 7 : minimum_value = j
Étape 8 : incrément j; passez à l'étape 5
Étape 9 : échangez le tableau[minimum_value] et le tableau[i]
Étape 10 : incrémenter i ; passez à 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] < arr[min_val]:
                min_val = j

        arr[i], arr[min_val] = arr[min_val], arr[i]

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

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

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 dans la position correcte dans la partie triée.

Algorithme

Étape 1 : Commencer
Étape 2 : i = 1
Étape 3 : si je < len(arr), passez à l'étape 4 ; sinon, passez à l'étape 12
É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 ; passez à 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 récursivement 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) <= 1, renvoie le tableau ; passez à l'étape 9
Étape 3 : mid_point = length(array) // 2
Étape 4 : left_half = 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 < len(à gauche) et r &Lt ; len (à droite), passez à l'étape 5 ; sinon, passez à l'étape 9
Étape 5 : si gauche[l] <= droite[r], passez à l'étape 6 ; sinon, passez à l'étape 7
É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 < len (à gauche), passez à l'étape 10 ; sinon, passez à l'étape 12
Étape 10 : ajoutez left[l] à sorted_merge ; incrémenter l de 1
Étape 11 : passez à l’étape 9
Étape 12 : si r < len (à droite), passez à l'étape 13 ; sinon, passez à l'étape 15
É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 < len(left) and r < len(right):
        if left[l] <= right[r]:
            sorted_merge.append(left[l])
            l += 1
        else:
            sorted_merge.append(right[r])
            r += 1

    while l < len(left):
        sorted_merge.append(left[l])
        l += 1

    while r < len(right):
        sorted_merge.append(right[r])
        r += 1

    return sorted_merge

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid_point = len(arr) // 2
    left_half = arr[:mid_point]
    right_half = arr[mid_point:]

    sorted_left = merge_sort(left_half)
    sorted_right = merge_sort(right_half)

    return merge(sorted_left, sorted_right)

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

Complexité temporelle

Meilleur cas : O(n log n)
Cas moyen : O(n log n)
Pire des cas : O(n log n)

Quick Sort

Quick Sort is an efficient, in-place sorting algorithm that uses a divide-and-conquer approach. It selects a pivot element and partitions the array around the pivot so that elements less than the pivot are on its left and elements greater than the pivot are on its right. This process is then recursively applied to the sub-arrays.

Algorithm

Quick Sort

Step 1: Begin
Step 2: If low < high, goto Step 3; else goto Step 6
Step 3: pivot_index = partition(arr, low, high)
Step 4: quicksort(arr, low, pivot_index - 1)
Step 5: quicksort(arr, pivot_index + 1, high)
Step 6: End

Partition Function

Step 1: Begin
Step 2: pivot = arr[high]
Step 3: left = low, right = high - 1
Step 4: if left <= right goto Step 5, else goto Step 9
Step 5: if arr[left] > pivot and arr[right] < pivot, swap arr[left] and arr[right]
Step 6: if arr[left] <= pivot, increment left
Step 7: if arr[right] >= pivot, decrement right
Step 8: goto Step 4
Step 9: swap arr[left] and arr[high]
Step 10: return left
Step 11: End

Code

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

def quicksort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quicksort(arr, low, pivot_index - 1)
        quicksort(arr, pivot_index + 1, high)

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

Time Complexity

Best Case : O(n log n)
Average Case : O(n log n)
Worst Case : O(n^2)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!