STL __merge_without_buffer algorithme?

Question

Où puis-je obtenir une description de haut niveau décente de l'algorithme utilisé dans __ merge_without_buffer () dans la STL C ++? J'essaie de réimplémenter ce code dans le langage de programmation D, avec quelques améliorations. Je n'arrive pas à comprendre ce qu'il fait au niveau algorithmique en lisant simplement le code source de la STL parce qu'il y a trop de détails de bas niveau qui l'obscurcissent. De plus, je ne veux pas simplement traduire le code à l'aveuglette, car si cela ne fonctionnait pas, je ne saurais pas pourquoi et je ne pourrais pas ajouter mes améliorations.

Answer 1

__ merge_without_buffer () effectue une fusion sur place , en tant qu'étape de fusion d'un tri par fusion sur place. Il prend en entrée deux plages de données [premier, milieu) et [milieu, dernier) qui sont supposées être déjà triées. Les paramètres len1 et len2 sont égaux aux longueurs des deux plages d’entrée, à savoir (milieu - premier) et (dernier - milieu) respectivement.

Tout d'abord, il sélectionne un élément pivot . Ensuite, il réorganise les données dans l'ordre A1 B1 A2 B2 , où A1 est l'ensemble des éléments de [premier, milieu) qui sont inférieur au pivot, A2 est l'ensemble des éléments dans [premier, milieu) supérieur ou égal au pivot, B1 est l'ensemble d’éléments [dernier, dernier) inférieurs au pivot, et B2 est l’ensemble des éléments situés dans [milieu, dernier) supérieur à ou égal au pivot. Notez que les données sont à l’origine dans l’ordre A1 A2 B1 B2 . Il suffit donc de transformer A2 B1 en B1 A2 . C’est avec un appel à std :: rotate () , qui ne fait que cela.

Nous avons maintenant séparé les éléments inférieurs au pivot ( A1 et B1 ) de ceux qui sont supérieurs ou égaux au pivot ( A2 et B2 ), nous pouvons donc maintenant fusionner de manière récursive les deux sous-gammes A1 A2 et B1 B2 .

Comment choisit-on un pivot? Dans l'implémentation que je regarde, il choisit l'élément médian de la plus grande sous-gamme (c'est-à-dire si [premier, milieu) a plus d'éléments que [milieu, dernier) , il choisit la médiane de [premier, milieu) ; sinon, il choisit la médiane de [milieu, dernier) ). Les sous-gammes étant déjà triées, le choix de la médiane est trivial. Ce choix de pivot garantit que lors de la fusion récursive des deux sous-plages, chaque sous-problème ne représente pas plus de 3/4 de la taille du problème actuel, car dans le pire des cas, au moins 1/4 des éléments sont plus grands ou plus petits que le pivot. .

Quelle est la durée d'exécution de ceci? L'appel std :: rotate () prend O (N) fois et nous effectuons deux appels récursifs. Cela équivaut à une durée d'exécution de O (N log N). Toutefois, notez qu'il ne s'agit que d'une étape dans mergesort: rappelez-vous que, dans le cas de mergesort, vous devez d'abord trier récursivement les deux moitiés, puis les fusionner. Ainsi, la relation de récurrence pour la durée d'exécution de mergesort est maintenant:

T (N) = 2T (N / 2) + O (N log N)

Connectez-le au théorème principal et vous obtiendrez que ce test s'exécute maintenant en O (N log ² N) heure!

Comme dernier point intéressant, considérons les trois qualités suivantes d’un algorithme de tri basé sur la comparaison:

1. En place
2. Stable
3. s'exécute dans le temps O (N log N)

Vous ne pouvez généralement obtenir que deux de ces éléments à la fois: le tri rapide vous permet d'obtenir (1) et (3), mergesort, vous (2) et (3), et un système de fusion sur place vous permet d'obtenir (1) et (2). ). Les tris non basés sur des comparaisons tels que le tri par nombre peuvent atteindre les 3, mais ces tris ne peuvent trier que certains types de données. Il est possible qu'il existe un type basé sur la comparaison qui réalise les 3, mais s'il en existe, je ne suis pas au courant de son existence, et c'est certainement beaucoup plus compliqué.