Comparaison des algorithmes de tri de données en Python, Java et Rust

Claude Paugh
17 oct.
6 min de lecture

Les algorithmes de tri sont essentiels en informatique et en programmation. Ils permettent d'organiser les données dans un ordre précis, améliorant ainsi l'efficacité et la convivialité. Dans cet article, nous comparerons plusieurs algorithmes de tri implémentés en Python, Java et Rust. Nous n'avons pas inclus C++, généralement le langage le plus performant, mais il est utilisé pour la manipulation et le traitement des données en ingénierie des données. Nous nous concentrerons sur la complexité de leur code et la notation Big O. Vous découvrirez des exemples de code pour chaque langage et des recommandations pour les meilleures combinaisons en fonction des performances et de la simplicité d'utilisation.

Comprendre les algorithmes de tri

Les algorithmes de tri permettent de classer les éléments d'une liste ou d'un tableau selon un ordre spécifique, généralement croissant ou décroissant. Il existe de nombreux algorithmes de tri, chacun présentant ses avantages et ses inconvénients. Voici quelques exemples courants :

Tri à bulles : simple mais inefficace pour les grands ensembles de données.
Tri par sélection : également simple, mais présente des inefficacités similaires.
Tri par insertion : efficace pour les petits ensembles de données ou les données principalement triées.
Tri par fusion : une stratégie de division et de conquête efficace avec des ensembles de données plus volumineux.
Tri rapide : très efficace pour une large gamme d'ensembles de données.

Chaque algorithme trie les données différemment, ce qui affecte son efficacité et ses performances.

Notation Big O

La notation Big O décrit les performances et la complexité d'un algorithme. Elle fixe une limite supérieure à la complexité temporelle ou spatiale en fonction de la taille des données d'entrée. La compréhension de la notation Big O est essentielle pour évaluer l'efficacité des algorithmes de tri.

Notations Big O courantes pour les algorithmes de tri

O(n^2) : complexité temporelle quadratique, typique des algorithmes tels que le tri à bulles, le tri par sélection et le tri par insertion.
O(n log n) : complexité temporelle log-linéaire, trouvée dans des algorithmes plus efficaces tels que Merge Sort et Quick Sort.
O(n) : Complexité temporelle linéaire, observée dans des cas spécifiques comme le tri par comptage.

Algorithmes de tri en Python

Tri à bulles

Le tri à bulles est l'une des méthodes de tri les plus simples. Il parcourt la liste de manière répétée, compare les éléments adjacents et les permute s'ils sont dans le mauvais ordre.

--> python

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

Exemple d'utilisation

arr = [64, 34, 25, 12, 22, 11, 90]
print("Sorted array:", bubble_sort(arr))

Le tri à bulles a une complexité temporelle de O(n^2), ce qui le rend inefficace pour les grands ensembles de données.

Tri par fusion

Le tri par fusion est un algorithme de division pour régner. Il divise le tableau d'entrée en deux moitiés, les trie, puis les fusionne à nouveau.

