Algorithmes et structures de données en Swift : cours complet pour débutants

Introduction aux algorithmes et structures de données en Swift

Swift est un langage de programmation puissant et intuitif, créé par Apple pour le développement d'applications sous iOS, macOS, watchOS et tvOS. Cependant, pour écrire un code efficace et rapide, il ne suffit pas de connaître la syntaxe. La compréhension des algorithmes et des structures de données est le fondement qui transforme un débutant en développeur professionnel.

Dans cet article, nous allons examiner les structures de données de base (tableaux, dictionnaires, ensembles) et les algorithmes clés (tri, recherche) en Swift. Tous les exemples de code sont prêts à être exécutés dans Xcode Playground.

Structures de données principales en Swift

Swift fournit des structures de données intégrées, optimisées pour la gestion de la mémoire et les performances. Examinons les trois plus importantes.

Tableaux (Array)

Un tableau est une collection ordonnée d'éléments du même type. En Swift, les tableaux sont strictement typés et ont un ordre fixe.

// Création d'un tableauvar numbers: [Int] = [1, 2, 3, 4, 5]

// Ajout d'un élémentnumbers.append(6)

// Accès par indexlet first = numbers[0] // 1

// Itérationfor number in numbers {    print(number)}

// Tri sur placenumbers.sort() // [1, 2, 3, 4, 5, 6]

Les tableaux sont idéaux lorsque l'ordre des éléments est important et qu'un accès rapide par index est nécessaire (O(1)). Cependant, l'insertion ou la suppression au début du tableau nécessite un temps O(n).

Dictionnaires (Dictionary)

Un dictionnaire stocke des paires "clé-valeur". Les clés doivent être uniques et hachables (par exemple, String, Int).

// Création d'un dictionnairevar scores: [String: Int] = ["Alice": 95, "Bob": 87]

// Ajout ou mise à jourscores["Charlie"] = 92

// Obtention de la valeur (optionnelle)if let aliceScore = scores["Alice"] {    print("Score d'Alice : \\(aliceScore)")}

// Suppressionscores.removeValue(forKey: "Bob")

Les dictionnaires permettent d'accéder à une valeur par sa clé en O(1) en moyenne. Utilisez-les lorsque les données sont naturellement regroupées par des clés uniques.

Ensembles (Set)

Un ensemble est une collection non ordonnée d'éléments uniques. Utile pour vérifier l'appartenance et supprimer les doublons.

// Création d'un ensemblevar fruits: Set<String> = ["Pomme", "Banane", "Orange"]

// Ajoutfruits.insert("Mangue")

// Vérification de présenceif fruits.contains("Pomme") {    print("La pomme est dans l'ensemble")}

// Suppression des doublons d'un tableaulet arrayWithDuplicates = [1, 1, 2, 3, 3, 4]let uniqueSet = Set(arrayWithDuplicates) // {1, 2, 3, 4}

Algorithmes de base en Swift

Appliquons maintenant les structures de données pour résoudre des problèmes typiques. Examinons le tri et la recherche.

Algorithmes de tri

Swift dispose d'une fonction intégrée sort(), mais pour comprendre, écrivons l'algorithme classique du tri rapide (Quick Sort).

func quickSort(_ array: [Int]) -> [Int] {    guard array.count > 1 else { return array }        let pivot = array[array.count / 2]    let less = array.filter { $0 < pivot }    let equal = array.filter { $0 == pivot }    let greater = array.filter { $0 > pivot }        return quickSort(less) + equal + quickSort(greater)}

let unsorted = [3, 6, 1, 8, 2, 9, 4]let sorted = quickSort(unsorted)print(sorted) // [1, 2, 3, 4, 6, 8, 9]

Le tri rapide est l'un des algorithmes les plus efficaces avec une complexité moyenne de O(n log n). Pour les petits tableaux, vous pouvez utiliser la fonction intégrée sorted().

Algorithmes de recherche

La recherche linéaire est simple mais lente (O(n)). Pour les données triées, utilisez la recherche binaire (O(log n)).

// Recherche binairefunc binarySearch(_ array: [Int], target: Int) -> Int? {    var low = 0    var high = array.count - 1        while low <= high {        let mid = (low + high)