Geekly articles weekly

Fusion équilibrée de haut en bas et de bas en haut


Dans le dernier article, nous nous sommes familiarisés avec les types de fusion reliques (provoquant principalement un intérêt historique). Quelle est la tendance aujourd'hui?

Pour vous familiariser avec le concept de classement par fusion, des algorithmes de fusion équilibrés sont généralement utilisés. Le terme «équilibre» signifie que l'algorithme divise récursivement le tableau et ses sous-réseaux en parties approximativement égales. Aujourd'hui, nous regardons à quoi cela ressemble dans la pratique.

Une paire de fonctions est la même pour les deux méthodes. Quoi qu'il en soit, ce «haut-bas», ce «haut-bas» est presque le même algorithme, juste montré sous des angles différents.

Nous avons besoin, en fait, de la fusion de deux moitiés du segment en un seul sous-tableau. Les moitiés sont triées simultanément dans un tableau, les éléments actuels dans les deux itérations sont comparés et l'élément plus petit va dans le deuxième tableau:

//   A[iBegin: iMiddle - 1] //   A[iMiddle: iEnd - 1] //:   B[iBegin: iEnd - 1] void Merge(A[], iBegin, iMiddle, iEnd, B[]) { i = iBegin, j = iMiddle; //       ... for (k = iBegin; k < iEnd; k++) { //     //  <=    if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) { B[k] = A[i]; i++; } else { B[k] = A[j]; j++; } } }

Copie d'un segment d'un tableau à un autre. Les deux implémentations fonctionnent sur deux tableaux, les données doivent être constamment conduites du principal vers l'auxiliaire et vice versa:

 //    A[] //   B[] void CopyArray(A[], iBegin, iEnd, B[]) { for(k = iBegin; k < iEnd; k++) B[k] = A[k]; }

Fusion équilibrée décroissante




Tout d'abord, l'ensemble du tableau est pris, après quoi une descente récursive commence. Un tableau est dichotomisé jusqu'à ce que nous atteignions des sous-tableaux d'un élément (qui sont triés par eux-mêmes). Ensuite, la récursion commence la montée inverse, fusionnant les sous-réseaux le long du chemin (dont la taille double à chaque niveau).

 //  A[]     // B[]   void TopDownMergeSort(A[], B[], n) { CopyArray(A, 0, n, B); // A[]  B[] TopDownSplitMerge(B, 0, n, A);// B[]    A[] } //    A[],  B[]    // : iBegin ; iEnd   void TopDownSplitMerge(B[], iBegin, iEnd, A[]) { // size == 1,     if(iEnd - iBegin < 2) return; // size > 1,     iMiddle = (iEnd + iBegin) / 2;//iMiddle -   //     A[]  B[] TopDownSplitMerge(A, iBegin, iMiddle, B);//   TopDownSplitMerge(A, iMiddle, iEnd, B);//   //    B[]  A[] Merge(B, iBegin, iMiddle, iEnd, A); }


Fusion équilibrée à la hausse




Ici, l'itération sur le tableau a lieu, en cours de route, nous prenons d'abord les tableaux minimaux voisins (d'un élément) et les fusionnons par paires. En obtenant des sous-réseaux triés doublés à chaque étape, nous fusionnons à nouveau les voisins et continuons jusqu'à ce que nous obtenions tout le tableau dans la sortie, déjà sous forme triée.

 //  A[]     // B[]   void BottomUpMergeSort(A[], B[], n) { //      A[]  «». //    : //× 2, 4, 8, 16, ... -   ,       for (width = 1; width < n; width = 2 * width) { //     width for (i = 0; i < n; i = i + 2 * width) { //   : //A [i: i + width - 1]  A [i + width: i + 2 * width - 1]  B[] //  A[i: n - 1]  B[] ( i + width > = n) Merge(A, i, min(i + width, n), min(i + 2 * width, n), B); } //   B[]    2 * width //  B[]   A[]    //     A[]  B[] CopyArray(B, 0, n, A); // B[]  A[] //      2 * width } }

En général, une implémentation vers le bas est préférable, car elle utilise plus efficacement deux tableaux, qui changent simplement constamment les rôles de "principal / auxiliaire". Dans la version en amont, le tableau A est toujours principal et le tableau B est toujours auxiliaire. Par conséquent, après chaque itération, les données de B doivent être renvoyées intégralement à A, ce qui ne contribue pas à l'amélioration de la complexité algorithmique. En revanche, l'implémentation de l'ascendant est plus simple, elle n'a même pas de récursivité.

Fusion déséquilibrée


Du mot «équilibre» lui-même, il souffle une sorte de fiabilité, de stabilité. Vous pouvez même avoir l'impression qu'un bon algorithme doit être équilibré. Et le «déséquilibre» est associé à une sorte de tremblements et de distorsions. Eh bien, vraiment, un modèle équilibré ne devrait-il pas être meilleur à tous égards qu'un modèle non équilibré ?

En fait, c'est pire. Bien sûr, la division des sous-réseaux en moitiés égales (ce que l'on entend par équilibre pour les types de fusion) est beaucoup plus facile à mettre en œuvre. Divisez-vous le tableau en deux et appliquez la récursivité à chaque moitié. En fait, cette facilité est le principal avantage d'une fusion équilibrée avant une fusion déséquilibrée.

Dans les publications suivantes, nous présenterons des méthodes non équilibrées. Ils sont nettement plus difficiles à comprendre et à mettre en œuvre. Les données pour la fusion ultérieure ne seront pas distribuées de manière homogène et uniforme entre les matrices auxiliaires, mais conformément à un certain nombre de nombres de Fibonacci généralisés. Et cela vous permettra d'obtenir des résultats puissants qui sont inaccessibles pour des méthodes équilibrées simplifiées.

Les références


Fusionner ( Google-traduire ), Fusionner

Articles de série:



Les prochains triages de fusion sont désormais disponibles dans l'application AlgoLab (pour ceux qui étudient les algorithmes à l'aide de cette application Excel, mettez à jour le fichier).

Les tableaux sont temporairement limités - leur taille doit être une puissance de deux (en raison de certaines difficultés rencontrées lors de la programmation de la visualisation). Un peu plus tard, il sera possible de trier tous les tableaux.

Logiciel EDISON - développement web
Cet article a été écrit avec le soutien d'EDISON Software, une entreprise qui utilise des services cloud pour créer des logiciels embarqués et développer des applications mobiles sur JAVA .

Source: https://habr.com/ru/post/fr432646/

More articles:


All Articles