` -->python

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
    return arr

Exemple d'utilisation

arr = [38, 27, 43, 3, 9, 82, 10]
print("Sorted array:", merge_sort(arr))

Avec une complexité temporelle de O(n log n), le tri par fusion est plus efficace pour les ensembles de données plus volumineux que le tri à bulles.

Algorithmes de tri en Java

Tri par sélection

Le tri par sélection divise la liste d'entrée en une partie triée et une partie non triée. Il sélectionne à plusieurs reprises le plus petit (ou le plus grand) élément de la partie non triée et le déplace vers la partie triée.

-->java

import java.util.Arrays;

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

Comme le tri à bulles, le tri par sélection a également une complexité temporelle de O(n^2).

Tri rapide

Quick Sort est un algorithme de tri efficace utilisant une stratégie de division pour régner. Il sélectionne un élément pivot et partitionne le tableau en deux moitiés, les triant de manière récursive.

-->java

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

Quick Sort a une complexité temporelle moyenne de O(n log n), ce qui en fait l'un des algorithmes de tri les plus rapides.

Algorithmes de tri en Rust

Tri par insertion

Le tri par insertion crée un tableau trié de manière incrémentale. Il peut être plus efficace sur de petites listes ou des données majoritairement triées.

--> rouille

fn insertion_sort(arr: &mut Vec<i32>) {
    let n = arr.len();
    for i in 1..n {
        let key = arr[i];
        let mut j = i as isize - 1;
        while j >= 0 && arr[j as usize] > key {
            arr[j as usize + 1] = arr[j as usize];
            j -= 1;
        }

        arr[j as usize + 1] = key;
    }
}

fn main() {
    let mut arr = vec![12, 11, 13, 5, 6];
    insertion_sort(&mut arr);
    println!("Sorted array: {:?}", arr);
}

Le tri par insertion a une complexité temporelle de O(n^2), il n'est donc pas idéal pour les grands ensembles de données.

Tri par tas

Le tri par tas utilise une structure de tas binaire. Il s'agit d'un algorithme de comparaison dont la complexité temporelle est de O(n log n).

--> rouille

fn heapify(arr: &mut Vec<i32>, n: usize, i: usize) {
    let mut largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;

    if left < n && arr[left] > arr[largest] {
        largest = left;
    }

    if right < n && arr[right] > arr[largest] {
        largest = right;
    }

    if largest != i {
        arr.swap(i, largest);
        heapify(arr, n, largest);
    }
}

fn heap_sort(arr: &mut Vec<i32>) {
    let n = arr.len();
    for i in (0..n / 2).rev() {
        heapify(arr, n, i);
    }

    for i in (0..n).rev() {
        arr.swap(0, i);
        heapify(arr, i, 0);
    }
}

fn main() {
    let mut arr = vec![12, 11, 13, 5, 6];
    heap_sort(&mut arr);
    println!("Sorted array: {:?}", arr);
}

Le tri par tas est efficace, ce qui le rend adapté aux ensembles de données plus volumineux, avec une complexité temporelle de O(n log n).

Comparaison de la complexité et des performances du code

Lors de la comparaison des algorithmes de tri entre Python, Java et Rust, plusieurs facteurs sont importants :

Facilité d'implémentation : La syntaxe simple de Python permet souvent des implémentations plus rapides et plus simples. En revanche, Java et Rust nécessitent davantage de code standard.
Performances : Rust surpasse généralement les autres langages grâce à sa gestion efficace de la mémoire et à ses capacités système. Java offre également de bonnes performances, mais Python est plus lent car c'est un langage interprété. Par exemple, pour le même jeu de données, Quick Sort s'exécute deux fois plus vite en Rust qu'en Python.
Notation Big O : les complexités temporelles des algorithmes restent cohérentes entre les langages, mais les performances réelles varient en fonction du modèle d'exécution et des optimisations de chaque langage.

Accords recommandés

Python avec Merge Sort : utile pour sa lisibilité et sa simplicité, en particulier pour les ensembles de données plus volumineux.
Java avec tri rapide : connu pour sa grande efficacité, ce qui le rend idéal pour les applications axées sur les performances.
Rust avec tri par tas : excellent choix pour la vitesse et l'utilisation efficace de la mémoire.

Réflexions finales

Les algorithmes de tri sont des outils essentiels en programmation. Comprendre leur complexité et leur implémentation dans différents langages peut grandement influencer les performances. Alors que Python offre une grande simplicité d'utilisation, Java allie performance et lisibilité. Rust se distingue par sa rapidité, ce qui le rend idéal pour les applications à haute performance.

Le choix du bon algorithme de tri et du bon langage dépend en fin de compte des besoins de votre projet et des caractéristiques de chaque langage. En comprenant les options, vous pourrez prendre une décision éclairée qui améliorera les performances de votre application.