Le tri par fusion est un algorithme de tri qui fonctionne en divisant une liste donnée en deux, en triant récursivement les deux listes plus petites et en les fusionnant à nouveau dans une liste triée. Le cas de base de la récursivité arrive à une liste singleton, qui ne peut pas être divisée davantage mais qui est par définition déjà triée.

L'exécution de l'algorithme sur la liste [1,7,6,3,3,2,5]peut être visualisée de la manière suivante:

       [1,7,6,3,3,2,5]
       /             \      split
   [1,7,6,3]       [3,2,5]
    /     \        /    \   split
 [1,7]   [6,3]   [3,2]  [5]
 /   \   /   \   /   \   |  split
[1] [7] [6] [3] [3] [2] [5]
 \   /   \   /   \   /   |  merge
 [1,7]   [3,6]   [2,3]  [5]
    \     /         \   /   merge
   [1,3,6,7]       [2,3,5]
       \             /      merge
       [1,2,3,3,5,6,7]

La tâche

Écrivez un programme ou une fonction qui prend une liste d'entiers de manière raisonnable en entrée et visualise les différentes partitions de cette liste tout en étant triée par un algorithme de tri par fusion. Cela signifie que vous n'avez pas besoin de générer un graphique comme ci-dessus, mais juste les listes sont bien:

[1,7,6,3,3,2,5]
[1,7,6,3][3,2,5]
[1,7][6,3][3,2][5]
[1][7][6][3][3][2][5]
[1,7][3,6][2,3][5]
[1,3,6,7][2,3,5]
[1,2,3,3,5,6,7]

De plus, toute notation de liste raisonnable est très bien, donc ce qui suit serait également une sortie valide:

1 7 6 3 3 2 5
1 7 6 3|3 2 5
1 7|6 3|3 2|5
1|7|6|3|3|2|5
1 7|3 6|2 3|5
1 3 6 7|2 3 5
1 2 3 3 5 6 7

Enfin, la façon de diviser une liste en deux listes plus petites vous appartient tant que la longueur des deux listes résultantes diffère au maximum d'une unité. Cela signifie qu'au lieu de diviser [3,2,4,3,7]en [3,2,4]et [3,7], vous pouvez également diviser en prenant des éléments à des index pairs et impairs ( [3,4,7]et [2,3]) ou même randomiser la division à chaque fois.

C'est le code-golf , donc le code le plus court dans n'importe quelle langue, mesuré en octets, gagne.

Cas de test

Comme indiqué ci-dessus, le format réel et la façon de diviser les listes en deux sont à vous.

[10,2]
[10][2]
[2,10]

[4,17,1,32]
[4,17][1,32]
[4][17][1][32]
[4,17][1,32]
[1,4,17,32]

[6,5,4,3,2,1]
[6,5,4][3,2,1]
[6,5][4][3,2][1]
[6][5][4][3][2][1]
[5,6][4][2,3][1] <- Important: This step cannot be [5,6][3,4][1,2], because 3 and 4 are on different branches in the the tree
[4,5,6][1,2,3]
[1,2,3,4,5,6]

Haskell , 137 128 127 125 121 109 106 octets

^{(-2) + (- 4) = (- 6) octets grâce à nimi ! Le modifier pour collecter toutes les étapes d'une liste (à nouveau en raison de nimi) permet d'économiser 12 octets supplémentaires.}

^{Encore 3 octets dus à Laikoni , avec une liaison de garde de modèle et une utilisation intelligente de la compréhension de liste pour coder la garde.}

import Data.List
g x|y<-x>>=h=x:[z|x/=y,z<-g y++[sort<$>x]]
h[a]=[[a]]
h x=foldr(\x[b,a]->[x:a,b])[[],[]]x

Essayez-le en ligne!

Le fractionnement des listes en éléments impairs et pairs est un code plus court qu'en deux moitiés séquentielles, car nous sommes épargnés d'avoir à mesurer le length, alors.

Fonctionne en "imprimant" les listes, puis en répétant avec les listes de partage ( x >>= h) s'il y a effectivement eu un fractionnement, et en "imprimant" les listes triées; en commençant par la seule liste d'entrée; en supposant l'entrée non vide. Et au lieu de l'impression réelle, il suffit de les rassembler dans une liste.

