47. Divide and Conquer (Diviser pour Régner) : Révision de Merge Sort/Quick Sort

Nous avons déjà rencontré les exemples les plus fondamentaux de Divide and Conquer (D&C) dans le tri.

Caractéristiques du D&C

• Indépendance : Les sous-problèmes créés pendant la phase de 'Division' doivent être résolus indépendamment les uns des autres. Leurs solutions n'affectent pas les solutions des autres sous-problèmes.
• Structure Identique : Les sous-problèmes sont généralement des instances plus petites du problème principal.

Exemple : Merge Sort (D&C Pur)

1. Diviser : Fractionner le tableau [1..N] en [1..N/2] et [N/2+1..N].
2. Régner : Trier récursivement les deux moitiés.
3. Combiner : Fusionner les deux moitiés triées.

Exemple : Quick Sort (D&C avec Partitionnement)

1. Diviser : Partitionner le tableau autour du pivot P.
2. Régner : Trier récursivement les éléments à gauche de P et les éléments à droite de P.
3. Combiner : Aucune étape de combinaison explicite n'est nécessaire, car le partitionnement garantit que P est déjà en place.