Algorithmes et structures de données en PHP : guide pratique

Algorithmes et structures de données en PHP : en pratique

Dans le monde du développement web, PHP reste l'un des langages les plus populaires. Cependant, de nombreux développeurs, familiers avec la syntaxe, négligent souvent les concepts fondamentaux — les algorithmes et les structures de données. Comprendre ces sujets améliore non seulement la qualité du code, mais fait également de vous un spécialiste plus compétitif lors des entretiens. Dans cet article, nous allons décortiquer les algorithmes et structures de données clés en PHP avec des exemples de code réels que vous pourrez immédiatement appliquer dans vos projets.

1. Structures de données de base : pile et file d'attente

La pile et la file d'attente sont des structures de données linéaires souvent utilisées dans les applications réelles. La pile fonctionne selon le principe LIFO (Last In, First Out), tandis que la file d'attente fonctionne selon le principe FIFO (First In, First Out). En PHP, on peut les implémenter à l'aide des fonctions intégrées de tableau.

Implémentation d'une pile

<?php\nclass Stack {\n    private $stack = [];\n\n    public function push($item) {\n        array_push($this->stack, $item);\n    }\n\n    public function pop() {\n        if ($this->isEmpty()) {\n            return null;\n        }\n        return array_pop($this->stack);\n    }\n\n    public function peek() {\n        return end($this->stack);\n    }\n\n    public function isEmpty() {\n        return empty($this->stack);\n    }\n}\n\n// Exemple d'utilisation\n$stack = new Stack();\n$stack->push("Premier");\n$stack->push("Deuxième");\n$stack->push("Troisième");\necho $stack->pop(); // Troisième\necho $stack->peek(); // Deuxième\n?>

Implémentation d'une file d'attente

<?php\nclass Queue {\n    private $queue = [];\n\n    public function enqueue($item) {\n        array_push($this->queue, $item);\n    }\n\n    public function dequeue() {\n        if ($this->isEmpty()) {\n            return null;\n        }\n        return array_shift($this->queue);\n    }\n\n    public function front() {\n        return reset($this->queue);\n    }\n\n    public function isEmpty() {\n        return empty($this->queue);\n    }\n}\n\n// Exemple d'utilisation\n$queue = new Queue();\n$queue->enqueue("Premier");\n$queue->enqueue("Deuxième");\n$queue->enqueue("Troisième");\necho $queue->dequeue(); // Premier\necho $queue->front();    // Deuxième\n?>

Ces structures de données sont indispensables pour implémenter des tampons, l'historique des actions (undo/redo) et le traitement des tâches dans l'ordre d'arrivée.

2. Algorithmes de tri en PHP

Le tri est l'une des opérations les plus fréquentes en programmation. Examinons deux implémentations classiques : le tri à bulles (pour l'apprentissage) et le tri rapide (pour un usage réel).

Tri à bulles (Bubble Sort)

<?php\nfunction bubbleSort(&$arr) {\n    $n = count($arr);\n    for ($i = 0; $i < $n - 1; $i++) {\n        for ($j = 0; $j < $n - $i - 1; $j++) {\n            if ($arr[$j] > $arr[$j + 1]) {\n                // Échange des valeurs\n                $temp = $arr[$j];\n                $arr[$j] = $arr[$j + 1];\n                $arr[$j + 1] = $temp;\n            }\n        }\n    }\n}\n\n$numbers = [64, 34, 25, 12, 22, 11, 90];\nbubbleSort($numbers);\nprint_r($numbers); // [11, 12, 22, 25, 34, 64, 90]\n?>

Complexité : O(n²) — ne convient pas pour les grands tableaux, mais illustre parfaitement le principe.

Tri rapide (Quick Sort)

<?php\nfunction quickSort($arr) {\n    if (count($arr) < 2) {\n        return $arr;\n    }\n\n    $pivot = $arr[0];\n    $left = $right = [];\n\n    for ($i = 1; $i < count($arr); $i++) {\n        if ($arr[$i] < $pivot) {\n            $left[] = $arr[$i];\n        } else {\n            $right[] = $arr[$i];\n        }\n    }\n\n    return array_merge(quickSort($left), [$pivot], quickSort($right));\n}\n\n$numbers = [3, 6, 8, 10, 1, 2, 1];\n$sorted = quickSort($numbers);\nprint_r($sorted); // [1, 1, 2, 3, 6, 8, 10]\n?>