Comment trier sur place à l'aide de l'algorithme de tri par fusion?

244

Je sais que la question n'est pas trop précise.

Tout ce que je veux, c'est que quelqu'un me dise comment convertir un tri de fusion normal en un tri de fusion sur place (ou un tri de fusion avec un espace supplémentaire constant).

Tout ce que je peux trouver (sur le net), c'est des pages disant "c'est trop complexe" ou "hors de portée de ce texte".

Les seules façons connues de fusionner sur place (sans espace supplémentaire) sont trop complexes pour être réduites à un programme pratique. (extrait d'ici )

Même s'il est trop complexe, quel est le concept de base sur la façon de rendre le tri de fusion en place?

Lazer
la source
Belle question, je me suis posé la question en lisant une question d'hier: stackoverflow.com/questions/2566459/…
Chris Lercher
Il existe une méthode assez simple décrite ici: xinok.wordpress.com/2014/08/17/…
Branko Dimitrijevic

Réponses:

140

Knuth a laissé cela comme un exercice (Vol 3, 5.2.5). Il existe des sortes de fusion sur place. Ils doivent être mis en œuvre avec soin.

Tout d'abord, la fusion naïve sur place telle que décrite ici n'est pas la bonne solution. Il rétrograde les performances à O (N 2 ) .

L'idée est de trier une partie du tableau tout en utilisant le reste comme zone de travail pour la fusion.

Par exemple, comme la fonction de fusion suivante.

void wmerge(Key* xs, int i, int m, int j, int n, int w) {
    while (i < m && j < n)
        swap(xs, w++, xs[i] < xs[j] ? i++ : j++);
    while (i < m)
        swap(xs, w++, i++);
    while (j < n)
        swap(xs, w++, j++);
}  

Il prend le tableau xs, les deux sous-tableaux triés sont représentés sous forme de plages [i, m)et [j, n)respectivement. La zone de travail commence à partir de w. Comparer avec l'algorithme de fusion standard donné dans la plupart des manuels, celui-ci échange le contenu entre le sous-tableau trié et la zone de travail. Par conséquent, la zone de travail précédente contient les éléments triés fusionnés, tandis que les éléments précédents stockés dans la zone de travail sont déplacés vers les deux sous-tableaux.

Cependant, deux contraintes doivent être satisfaites:

  1. La zone de travail doit être dans les limites du tableau. En d'autres termes, il doit être suffisamment grand pour contenir les éléments échangés sans provoquer d'erreur hors limites.
  2. La zone de travail peut être chevauchée avec l'un des deux tableaux triés; cependant, il doit garantir qu'aucun des éléments non fusionnés n'est écrasé.

Avec cet algorithme de fusion défini, il est facile d'imaginer une solution, qui peut trier la moitié du tableau; La question suivante est de savoir comment traiter le reste de la partie non triée stockée dans la zone de travail, comme indiqué ci-dessous:

... unsorted 1/2 array ... | ... sorted 1/2 array ...

Une idée intuitive est de trier récursivement une autre moitié de la zone de travail, il n'y a donc que 1/4 des éléments qui n'ont pas encore été triés.

... unsorted 1/4 array ... | sorted 1/4 array B | sorted 1/2 array A ...

Le point clé à ce stade est que nous devons fusionner les 1/4 éléments triés B avec les 1/2 éléments triés A tôt ou tard.

La zone de travail reste-t-elle, qui ne contient que 1/4 des éléments, assez grande pour fusionner A et B? Ce n'est malheureusement pas le cas.

Cependant, la deuxième contrainte mentionnée ci-dessus nous donne un indice, que nous pouvons l'exploiter en arrangeant la zone de travail pour qu'elle se chevauche avec l'un ou l'autre sous-tableau si nous pouvons garantir la séquence de fusion que les éléments non fusionnés ne seront pas écrasés.

En fait, au lieu de trier la seconde moitié de la zone de travail, nous pouvons trier la première moitié et placer la zone de travail entre les deux tableaux triés comme ceci:

... sorted 1/4 array B | unsorted work area | ... sorted 1/2 array A ...

Cette configuration organise efficacement le chevauchement de la zone de travail avec le sous-réseau A. Cette idée est proposée dans [Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola. `` Mergesort pratique sur place ''. Nordic Journal of Computing, 1996].

Donc, la seule chose qui reste est de répéter l'étape ci-dessus, ce qui réduit la zone de travail de 1/2, 1/4, 1/8,… Lorsque la zone de travail devient suffisamment petite (par exemple, il ne reste que deux éléments), nous pouvons passer à un tri d'insertion trivial pour terminer cet algorithme.

Voici l'implémentation en ANSI C basée sur cet article.

void imsort(Key* xs, int l, int u);

void swap(Key* xs, int i, int j) {
    Key tmp = xs[i]; xs[i] = xs[j]; xs[j] = tmp;
}

/* 
 * sort xs[l, u), and put result to working area w. 
 * constraint, len(w) == u - l
 */
void wsort(Key* xs, int l, int u, int w) {
    int m;
    if (u - l > 1) {
        m = l + (u - l) / 2;
        imsort(xs, l, m);
        imsort(xs, m, u);
        wmerge(xs, l, m, m, u, w);
    }
    else
        while (l < u)
            swap(xs, l++, w++);
}

void imsort(Key* xs, int l, int u) {
    int m, n, w;
    if (u - l > 1) {
        m = l + (u - l) / 2;
        w = l + u - m;
        wsort(xs, l, m, w); /* the last half contains sorted elements */
        while (w - l > 2) {
            n = w;
            w = l + (n - l + 1) / 2;
            wsort(xs, w, n, l);  /* the first half of the previous working area contains sorted elements */
            wmerge(xs, l, l + n - w, n, u, w);
        }
        for (n = w; n > l; --n) /*switch to insertion sort*/
            for (m = n; m < u && xs[m] < xs[m-1]; ++m)
                swap(xs, m, m - 1);
    }
}

Où wmerge est défini précédemment.

Le code source complet se trouve ici et l'explication détaillée se trouve ici

Soit dit en passant, cette version n'est pas le tri de fusion le plus rapide car elle nécessite plus d'opérations de swap. Selon mon test, c'est plus rapide que la version standard, qui alloue des espaces supplémentaires à chaque récursivité. Mais c'est plus lent que la version optimisée, qui double à l'avance le tableau d'origine et l'utilise pour une fusion ultérieure.

Larry LIU Xinyu
la source
6
Knuth left this as an exercise (Vol 3, 5.2.5).fait référence à ex. 13. [40] Implémentez la méthode de tri interne suggérée [à la fin de cette section], produisant qui trie les données aléatoires en O (N) unités de temps avec seulement O (sqrt (N)) emplacements de mémoire supplémentaires. ? ( 40 indiquant un problème assez difficile ou long qui peut peut-être convenir comme projet à terme dans des situations de classe. )
greybeard
4
Je pense que la complexité temporelle de l'algorithme sur place mentionné dans le site penguin.ew est O (log n * n ^ 2) .Puisque nous avons log n fusionne et chaque fusion est de l'ordre O (n ^ 2). N'est-ce pas vrai?
code4fun
1
Cet algorithme est-il toujours stable et en n log n temps?
Paul Stelian du
1
@PaulStelian - ce n'est pas stable. Les éléments de la zone de travail sont réorganisés en fonction des opérations de commande sur les éléments de la zone triée. Cela signifie que les éléments de la zone de travail avec des valeurs égales seront réorganisés afin qu'ils ne soient plus dans leur ordre d'origine.
rcgldr
1
@PaulStelian - Wiki a un article pour le tri par fusion de blocs , qui, comme vous l'avez commenté, est stable. Cela fonctionne mieux s'il y a au moins 2 · sqrt (n) valeurs uniques, ce qui leur permet d'être réorganisées pour fournir des zones de travail d'un tableau et rester stables.
rcgldr
59

Incluant son "grand résultat", cet article décrit quelques variantes du tri par fusion sur place (PDF):

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=pdf

Tri sur place avec moins de mouvements

Jyrki Katajainen, Tomi A. Pasanen

Il est montré qu'un tableau de n éléments peut être trié en utilisant O (1) espace supplémentaire, O (n log n / log log n) mouvements et n log 2 n + O (n log log n) comparaisons. Il s'agit du premier algorithme de tri sur place nécessitant o (n log n) mouvements dans le pire des cas tout en garantissant des comparaisons O (n log n), mais en raison des facteurs constants impliqués, l'algorithme est principalement d'intérêt théorique.

Je pense que cela est également pertinent. J'en ai une copie imprimée qui m'a été remise par un collègue, mais je ne l'ai pas lue. Il semble couvrir la théorie de base, mais je ne connais pas suffisamment le sujet pour juger de manière exhaustive:

http://comjnl.oxfordjournals.org/cgi/content/abstract/38/8/681

Fusion stable optimale

Antonios Symvonis

Cet article montre comment fusionner de manière stable deux séquences A et B de tailles m et n, m ≤ n, respectivement, avec des affectations O (m + n), O (mlog (n / m + 1)) et en utilisant uniquement une constante quantité d'espace supplémentaire. Ce résultat correspond à toutes les bornes inférieures connues ...

Steve Jessop
la source
12

Ce n'est vraiment pas facile ou efficace, et je vous suggère de ne pas le faire à moins que vous ne deviez vraiment le faire (et vous n'avez probablement pas à le faire à moins que ce ne soit des devoirs puisque les applications de la fusion sur place sont principalement théoriques). Vous ne pouvez pas utiliser quicksort à la place? Quicksort sera de toute façon plus rapide avec quelques optimisations plus simples et sa mémoire supplémentaire est O (log N) .

