Visualisez le tri

20

Disons que j'ai une liste telle que [3, 0, 4, 2, 1], et que j'utilise le tri par sélection pour le trier, je pourrais le visualiser comme ceci:

3,0,4,2,1
|-|
0,3,4,2,1
  |-----|
0,1,4,2,3
    |-|
0,1,2,4,3
      |-|
0,1,2,3,4

Ce défi consiste à visualiser le tri comme ceci.

Contribution

Votre entrée sera une liste d'entiers positifs, dans le format de votre choix.

Tâche

Votre soumission doit trier la liste d'entrée en échangeant uniquement deux éléments à la fois, et à chaque échange, la soumission doit afficher la liste et un caractère sous chacun des éléments en cours d'échange. Si un nombre qui a été échangé a plus d'un chiffre, le caractère peut être n'importe où en dessous. À la fin, la soumission devrait afficher la liste triée.

Autres règles

  • Le tri doit utiliser moins de swaps que n 4 , où n est la longueur de la liste.
  • Le tri n'a pas besoin d'être déterministe.
  • Les caractères sous l'échange peuvent être n'importe quel caractère sauf l'espace.
code-golf sorting Loovjo
la source
Puis-je supposer que les entiers sont uniques?
Jörg Hülsermann,
n^4? Vous êtes un peu généreux ici.
orlp
@ JörgHülsermann No
Loovjo
2
Si quelqu'un est intéressé par le tri de toptal.com/developers/sorting-algorithms
exussum
3
Vous dites que l'entrée est des entiers positifs mais votre exemple a un 0 (veuillez corriger uniquement l'exemple afin de ne pas invalider les réponses qui ne peuvent pas gérer 0)
Ton Hospel

Réponses:

10

Perl, 62 octets

Comprend +3 pour -p

Donnez une entrée sous forme d'une seule ligne de chiffres sur STDIN:

perl -M5.010 visisort.pl <<< "3 0 4 2 1"

Échange à plusieurs reprises la première inversion. La complexité de l'échange est la O(n^2)complexité du temps O(n^3). Utilise les numéros échangés comme marque:

3 0 4 2 1
3 0
0 3 4 2 1
    4 2
0 3 2 4 1
  3 2
0 2 3 4 1
      4 1
0 2 3 1 4
    3 1
0 2 1 3 4
  2 1
0 1 2 3 4

visisort.pl:

#!/usr/bin/perl -p
$&>$'&&say$_.$"x"@-".!s/(\S+) \G(\S+)/$2 $1/.$&while/\S+ /g

Le programme prend également en charge les valeurs négatives et les nombres à virgule flottante

Si vous insistez sur un caractère de connexion, le code devient 66 octets:

#!/usr/bin/perl -p
$&>$'&&say$_.$"x"@-".!s/(\S+) \G(\S+)/$2 $1/.$1.-$2while/\S+ /g

Mais maintenant, il ne prend plus en charge les nombres négatifs et 0 (mais le programme ne doit de toute façon que prendre en charge les entiers positifs. Dans 0l'exemple, c'est une erreur)

Ton Hospel
la source
Étant donné que The characters under the swapped can be any char except space. vous ne devriez pas avoir d'espaces entre les nombres dans la ligne de repère
edc65
@ edc65 Le ou les caractères sous les éléments échangés ne sont pas des espaces. Rien n'est dit sur les personnages entre eux
Ton Hospel
Pas entièrement convaincu, mais ok. J'étais en train de voter trop vite (mais j'ai attiré votre attention). Si vous apportez une modification (vide) à votre réponse, je changerai mon vote
edc65
@ edc65 Eh bien, votre commentaire m'a fait relire le défi très attentivement. Notez qu'il parle également du cas des nombres à plusieurs chiffres, ce qui signifie clairement que vous pouvez par exemple simplement mettre un _sous le premier chiffre, ce qui signifie que tous les caractères entre les deux seraient en fait des espaces). Je maintiens donc mon interprétation (sauf si le PO est en désaccord bien sûr). Buit juste pour te faire plaisir J'ai aussi ajouté une version sans espace :-)
Ton Hospel
9

