Problème de sélection du k-ième plus petit élément d'un tableau

Étant donné un tableau T=[T[0],...,T[n-1]] de $n$ éléments quelconques (par exemple des entiers), et $k\in\{1,\dots,n\}$, on cherche le k-ième plus petit élément du tableau.

Exemple : pour T = [5, 4, 1, 2, 3], pour k=1 on a 1, k=2 on a 2, etc.

En cas d'éléments distincts, par exemple T = [1, 1, 2, 3], le 2-ième plus petit peut être définit comme 2, ou comme 1. Il vaut mieux le définir comme 1, ainsi l'élément cherché a toujours un sens.

Ce petit notebook Python implémente :

Je fais aussi des expériences numériques pour illustrer empiriquement leurs complexités.

J'ai pris l'habitude d'écrire des signatures de fonctions en python qui soient typées :

Je ferai les premiers exemples avec ces deux tableaux :

Solution naïve en temps quadratique

On peut rapidement imaginer un algorithme "divisé pour régner" naïf :

Deux exemples :

Solution naïve en temps sur logarithmique (O(n log n))

C'est un algorithme très simple :

Deux exemples :

Méthode optimale : médiane des médianes

L'algorithme se déroule en 3 étapes :

Référence : https://fr.wikipedia.org/wiki/Médiane_des_médianes, aussi dans [Algorithmique, Cormen et al]

Calcul en temps constant de la médiane de 5 valeurs

Que se passe-t-il si la liste n'est pas de taille impaire ? On peut prendre la valeur à gauche ou à droite du milieu. Ici, c'est la valeur à droite qui a été choisie :

Découper le tableau en sous-tableaux :

Par exemple :

Cela est très rapide avec des listes par compréhension :

Et donc si on calcule les médianes :

Médiane des médianes par une approche récursive

Par exemple, la médiane des médianes du tableau d'exemple est 8 car son tableau des médianes des sous-tableaux de taille <= 5 est [3, 8, 12] :

Sélection par médianes

On met ensemble tous les éléments :

Deux exemples :

Autre approche

En regardant le code donné sur https://en.wikipedia.org/wiki/Median_of_medians

On va faire plein d'échanges de valeurs dans un tableau :

Avec un petit tri par insertion sur cinq éléments (max cinq), on peut trouver la médiane d'un petit tableau en temps constant :

Par exemple :

Le calcul du pivot fera un appel à selection, qui lui-même appelle pivot (par récursion mutuelle) :

La sélection utilisera la fonction pivot et la partition :

Et enfin la fonction de partition :

Deux exemples :

Autre implémentation

Celle-ci sera la bonne :

Inspirée de https://stackoverflow.com/a/34911527/

On peut faire quelques tests :

Empiriquement, pour des listes pas trop grandes, la méthode naïve qui trie la liste est plus rapide. C'est assez logique, le tri sorted() de Python est implémenté en C et est très efficace.

Pour des listes plus grandes, on voit que la tendance s'inverse.

Conclusion

C'est tout pour ce notebook ! Merci de l'avoir lu.

Pour plus de notebooks, cf https://GitHub.com/Naereen/notebooks