Quoi qu'il en soit, si vous devez le faire, vous devez. Voici ce que j'ai trouvé: un et deux . Je ne connais pas le tri par fusion interne, mais il semble que l'idée de base consiste à utiliser des rotations pour faciliter la fusion de deux tableaux sans utiliser de mémoire supplémentaire.

Notez que cela est même plus lent que le tri de fusion classique qui n'est pas en place.

IVlad
la source
9
Quicksort n'est pas stable. Cela compte vraiment pour beaucoup de code de production.
Donal Fellows
7
quicksort peut être stable, et le tri de fusion iirc n'est pas nécessairement stable s'il est en place
jk.
4
@jk: Quicksort n'est pas stable; c'est la vitesse qui en découle et vous ne devriez pas essayer de prétendre le contraire. C'est un très bon compromis. Oui, il est possible d'associer l'index d'origine au reste de la clé afin que vous n'ayez jamais deux éléments identiques, donnant un tri stable; cela a un coût nécessaire d'espace supplémentaire (linéaire dans le nombre d'éléments) car vous ne pouvez pas maintenir l'ordre relatif des éléments «équivalents» sans avoir recours à des mouvements d'éléments supplémentaires qui détruisent les performances.
Donal Fellows
4
Quicksort a également un pire cas O (n ^ 2) pour une entrée spécialement conçue
HoboBen
4
@DonalFellows: jk a exactement raison; quicksort PEUT être implémenté pour être stable, sans coût d'espace supplémentaire. Consultez Wikipedia.
Rusty
10

L'étape critique consiste à mettre en place la fusion elle-même. Ce n'est pas aussi difficile que le disent ces sources, mais vous perdez quelque chose lorsque vous essayez.

En regardant une étape de la fusion:

[... liste triée ... | x ... liste- A ... | y ... liste- B ...]

Nous savons que la Sorted séquence est inférieure à tout le reste, que x est inférieur à tout le reste en A , et que y est inférieur à tout le reste en B . Dans le cas où x est inférieur ou égal à y , il vous suffit de déplacer votre pointeur vers le début de A sur un. Dans le cas où y est inférieur à x , vous devez mélanger y après l'ensemble de A pour trier . C'est cette dernière étape qui fait que cela coûte cher (sauf dans les cas dégénérés).

Il est généralement moins cher (en particulier lorsque les tableaux ne contiennent en fait que des mots uniques par élément, par exemple, un pointeur vers une chaîne ou une structure) pour échanger de l'espace pour le temps et avoir un tableau temporaire séparé que vous triez dans les deux sens.

Associés Donal
la source
5
Votre fusion sur place a la complexité O (m n) dans le pire des cas, où m est une taille A et n est une taille B. C'est le cas lorsque le premier élément de A est plus grand que le dernier élément de B. La complexité peut être améliorée à O (k log (k) + m + n), où k = min (m, n) en ajoutant un tas entre A et B. Ce tas doit contenir des éléments de A, qui sont plus grands que les éléments restants dans B, mais plus petits que les éléments restants dans A. Si A est épuisé en premier, alors le tas doit être déplacé à la fin de B. Sinon, le segment de mémoire doit être déplacé au début de A. Ensuite, les éléments de segment de mémoire doivent être extraits en place et inversés pour terminer la fusion.
valyala
2
@valyala Notez que lorsque vous utilisez un tas, le tri n'est plus stable. De plus, si vous utilisez un segment de mémoire, vous pouvez utiliser le tri par segment de mémoire au lieu du tri par fusion.
martinkunev
4

Un exemple de fusion sans tampon en C.

#define SWAP(type, a, b) \
    do { type t=(a);(a)=(b);(b)=t; } while (0)

static void reverse_(int* a, int* b)
{
    for ( --b; a < b; a++, b-- )
       SWAP(int, *a, *b);
}
static int* rotate_(int* a, int* b, int* c)
/* swap the sequence [a,b) with [b,c). */
{
    if (a != b && b != c)
     {
       reverse_(a, b);
       reverse_(b, c);
       reverse_(a, c);
     }
    return a + (c - b);
}

static int* lower_bound_(int* a, int* b, const int key)
/* find first element not less than @p key in sorted sequence or end of
 * sequence (@p b) if not found. */
{
    int i;
    for ( i = b-a; i != 0; i /= 2 )
     {
       int* mid = a + i/2;
       if (*mid < key)
          a = mid + 1, i--;
     }
    return a;
}
static int* upper_bound_(int* a, int* b, const int key)
/* find first element greater than @p key in sorted sequence or end of
 * sequence (@p b) if not found. */
{
    int i;
    for ( i = b-a; i != 0; i /= 2 )
     {
       int* mid = a + i/2;
       if (*mid <= key)
          a = mid + 1, i--;
     }
    return a;
}

static void ip_merge_(int* a, int* b, int* c)
/* inplace merge. */
{
    int n1 = b - a;
    int n2 = c - b;

    if (n1 == 0 || n2 == 0)
       return;
    if (n1 == 1 && n2 == 1)
     {
       if (*b < *a)
          SWAP(int, *a, *b);
     }
    else
     {
       int* p, * q;

       if (n1 <= n2)
          p = upper_bound_(a, b, *(q = b+n2/2));
       else
          q = lower_bound_(b, c, *(p = a+n1/2));
       b = rotate_(p, b, q);

       ip_merge_(a, p, b);
       ip_merge_(b, q, c);
     }
}

void mergesort(int* v, int n)
{
    if (n > 1)
     {
       int h = n/2;
       mergesort(v, h); mergesort(v+h, n-h);
       ip_merge_(v, v+h, v+n);
     }
}

Un exemple de fusion adaptative (optimisé).

Ajoute du code de support et des modifications pour accélérer la fusion lorsqu'un tampon auxiliaire de n'importe quelle taille est disponible (fonctionne toujours sans mémoire supplémentaire). Utilise la fusion avant et arrière, la rotation en anneau, la fusion et le tri de petites séquences et la fusion itérative.

#include <stdlib.h>
#include <string.h>

static int* copy_(const int* a, const int* b, int* out)
{
    int count = b - a;
    if (a != out)
       memcpy(out, a, count*sizeof(int));
    return out + count;
}
static int* copy_backward_(const int* a, const int* b, int* out)
{
    int count = b - a;
    if (b != out)
       memmove(out - count, a, count*sizeof(int));
    return out - count;
}

static int* merge_(const int* a1, const int* b1, const int* a2,
  const int* b2, int* out)
{
    while ( a1 != b1 && a2 != b2 )
       *out++ = (*a1 <= *a2) ? *a1++ : *a2++;
    return copy_(a2, b2, copy_(a1, b1, out));
}
static int* merge_backward_(const int* a1, const int* b1,
  const int* a2, const int* b2, int* out)
{
    while ( a1 != b1 && a2 != b2 )
       *--out = (*(b1-1) > *(b2-1)) ? *--b1 : *--b2;
    return copy_backward_(a1, b1, copy_backward_(a2, b2, out));
}

static unsigned int gcd_(unsigned int m, unsigned int n)
{
    while ( n != 0 )
     {
       unsigned int t = m % n;
       m = n;
       n = t;
     }
    return m;
}
static void rotate_inner_(const int length, const int stride,
  int* first, int* last)
{
    int* p, * next = first, x = *first;
    while ( 1 )
     {
       p = next;
       if ((next += stride) >= last)
          next -= length;
       if (next == first)
          break;
       *p = *next;
     }
    *p = x;
}
static int* rotate_(int* a, int* b, int* c)
/* swap the sequence [a,b) with [b,c). */
{
    if (a != b && b != c)
     {
       int n1 = c - a;
       int n2 = b - a;

       int* i = a;
       int* j = a + gcd_(n1, n2);

       for ( ; i != j; i++ )
          rotate_inner_(n1, n2, i, c);
     }
    return a + (c - b);
}

static void ip_merge_small_(int* a, int* b, int* c)
/* inplace merge.
 * @note faster for small sequences. */
{
    while ( a != b && b != c )
       if (*a <= *b)
          a++;
       else
        {
          int* p = b+1;
          while ( p != c && *p < *a )
             p++;
          rotate_(a, b, p);
          b = p;
        }
}
static void ip_merge_(int* a, int* b, int* c, int* t, const int ts)
/* inplace merge.
 * @note works with or without additional memory. */
{
    int n1 = b - a;
    int n2 = c - b;

    if (n1 <= n2 && n1 <= ts)
     {
       merge_(t, copy_(a, b, t), b, c, a);
     }
    else if (n2 <= ts)
     {
       merge_backward_(a, b, t, copy_(b, c, t), c);
     }
    /* merge without buffer. */
    else if (n1 + n2 < 48)
     {
       ip_merge_small_(a, b, c);
     }
    else
     {
       int* p, * q;

       if (n1 <= n2)
          p = upper_bound_(a, b, *(q = b+n2/2));
       else
          q = lower_bound_(b, c, *(p = a+n1/2));
       b = rotate_(p, b, q);

       ip_merge_(a, p, b, t, ts);
       ip_merge_(b, q, c, t, ts);
     }
}
static void ip_merge_chunk_(const int cs, int* a, int* b, int* t,
  const int ts)
{
    int* p = a + cs*2;
    for ( ; p <= b; a = p, p += cs*2 )
       ip_merge_(a, a+cs, p, t, ts);
    if (a+cs < b)
       ip_merge_(a, a+cs, b, t, ts);
}

static void smallsort_(int* a, int* b)
/* insertion sort.
 * @note any stable sort with low setup cost will do. */
{
    int* p, * q;
    for ( p = a+1; p < b; p++ )
     {
       int x = *p;
       for ( q = p; a < q && x < *(q-1); q-- )
          *q = *(q-1);
       *q = x;
     }
}
static void smallsort_chunk_(const int cs, int* a, int* b)
{
    int* p = a + cs;
    for ( ; p <= b; a = p, p += cs )
       smallsort_(a, p);
    smallsort_(a, b);
}

static void mergesort_lower_(int* v, int n, int* t, const int ts)
{
    int cs = 16;
    smallsort_chunk_(cs, v, v+n);
    for ( ; cs < n; cs *= 2 )
       ip_merge_chunk_(cs, v, v+n, t, ts);
}

static void* get_buffer_(int size, int* final)
{
    void* p = NULL;
    while ( size != 0 && (p = malloc(size)) == NULL )
       size /= 2;
    *final = size;
    return p;
}
void mergesort(int* v, int n)
{
    /* @note buffer size may be in the range [0,(n+1)/2]. */
    int request = (n+1)/2 * sizeof(int);
    int actual;
    int* t = (int*) get_buffer_(request, &actual);

    /* @note allocation failure okay. */
    int tsize = actual / sizeof(int);
    mergesort_lower_(v, n, t, tsize);
    free(t);
}
Johnny Cage
la source
2
Tu as écrit ça? Comment surmonte-t-il les difficultés exprimées dans les autres réponses? Quelle est sa durée de fonctionnement?
Thomas Ahle
Ceci est adapté de ma propre bibliothèque personnalisée , mais je n'ai pas créé ces algorithmes si c'est ce que vous demandez. La croissance est O (n (log n) ^ 2) sans mémoire auxiliaire; O (n log n) avec tampon complet. Cela tente d'être une implémentation pratique et est structuré pour montrer les algorithmes constitutifs.
Johnny Cage
Pourquoi avez-vous besoin d'une récursivité ou d'un tampon supplémentaire pour fusionner deux listes triées? Je pense que cela peut être fait en déplaçant les deux pointeurs vers l'avant et en les échangeant si la gauche est plus grande que la droite.
jack
3

Cette réponse contient un exemple de code qui implémente l'algorithme décrit dans l'article Practical In-Place Merging par Bing-Chao Huang et Michael A. Langston. Je dois admettre que je ne comprends pas les détails, mais la complexité donnée de l'étape de fusion est O (n).

D'un point de vue pratique, il est prouvé que les implémentations pures sur place ne fonctionnent pas mieux dans des scénarios du monde réel. Par exemple, la norme C ++ définit std :: inplace_merge , qui est comme son nom l'indique une opération de fusion sur place.

En supposant que les bibliothèques C ++ sont généralement très bien optimisées, il est intéressant de voir comment elles sont implémentées:

1) libstdc ++ (partie de la base de code GCC): std :: inplace_merge