JavaScript (ES6), 158 octets

a=>{for(;;){console.log(``+a);i=a.findIndex((e,i)=>e<a[i-1]);if(i<0)break;console.log(` `.repeat(`${a.slice(0,i)}`.length-1)+`|-|`);t=a[i];a[i]=a[--i];a[i]=t}}

Tri par bulle. Exemple de sortie:

3,0,4,2,1
|-|
0,3,4,2,1
    |-|
0,3,2,4,1
  |-|
0,2,3,4,1
      |-|
0,2,3,1,4
    |-|
0,2,1,3,4
  |-|
0,1,2,3,4
Neil
la source
@nimi Puisque j'échange toujours des éléments adjacents, je peux toujours mettre le -sous le ,et les deux |s seront toujours sous les nombres adjacents.
Neil
aah, intelligent! Merci!
nimi
1
Le tri à bulles est un choix vraiment judicieux pour simplifier la mise en évidence des numéros échangés. Bien joué!
Arnauld
9

PHP, 248 octets

Bubblesort ennuyeux gagne

<?for($c=count($a=$_GET[a]);$c--;){for($s=$i=0;$i<$c;){$l=strlen($j=join(",",$a));if($a[$i]>$a[$i+1]){$t=$a[$i];$a[$i]=$a[$i+1];$a[$i+1]=$t;$m=" ";$m[$s]=I;$m[$s+strlen($a[$i].$a[$i+1])]=X;echo"$j\n$m\n";}$s+=strlen($a[$i++])+1;}}echo join(",",$a);

PHP, 266 octets par chemin avec array_slice et min

sortie modifiée I Xau lieu de*~~*

<?for($c=count($a=$_GET[a]);$i<$c;){$j=join(",",$s=($d=array_slice)($a,$i));$x=array_search($m=min($s),$s);echo($o=join(",",$a));$a[$x+$i]=$a[$i];$a[$i]=$m;if($i++!=$c-1){$t=" ";$t[$z=($f=strlen)($o)-($l=$f($j))]=I;$t[$l+$z-$f(join(",",$d($s,$x)))]=X;echo"\n$t\n";}}

282 octets

<?for($c=count($a=$_GET[a]);$i<$c;){$j=join(",",$s=($d=array_slice)($a,$i));$x=array_search($m=min($s),$s);echo($o=join(",",$a));$a[$x+$i]=$a[$i];$a[$i]=$m;if($i++!=$c-1)echo"\n".str_repeat(" ",($f=strlen)($o)-($l=$f($j))).($x?str_pad("*",$l-$f(join(",",$d($s,$x))),"~"):"")."*\n";}

Comment ça fonctionne

Recherche le minimum dans un tableau et le prend sur la première position Recherchez le minimum sans première position .... et ainsi de suite Si une valeur est double, la première valeur sera permutée

Exemple de sortie

31,7,0,5,5,5,753,5,99,4,333,5,2,1001,35,1,67
*~~~~*
0,7,31,5,5,5,753,5,99,4,333,5,2,1001,35,1,67
  *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
0,1,31,5,5,5,753,5,99,4,333,5,2,1001,35,7,67
    *~~~~~~~~~~~~~~~~~~~~~~~~~*
0,1,2,5,5,5,753,5,99,4,333,5,31,1001,35,7,67
      *~~~~~~~~~~~~~~*
0,1,2,4,5,5,753,5,99,5,333,5,31,1001,35,7,67
        *
0,1,2,4,5,5,753,5,99,5,333,5,31,1001,35,7,67
          *
0,1,2,4,5,5,753,5,99,5,333,5,31,1001,35,7,67
            *~~~*
0,1,2,4,5,5,5,753,99,5,333,5,31,1001,35,7,67
              *~~~~~~*