La liste produite par g[[6,5..1]], imprimée ligne par ligne, est la suivante:

[[6,5,4,3,2,1]]
[[6,4,2],[5,3,1]]
[[6,2],[4],[5,1],[3]]
[[6],[2],[4],[5],[1],[3]]
[[2,6],[4],[1,5],[3]]
[[2,4,6],[1,3,5]]
[[1,2,3,4,5,6]]

Wolfram Language (Mathematica) , 146 127 111 111 102 octets

Join[u=Most[#/.a:{_,b=__Integer}:>TakeDrop[a,;;;;2]&~FixedPointList~#],Reverse@Most@u/.a:{b}:>Sort@a]&

Essayez-le en ligne!

Renvoie un Listqui contient les étapes.

Explication

#/.a:{_,b=__Integer}:>TakeDrop[a,;;;;2]&

Dans une entrée, divisez tous les Lists contenant 2 ou plusieurs entiers en deux. La première sous-liste contient les éléments indexés impairs (indexés 1) et la seconde les éléments indexés pairs.

u=Most[... &~FixedPointList~#]

Répétez cela jusqu'à ce que rien ne change (c'est-à-dire que toutes les sous-listes sont de longueur 1). Conservez tous les résultats intermédiaires. Stockez-le (le Listde toutes les étapes) dans u.

Reverse@Most@u

Déposez le dernier élément de uet inversez-le.

... /.a:{b}:>Sort@a

À partir du résultat ci-dessus, triez toutes les occurrences d'une liste d'entiers.

Nettoyer , 228 206 168 157 157 140 121 104 octets

Construit la liste des étapes à partir des extrémités, en utilisant le fait que l' nélément -th à partir de la fin est la version triée de l' nélément -th depuis le début.

Idée du commentaire de JungHwan Min

import StdEnv
@u#(a,b)=splitAt(length u/2)u
=if(a>[])[[u]:[x++y\\y<- @b&x<- @a++ @a++ @a]][]++[[sort u]]

Essayez-le en ligne!

Charbon de bois , 145 133 123 122 octets

≔⟦⪪Ｓ ⟧θＷ⊖Ｌ§θ⁰«⟦⪫Ｅθ⪫κ ¦|⟧≔ＥＥ⊗Ｌθ§θ÷λ²✂κ﹪λ²Ｌκ²θ»⟦⪫ΦＥθ⪫ι ι|⟧Ｗ⊖Ｌθ«≔⮌θη≔⟦⟧θＷη«≔⊟ηε≔⟦⟧ζＦ⊟η«≔εδ≔⟦⟧εＦδ⊞⎇‹ＩμＩλζεμ⊞ζλ»⊞θ⁺ζε»⟦⪫Ｅθ⪫κ ¦|

Essayez-le en ligne! Le lien est vers la version détaillée du code. Toujours à contourner les bugs de charbon de bois ... Edit: sauvé 5 octets en utilisant un double Mapcomme compréhension de tableau d'un pauvre. Enregistré 4 octets en utilisant Poppour double itérer sur un tableau. Enregistré 3 octets en utilisant la concaténation au lieu de Push. Économisé 10 octets en proposant une whilecondition de golfeur qui évite également un bug de charbon de bois. Économisé 1 octet en découvrant que Charcoal a effectivement un opérateur de filtre. Explication:

≔⟦⪪Ｓ ⟧θ

Divisez l'entrée sur des espaces, puis encapsulez le résultat dans un tableau externe, en l'enregistrant q.

Ｗ⊖Ｌ§θ⁰«

Répétez l'opération alors que le premier élément de qpossède plusieurs éléments. (Le premier élément de qcontient toujours le plus d'éléments en raison de la façon dont les listes sont divisées en deux.)

⟦⪫Ｅθ⪫κ ¦|⟧

Imprimez les éléments de qjointure avec des espaces et des lignes verticales. (Le tableau entraîne l'impression du résultat sur sa propre ligne. Il existe d'autres façons d'y parvenir pour le même nombre d'octets.)

≔ＥＥ⊗Ｌθ§θ÷λ²✂κ﹪λ²Ｌκ²θ»

Créez une liste en dupliquant chaque élément de q, puis mappez sur cette liste et prenez la moitié de chaque liste (en utilisant l'approche des éléments alternatifs), en enregistrant le résultat q.

⟦⪫ΦＥθ⪫ι ι|⟧

Imprimer les éléments de qjointure avec des espaces et des lignes verticales. En fait, à ce stade, les éléments de qsont des listes vides ou à un seul élément, donc les joindre les convertit simplement en chaînes vides ou en leurs éléments. Les chaînes vides ajouteraient des lignes de fin inutiles afin qu'elles soient filtrées. Un opérateur aplati aurait été plus golfeur (quelque chose comme ⟦⪫Σθ|⟧).

Ｗ⊖Ｌθ«

Répéter tout en qayant plusieurs éléments. (Le code suivant nécessite un nombre pair d'éléments.)

≔⮌θη≔⟦⟧θ

Copiez qdans h, mais inversé (voir ci-dessous) et réinitialisez-le qdans une liste vide.

Ｗη«

Répétez jusqu'à ce qu'il hsoit vide.

≔⊟ηε

Extrayez l'élément suivant de hinto e. ( Popextraits de la fin, c'est pourquoi je dois inverser q.)

≔⟦⟧ζ

Initialisez zsur une liste vide.

Ｆ⊟η«

Faites une boucle sur les éléments de l'élément suivant de h.

≔εδ≔⟦⟧ε

Copier eà det remettre eà une liste vide.

Ｆδ

Faites une boucle sur les éléments de d.

⊞⎇‹ＩμＩλζεμ

Poussez-les vers zou eselon qu'ils sont plus petits que l'élément actuel de l'élément suivant de h.

⊞ζλ»

Appuyez sur l'élément actuel de l'élément suivant de hto z.

⊞θ⁺ζε»

Concaténer zavec tous les éléments restants eet pousser q. Ceci termine la fusion de deux éléments de h.

⟦⪫Ｅθ⪫κ ¦|

Imprimer les éléments de qjointure avec des espaces et des lignes verticales.

Python 2 , 145 144 octets

^{Idée du commentaire de JungHwan Min
-1 octet grâce à Jonathan Frech}

p=input()
l=[[p]]
i=0
while 2**i<len(p):l[i+1:i+1]=[sum([[x[1::2],x[::2]][len(x)<2:]for x in l[i]],[]),map(sorted,l[i])];i+=1
for s in l:print s

Essayez-le en ligne!

JavaScript (ES6), 145 octets

f=a=>a.join`|`+(a[0][1]?`
${f([].concat(...a.map(b=>b[1]?[b.slice(0,c=-b.length/2),b.slice(c)]:[b])))}
`+a.map(b=>b.sort((x,y)=>x-y)).join`|`:``)

Prend l'entrée comme un tableau dans un tableau, c'est-à-dire f([[6,5,4,3,2,1]]). Fonctionne en générant les première et dernière lignes de la sortie, puis en se divisant et en se rappelant, jusqu'à ce que chaque sous-tableau ait une longueur 1. Voici une démonstration de base de son fonctionnement:

f([[6,5,4,3,2,1]]):
  6,5,4,3,2,1
  f([[6,5,4],[3,2,1]]):
    6,5,4|3,2,1
    f([[6,5],[4],[3,2],[1]]):
      6,5|4|3,2|1
      f([[6],[5],[4],[3],[2],[1]]):
        6|5|4|3|2|1
      end f
      5,6|4|2,3|1
    end f
    4,5,6|1,2,3
  end f
  1,2,3,4,5,6
end f

Husk , 14 octets

S+ȯ†O↔hUmfL¡ṁ½

Prend un tableau contenant un seul tableau. Essayez-le en ligne!

Explication

S+ȯ†O↔hUmfL¡ṁ½  Implicit input, say A = [[4,17,32,1]].
           ¡    Iterate this function on A:
            ṁ½   Split each array in two, concatenate results: [[4,17],[32,1]]
                Result is [[[4,17,32,1]],
                           [[4,17],[32,1]],
                           [[4],[17],[32],[1]],
                           [[4],[],[17],[],[32],[],[1],[]],
                           ...
        mfL     Map filter by length, removing empty arrays.
                Result is [[[4,17,32,1]],
                           [[4,17],[32,1]],
                           [[4],[17],[32],[1]],
                           [[4],[17],[32],[1]],
                           ...
       U        Longest prefix of unique elements:
                       P = [[[4,17,32,1]],[[4,17],[32,1]],[[4],[17],[32],[1]]]
      h         Remove last element: [[[4,17,32,1]],[[4,17],[32,1]]]
     ↔          Reverse: [[[4,17],[32,1]],[[4,17,32,1]]]
   †O           Sort each inner array: [[[4,17],[1,32]],[[1,4,17,32]]]
S+ȯ             Concatenate to P:
                           [[[4,17,32,1]],
                            [[4,17],[32,1]],
                            [[4],[17],[32],[1]],
                            [[4,17],[1,32]],
                            [[1,4,17,32]]]
                Implicitly print.

L'intégré ½prend un tableau et le divise au milieu. Si sa longueur est impaire, la première partie est plus longue d'un élément. Un tableau singleton [a]donne [[a],[]]et un tableau vide []donne [[],[]], il est donc nécessaire de supprimer les tableaux vides avant d'appliquer U.

Stax , 116 (÷ 3>) 38 29 octets ^CP437

-9 octets par commentaire de @recursive. Maintenant, l'entrée est donnée comme un singleton dont le seul élément est un tableau des nombres à trier.

ƒ3s}óºE/ßB╢↕êb∩áαπüµrL╞¶è,te+

Essayez-le en ligne!

Version non compressée avec 35 octets:

{c{Jm'|*Pc{2Mm:f{fc{Dm$wW{{eoJm'|*P

Explication

Le code peut être divisé en deux parties. La première partie visualise le fractionnement et la seconde visualise la fusion.

Code pour visualiser le fractionnement:

{                      w    Do the following while the block generates a true value
 c                          Copy current nested array for printing
  {Jm                       Use spaces to join elements in each part
     '|*                    And join different parts with vertical bar 
        P                   Pop and print

         c                  Copy current nested array for splitting
          {2Mm              Separate each element of the array to two smaller parts with almost the same size
                                That is, if the number of elements is even, partition it evenly.
                                Otherwise, the first part will have one more element than the second.
              :f            Flatten the array once
                {f          Remove elements that are empty arrays

                  c         Copy the result for checking 
                   {Dm$     Is the array solely composed of singletons?
                            If yes, ends the loop.

Le code pour visualiser la fusion:

W              Execute the rest of the program until the stack is empty
 {{eoJm        For each part, sort by numeric value, then join with space
       '|*     Join the parts with vertical bar
          P    Pop and print the result

Ancienne version, en train de construire la structure de liste imbriquée.

{{cc0+=!{x!}Mm',*:}}Xd;%v:2^^{;s~{c^;<~sc%v,*{2M{s^y!svsm}M}YZ!x!Q,dmU@e;%v:2^{;%v:2^-N~0{c;={scc0+=Cc%v!C:f{o}{scc0+=C{s^y!svsm}?}Y!cx!P,dcm

cc0+= est utilisé trois fois dans le code pour vérifier si le haut de la pile est un scalaire ou un tableau.

{{cc0+=!{x!}Mm',*:}}Xconstruit un bloc qui s'appelle récursivement pour sortir correctement un tableau de nombres imbriqué. (La sortie par défaut dans Stax vectorise un tableau imbriqué avant l'impression).

{                  }X    Store the code block in X
 {           m           Map each element in the list with block
  cc                     Make two copies of the element
    0+                   + 0. If the element is a scalar, nothing will change
                              If the element is an array, the element 0 will be appended
      =!{  }M            If the element has changed after the `0+` operation
                             Which means it is an array
         x!              Recursively execute the whole code block on the element

              ',*        Join the mapped elements with comma
                 :}      Bracerizes the final result

Il y a deux autres blocs qui effectuent le fractionnement et la fusion, respectivement. Ils sont trop verbeux et je ne me soucie pas d'expliquer (il y a un peu plus d'informations dans la version historique de ce post mais ne vous attendez pas à trop).