L'implémentation délègue à __inplace_merge , ce qui évite le problème en essayant d'allouer un tampon temporaire:

typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
_TmpBuf __buf(__first, __len1 + __len2);

if (__buf.begin() == 0)
  std::__merge_without_buffer
    (__first, __middle, __last, __len1, __len2, __comp);
else
  std::__merge_adaptive
   (__first, __middle, __last, __len1, __len2, __buf.begin(),
     _DistanceType(__buf.size()), __comp);

Sinon, il revient à une implémentation ( __merge_without_buffer ), qui ne nécessite pas de mémoire supplémentaire, mais ne s'exécute plus en temps O (n).

2) libc ++ (partie de la base de code Clang): std :: inplace_merge

Ressemble similaire. Il délègue à une fonction , qui essaie également d' allouer un tampon . Selon qu'il aura suffisamment d'éléments, il choisira l'implémentation. La fonction de secours à mémoire constante est appelée __buffered_inplace_merge .

Peut-être que même la solution de rechange est toujours O (n), mais le fait est qu'ils n'utilisent pas l'implémentation si de la mémoire temporaire est disponible.


Notez que la norme C ++ donne explicitement aux implémentations la liberté de choisir cette approche en réduisant la complexité requise de O (n) à O (N log N):

Complexité: comparaisons exactes N-1 si suffisamment de mémoire supplémentaire est disponible. Si la mémoire est insuffisante, comparaisons O (N log N).