0,1,2,4,5,5,5,5,99,753,333,5,31,1001,35,7,67
                *~~~~~~~~~~*
0,1,2,4,5,5,5,5,5,753,333,99,31,1001,35,7,67
                  *~~~~~~~~~~~~~~~~~~~~~*
0,1,2,4,5,5,5,5,5,7,333,99,31,1001,35,753,67
                    *~~~~~~*
0,1,2,4,5,5,5,5,5,7,31,99,333,1001,35,753,67
                       *~~~~~~~~~~~*
0,1,2,4,5,5,5,5,5,7,31,35,333,1001,99,753,67
                          *~~~~~~~~~~~~~~~*
0,1,2,4,5,5,5,5,5,7,31,35,67,1001,99,753,333
                             *~~~~*
0,1,2,4,5,5,5,5,5,7,31,35,67,99,1001,753,333
                                *~~~~~~~~*
0,1,2,4,5,5,5,5,5,7,31,35,67,99,333,753,1001
                                    *
0,1,2,4,5,5,5,5,5,7,31,35,67,99,333,753,1001
Jörg Hülsermann
la source
Au lieu de echo$t."\n";, vous pouvez utiliser echo"$t\n";et enregistrer un octet.
Ismael Miguel
@IsmaelMiguel N'hésitez pas à modifier mes messages si vous trouvez quelque chose à améliorer
Jörg Hülsermann
7
Les modifications de code sur les publications sont généralement désapprouvées, ce avec quoi je suis totalement d'accord.
Ismael Miguel
3

Haskell, 165 164 162 octets