Bien sûr, cela ne peut pas être considéré comme une preuve que l'espace constant en place fusionne en temps O (n) ne doit jamais être utilisé. D'un autre côté, si c'était plus rapide, les bibliothèques C ++ optimisées passeraient probablement à ce type d'implémentation.

Philipp Claßen
la source
2

Voici ma version C:

void mergesort(int *a, int len) {
  int temp, listsize, xsize;

  for (listsize = 1; listsize <= len; listsize*=2) {
    for (int i = 0, j = listsize; (j+listsize) <= len; i += (listsize*2), j += (listsize*2)) {
      merge(& a[i], listsize, listsize);
    }
  }

  listsize /= 2;

  xsize = len % listsize;
  if (xsize > 1)
    mergesort(& a[len-xsize], xsize);

  merge(a, listsize, xsize);
}

void merge(int *a, int sizei, int sizej) {
  int temp;
  int ii = 0;
  int ji = sizei;
  int flength = sizei+sizej;

  for (int f = 0; f < (flength-1); f++) {
    if (sizei == 0 || sizej == 0)
      break;

    if (a[ii] < a[ji]) {
      ii++;
      sizei--;
    }
    else {
      temp = a[ji];

      for (int z = (ji-1); z >= ii; z--)
        a[z+1] = a[z];  
      ii++;

      a[f] = temp;

      ji++;
      sizej--;
    }
  }
}
Dylan Nissley
la source
Notez que cette implémentation prend Θ (n ^ 2 log n) dans le pire des cas (tableau inversé).
martinkunev
1

Il existe une implémentation relativement simple du tri par fusion sur place utilisant la technique originale de Kronrod mais avec une implémentation plus simple. Un exemple illustré qui illustre cette technique peut être trouvé ici: http://www.logiccoder.com/TheSortProblem/BestMergeInfo.htm .

Il existe également des liens vers une analyse théorique plus détaillée du même auteur associée à ce lien.

Calbert
la source
ce lien se traduit par un 403
Charlotte Tan
3
Le lien est fixe. La documentation y est cryptique au point d'être obtus. J'ai l'impression qu'il y a là une idée intéressante, mais aucun algorithme n'est présenté, juste un ensemble de diagrammes et quelques descriptions plutôt faibles. Je n'ai pas pu lier les descriptions faibles aux diagrammes de manière intéressante, alors j'ai abandonné.
Ira Baxter
-6

Je viens d'essayer l'algorithme de fusion sur place pour le tri par fusion dans JAVA en utilisant l'algorithme de tri par insertion, en suivant les étapes suivantes.
1) Deux tableaux triés sont disponibles.
2) Comparez les premières valeurs de chaque tableau; et placez la plus petite valeur dans le premier tableau.
3) Placez la plus grande valeur dans le deuxième tableau en utilisant le tri par insertion (traversée de gauche à droite).
4) Comparez à nouveau la deuxième valeur du premier tableau et la première valeur du deuxième tableau, et faites de même. Mais lorsque l'échange se produit, il est possible de ne pas comparer les autres éléments, mais simplement l'échange requis.