s%c=drop 2$show s>>c
p#x|(h,t:s)<-span(/=minimum x)x=id=<<[show$p++x,"\n ",[' '|p>[]],p%" ","|",h%"-",['|'|h>[]],"\n",(p++[t])#(drop 1h++take 1h++s)]|1<2=""
([]#)

Cela visualise le tri de la sélection. Exemple d'utilisation:

*Main> putStr $ ([]#) [31,7,0,5,5,5,753,5,99,4,333,5,2,1001,35,1,67]
[31,7,0,5,5,5,753,5,99,4,333,5,2,1001,35,1,67]
 |----|
[0,7,31,5,5,5,753,5,99,4,333,5,2,1001,35,1,67]
   |-------------------------------------|
[0,1,31,5,5,5,753,5,99,4,333,5,2,1001,35,7,67]
     |-------------------------|
[0,1,2,5,5,5,753,5,99,4,333,5,31,1001,35,7,67]
       |--------------|
[0,1,2,4,5,5,753,5,99,5,333,5,31,1001,35,7,67]
         |
[0,1,2,4,5,5,753,5,99,5,333,5,31,1001,35,7,67]
           |
[0,1,2,4,5,5,753,5,99,5,333,5,31,1001,35,7,67]
             |---|
[0,1,2,4,5,5,5,753,99,5,333,5,31,1001,35,7,67]
               |------|
[0,1,2,4,5,5,5,5,99,753,333,5,31,1001,35,7,67]
                 |----------|
[0,1,2,4,5,5,5,5,5,753,333,99,31,1001,35,7,67]
                   |---------------------|
[0,1,2,4,5,5,5,5,5,7,333,99,31,1001,35,753,67]
                     |------|
[0,1,2,4,5,5,5,5,5,7,31,99,333,1001,35,753,67]
                        |-----------|
[0,1,2,4,5,5,5,5,5,7,31,35,333,1001,99,753,67]
                           |---------------|
[0,1,2,4,5,5,5,5,5,7,31,35,67,1001,99,753,333]
                              |----|
[0,1,2,4,5,5,5,5,5,7,31,35,67,99,1001,753,333]
                                 |--------|
[0,1,2,4,5,5,5,5,5,7,31,35,67,99,333,753,1001]
                                     |
[0,1,2,4,5,5,5,5,5,7,31,35,67,99,333,753,1001]
                                         |

Comment ça fonctionne:

s % cest une fonction d'aide qui fait des length (show s) - 2copies de personnage c. Il est utilisé pour l'espacement avant les deux |, une fois avec c == ' 'et une fois avecc == '-' .

La fonction principale #prend une liste pqui est la partie triée de la liste et xqui est la partie encore à trier. La correspondance de modèle (h,t:s)<-span(/=minimum x)xfractionne la liste xà son élément minimum et se lie hà la partie avant le minimum, tau minimum lui-même et sà la partie après le minimum. Le reste est formaté sur deux lignes: 1) la liste à son état actuel ( p++x) et 2) la |----|partie suivie d'un appel récursif de #avec tannexé à pet la tête deh inséré entre la queue de hets .

PS: fonctionne également avec les nombres à virgule négative et / ou flottante:

*Main> putStr $ ([]#) [-3,-1,4e33,-7.3]
[-3.0,-1.0,4.0e33,-7.3]
 |----------------|
[-7.3,-1.0,4.0e33,-3.0]
      |-----------|
[-7.3,-3.0,4.0e33,-1.0]
           |------|
[-7.3,-3.0,-1.0,4.0e33]
                |

Modifier: @BlackCap a enregistré 2 octets. Merci!

nimi
la source
id=<<[show$p++x,"\n ",[' '|p>[]],p%" ","|",h%"-",['|'|h>[]],"\n",(p++[t])#(drop 1h++take 1h++s)]
BlackCap
1

Python 2, 267 octets

Il fonctionne également avec des nombres décimaux et négatifs.

p=1
while p!=len(a):    
 q=p-1;k=a[p:];m=min(k);n=k.index(m)+p;b=map(str,a)
 if a[q]>m:print','.join(b)+'\n'+''.join(' '*len(i)for i in b[:q])+' '*q+'*'+'-'*(len(b[n])+n-q-2)+''.join('-'*len(i)for i in b[q:n])+'*';a[q],a[n]=[a[n],a[q]]
 p+=1
print','.join(map(str,a))

Exemple:

7,2,64,-106,52.7,-542.25,54,209,0,-1,200.005,200,3,6,1,0,335,-500,3.1,-0.002
*----------------------*
-542.25,2,64,-106,52.7,7,54,209,0,-1,200.005,200,3,6,1,0,335,-500,3.1,-0.002
        *-------------------------------------------------------*
-542.25,-500,64,-106,52.7,7,54,209,0,-1,200.005,200,3,6,1,0,335,2,3.1,-0.002
             *-----*
-542.25,-500,-106,64,52.7,7,54,209,0,-1,200.005,200,3,6,1,0,335,2,3.1,-0.002
                  *-------------------*
-542.25,-500,-106,-1,52.7,7,54,209,0,64,200.005,200,3,6,1,0,335,2,3.1,-0.002
                     *-----------------------------------------------------*
-542.25,-500,-106,-1,-0.002,7,54,209,0,64,200.005,200,3,6,1,0,335,2,3.1,52.7
                            *--------*
-542.25,-500,-106,-1,-0.002,0,54,209,7,64,200.005,200,3,6,1,0,335,2,3.1,52.7
                              *-----------------------------*
-542.25,-500,-106,-1,-0.002,0,0,209,7,64,200.005,200,3,6,1,54,335,2,3.1,52.7
                                *------------------------*
-542.25,-500,-106,-1,-0.002,0,0,1,7,64,200.005,200,3,6,209,54,335,2,3.1,52.7
                                  *-------------------------------*
-542.25,-500,-106,-1,-0.002,0,0,1,2,64,200.005,200,3,6,209,54,335,7,3.1,52.7
                                    *--------------*
-542.25,-500,-106,-1,-0.002,0,0,1,2,3,200.005,200,64,6,209,54,335,7,3.1,52.7
                                      *-------------------------------*
-542.25,-500,-106,-1,-0.002,0,0,1,2,3,3.1,200,64,6,209,54,335,7,200.005,52.7
                                          *------*
-542.25,-500,-106,-1,-0.002,0,0,1,2,3,3.1,6,64,200,209,54,335,7,200.005,52.7
                                            *-----------------*
-542.25,-500,-106,-1,-0.002,0,0,1,2,3,3.1,6,7,200,209,54,335,64,200.005,52.7
                                              *----------------------------*
-542.25,-500,-106,-1,-0.002,0,0,1,2,3,3.1,6,7,52.7,209,54,335,64,200.005,200
                                                   *----*
-542.25,-500,-106,-1,-0.002,0,0,1,2,3,3.1,6,7,52.7,54,209,335,64,200.005,200
                                                      *--------*
-542.25,-500,-106,-1,-0.002,0,0,1,2,3,3.1,6,7,52.7,54,64,335,209,200.005,200
                                                         *-----------------*
-542.25,-500,-106,-1,-0.002,0,0,1,2,3,3.1,6,7,52.7,54,64,200,209,200.005,335
                                                             *---------*
-542.25,-500,-106,-1,-0.002,0,0,1,2,3,3.1,6,7,52.7,54,64,200,200.005,209,335
Peter
la source
1

JavaScript (ES6), 147 155

Utiliser n * n compare, mais (je crois) le nombre minimum de swaps. Et les positions de swap sont plus variables par rapport au type de bulles ennuyeuses.

l=>l.reduce((z,v,i)=>l.map((n,j)=>s+=`${j>i?n<l[i]?l[p=j,t=s,i]=n:0:u=s,n},`.length,s=p=0)|p?z+`
${l[p]=v,' '.repeat(u)}^${Array(t-u)}^
`+l:z,''+l)

Moins de golf et, je l' espère, plus compréhensible

l=>
  l.reduce( (z,v,i) => // update z for each list element v at position i
    ( // begin outer loop body
      // loop to find the least value that is to be placed at pos i
      l.map( (n,j) => // for each list element n at position j
        ( // begin inner loop body
          j > i ? // check if at position after i
            n < l[i] && // check if lower value 
            (
              p = j, // remember position in p 
              l[i] = n, // store value in l[i] (could change later)
              t = s // in t, string length of list elements up element preciding j
            )
          : // else, position up to i
            u = s, // in u, string length of list elements up element preciding i
          s += `${n},`.length, // string length of list elements up to this point (value length + comma)
        ) // end inner loop body
        , s = p = 0 // init s and p at start of inner loop
      ), 
      p ? (// if found a lower value, complete the swap and update output
          l[p] = v, // complete swap, l[i] was assigned before
          z + '\n' + ' '.repeat(u) + // spaces to align 
               '^' + // left marker
               Array(t-u) + // swap highlight, using sequence of commas
               '^\n' + // right marker, newline
               l + // list values after the swap, newline
      )
      : z // else output is unchanged
    ) // end outer loop body
    , ''+l // init string output at start of outer loop
  ) // output is the result of reduce

Tester

f=
l=>l.reduce((z,v,i)=>l.map((n,j)=>s+=`${j>i?n<l[i]?l[p=j,t=s,i]=n:0:u=s,n},`.length,s=p=0)|p?z+`
${l[p]=v,' '.repeat(u)}^${Array(t-u)}^
`+l:z,''+l)

function sort()
{
  var list=I.value.match(/-?[\d.]+/g).map(x=>+x)
  O.textContent = f(list)
}

sort()
#I { width:80% }
<input id=I value='3, 0, 4, 2, 1'>
<button onclick='sort()'>Sort</button>
<pre id=O></pre>
Développer l'extrait

edc65
la source
0

Java 7, 256 241 282 octets

Merci à @Geobits et @Axelh pour avoir économisé 15 octets

 void f(int[]a){int m,i,j,l=a.length;for(i=0;i<l;j=a[i],a[i]=a[m],a[m]=j,i++){for(int k:a)System.out.print(k+" ");System.out.println();for(j=i+1,m=i;j<l;m=a[j]<a[m]?j:m,j++);for(j=0;j<=m&i!=l-1;j++)System.out.print(j==i|j==m?a[j]+" ":"  ");System.out.println();}}

Non golfé

 void f(int[]a){
    int m,i,j,l=a.length;
for(i=0;i<l;j=a[i],a[i]=a[m],a[m]=j,i++){
    for(int k:a)
        System.out.print(k+" ");
    System.out.println();
     for(j=i+1,m=i;j<l;m=a[j]<a[m]?j:m,j++);
      for(j=0;j<=m&i!=l-1;j++)
      System.out.print(j==i|j==m?a[j]+" ":"  ");
      System.out.println();        

}
}

production

3 0 1 4 2 
3 0 
0 3 1 4 2 
  3 1 
0 1 3 4 2 
    3   2 
0 1 2 4 3 
      4 3 
0 1 2 3 4
Numberknot
la source
4
Il manque toujours la déclaration de out, vous devez mettre quelque chose comme PrintStream out=System.out;quelque part dans votre code.
Loovjo
2
Après avoir corrigé l'importation / la déclaration de out, vous devez utiliser un ternaire au lieu de if/elsesi vous allez imprimer sur les deux branches. Quelque chose comme out.print(a>b?a:b);au lieu deif(a>b)out.print(a);else out.print(b);
Geobits
Vous pouvez réduire le if else liek this: if(j==i|j==m)out.print(a[j]);out.print(" ");ou encore mieux avec un ternaire out.print((j==i|j==m?a[j]:" ")+" ");et ensuite vous pouvez supprimer {} de la boucle PS: j'utilise une importation statique pour l'instance de sortie, si cela vous
convient
Hmm, à part les conseils de golf des autres, la sortie est incorrecte. Voici une idée avec votre code copié-collé (et ajouté System.devant le outs), et il manque le 2et 3sur les deux dernières lignes de swap.
Kevin Cruijssen
@KevinCruijssen Je l'ai corrigé.En fait, je mélange la variable i avec la variable j (devrait être i) dans cette lignefor(j=0;j<=m&i!=l-1;j++)
Numberknot
0

Gelée , 36 octets

I;0CMḢ;L‘ṬCœṗ¹UF©µÐĿ,n+32Ọ$¥¥2\;/®ṭG

Essayez-le en ligne!

Explication

I;0CMḢ;L‘ṬCœṗ¹UF©µÐĿ,n+32Ọ$¥¥2\;/®ṭG
                 µÐĿ                 Repeat until we see a previously seen value:
I;0                                    Take differences of adjacent inputs, and 0
   CM                                  Find the indices (M) of the smallest (C) 
           œṗ                          Split {the input} into pieces
        ‘Ṭ                               that end
      ;L  C                              everywhere except
     Ḣ                                 the first of the chosen deltas
             ¹                         Resolve parser ambiguity
              U                        Reverse each piece
               F                       Concatenate the pieces back into a list
                ©                      Store the value in a register
                                     Then, on the accumulated list of results:
                             2\        Look at each consecutive pair of results
                    ,       ¥  ;/      and return the first element, followed by
                      +32Ọ$            the character with code 32 plus
                     n     ¥           1 (if unequal), 0 (if equal)
                                 ®ṭ  Append the value of the register
                                   G Output in grid form

L'exemple montré dans le lien TIO est particulièrement difficile pour ce programme; le ;0début proche est nécessaire pour garantir que la boucle se termine juste au point où l'entrée est triée. Normalement, cela n'est pas nécessaire (car il se terminera après une autre itération), mais si le dernier échange concerne les deux premiers éléments (comme on le voit ici), l'itération de plus ne se produira pas et rendra la finition impossible la liste de manière cohérente. En tant que tel, nous devons nous assurer de ne rien échanger lors de la dernière itération de la boucle.


la source