J'ai fait une optimisation ici; pour conserver des comparaisons moindres dans le tri par insertion.
Le seul inconvénient que j'ai trouvé avec cette solution est qu'elle nécessite un échange plus important des éléments du tableau dans le deuxième tableau.

par exemple)

First___Array: 3, 7, 8, 9

Deuxième tableau: 1, 2, 4, 5

Ensuite, 7, 8, 9 oblige le second tableau à échanger (déplacer à gauche d'un) tous ses éléments un à chaque fois pour se placer dans le dernier.

Donc, l'hypothèse ici est que l'échange d'articles est négligeable par rapport à la comparaison de deux articles.

https://github.com/skanagavelu/algorithams/blob/master/src/sorting/MergeSort.java

package sorting;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
    int[] array = { 5, 6, 10, 3, 9, 2, 12, 1, 8, 7 };
    mergeSort(array, 0, array.length -1);
    System.out.println(Arrays.toString(array));

    int[] array1 = {4, 7, 2};
    System.out.println(Arrays.toString(array1));
    mergeSort(array1, 0, array1.length -1);
    System.out.println(Arrays.toString(array1));
    System.out.println("\n\n");

    int[] array2 = {4, 7, 9};
    System.out.println(Arrays.toString(array2));
    mergeSort(array2, 0, array2.length -1);
    System.out.println(Arrays.toString(array2));
    System.out.println("\n\n");

    int[] array3 = {4, 7, 5};
    System.out.println(Arrays.toString(array3));
    mergeSort(array3, 0, array3.length -1);
    System.out.println(Arrays.toString(array3));
    System.out.println("\n\n");

    int[] array4 = {7, 4, 2};
    System.out.println(Arrays.toString(array4));
    mergeSort(array4, 0, array4.length -1);
    System.out.println(Arrays.toString(array4));
    System.out.println("\n\n");

    int[] array5 = {7, 4, 9};
    System.out.println(Arrays.toString(array5));
    mergeSort(array5, 0, array5.length -1);
    System.out.println(Arrays.toString(array5));
    System.out.println("\n\n");

    int[] array6 = {7, 4, 5};
    System.out.println(Arrays.toString(array6));
    mergeSort(array6, 0, array6.length -1);
    System.out.println(Arrays.toString(array6));
    System.out.println("\n\n");

    //Handling array of size two
    int[] array7 = {7, 4};
    System.out.println(Arrays.toString(array7));
    mergeSort(array7, 0, array7.length -1);
    System.out.println(Arrays.toString(array7));
    System.out.println("\n\n");

    int input1[] = {1};
    int input2[] = {4,2};
    int input3[] = {6,2,9};
    int input4[] = {6,-1,10,4,11,14,19,12,18};
    System.out.println(Arrays.toString(input1));
    mergeSort(input1, 0, input1.length-1);
    System.out.println(Arrays.toString(input1));
    System.out.println("\n\n");

    System.out.println(Arrays.toString(input2));
    mergeSort(input2, 0, input2.length-1);
    System.out.println(Arrays.toString(input2));
    System.out.println("\n\n");

    System.out.println(Arrays.toString(input3));
    mergeSort(input3, 0, input3.length-1);
    System.out.println(Arrays.toString(input3));
    System.out.println("\n\n");

    System.out.println(Arrays.toString(input4));
    mergeSort(input4, 0, input4.length-1);
    System.out.println(Arrays.toString(input4));
    System.out.println("\n\n");
}

private static void mergeSort(int[] array, int p, int r) {
    //Both below mid finding is fine.
    int mid = (r - p)/2 + p;
    int mid1 = (r + p)/2;
    if(mid != mid1) {
        System.out.println(" Mid is mismatching:" + mid + "/" + mid1+ "  for p:"+p+"  r:"+r);
    }

    if(p < r) {
        mergeSort(array, p, mid);
        mergeSort(array, mid+1, r);
//      merge(array, p, mid, r);
        inPlaceMerge(array, p, mid, r);
        }
    }

//Regular merge
private static void merge(int[] array, int p, int mid, int r) {
    int lengthOfLeftArray = mid - p + 1; // This is important to add +1.
    int lengthOfRightArray = r - mid;

    int[] left = new int[lengthOfLeftArray];
    int[] right = new int[lengthOfRightArray];

    for(int i = p, j = 0; i <= mid; ){
        left[j++] = array[i++];
    }

    for(int i = mid + 1, j = 0; i <= r; ){
        right[j++] = array[i++];
    }

    int i = 0, j = 0;
    for(; i < left.length && j < right.length; ) {
        if(left[i] < right[j]){
            array[p++] = left[i++];
        } else {
            array[p++] = right[j++];
        }
    }
    while(j < right.length){
        array[p++] = right[j++];
    } 
    while(i < left.length){
        array[p++] = left[i++];
    }
}

//InPlaceMerge no extra array
private static void inPlaceMerge(int[] array, int p, int mid, int r) {
    int secondArrayStart = mid+1;
    int prevPlaced = mid+1;
    int q = mid+1;
    while(p < mid+1 && q <= r){
        boolean swapped = false;
        if(array[p] > array[q]) {
            swap(array, p, q);
            swapped = true;
        }   
        if(q != secondArrayStart && array[p] > array[secondArrayStart]) {
            swap(array, p, secondArrayStart);
            swapped = true;
        }
        //Check swapped value is in right place of second sorted array
        if(swapped && secondArrayStart+1 <= r && array[secondArrayStart+1] < array[secondArrayStart]) {
            prevPlaced = placeInOrder(array, secondArrayStart, prevPlaced);
        }
        p++;
        if(q < r) {     //q+1 <= r) {
            q++;
        }
    }
}

private static int placeInOrder(int[] array, int secondArrayStart, int prevPlaced) {
    int i = secondArrayStart;
    for(; i < array.length; i++) {
        //Simply swap till the prevPlaced position
        if(secondArrayStart < prevPlaced) {
            swap(array, secondArrayStart, secondArrayStart+1);
            secondArrayStart++;
            continue;
        }
        if(array[i] < array[secondArrayStart]) {
            swap(array, i, secondArrayStart);
            secondArrayStart++;
        } else if(i != secondArrayStart && array[i] > array[secondArrayStart]){
            break;
        }
    }
    return secondArrayStart;
}

private static void swap(int[] array, int m, int n){
    int temp = array[m];
    array[m] = array[n];
    array[n] = temp;
}
}
Kanagavelu Sugumar
la source
3
C'est à la fois O (n ^ 2) et également très illisible (en raison d'erreurs de syntaxe occasionnelles et d'un style incohérent / médiocre)
glaba