20
\$\begingroup\$

Say I have a list such as [3, 0, 4, 2, 1], and I use selection sort to sort it, I could visualize it like this:

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

This challenge is about visualizing sorting like this.

Input

Your input will be a list of positive integers, in any format you like.

Task

Your submission should sort the input list by only swapping two elements at a time, and at each swap, the submission should display the list, and a character under each of the elements being swapped. If a number that was swapped has more than one digit, the character can be anywhere underneath it. At the end, the submission should display the sorted list.

Other rules

  • The sorting must use fewer swaps than n4, where n is the length of the list.
  • The sorting doesn't have to be deterministic.
  • The characters under the swapped can be any char except space.
\$\endgroup\$
  • \$\begingroup\$ Could I assume that the integers are unique? \$\endgroup\$ – Jörg Hülsermann Oct 9 '16 at 14:00
  • \$\begingroup\$ n^4? You're being a bit generous here. \$\endgroup\$ – orlp Oct 9 '16 at 14:00
  • \$\begingroup\$ @JörgHülsermann No \$\endgroup\$ – Loovjo Oct 9 '16 at 14:01
  • 2
    \$\begingroup\$ If anyone is interested in sorting toptal.com/developers/sorting-algorithms \$\endgroup\$ – exussum Oct 10 '16 at 6:12
  • 3
    \$\begingroup\$ You say the input is positive integers but your example has a 0 (please fix only the example so as not to invalidate answers that can't handle 0) \$\endgroup\$ – Ton Hospel Oct 12 '16 at 9:01
10
\$\begingroup\$

Perl, 62 bytes

Includes +3 for -p

Give input as a single line of numbers on STDIN:

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

Repeatedly swaps the first inversion. Swap complexity is O(n^2), time complexity is O(n^3). Uses the numbers being swapped as mark:

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

The program also supports negative values and floating point numbers

If you insist on a connecting character the code becomes 66 bytes:

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

But now it doesn't support negative numbers and 0 anymore (but the program only has to support positive integers anyways. The 0 in the example is a mistake)

\$\endgroup\$
  • \$\begingroup\$ Given that The characters under the swapped can be any char except space. you should not have spaces between number in the mark line \$\endgroup\$ – edc65 Oct 12 '16 at 8:06
  • \$\begingroup\$ @edc65 The character(s) under the elements being swapped is not a space. Nothing is said about the characters between them \$\endgroup\$ – Ton Hospel Oct 12 '16 at 8:20
  • \$\begingroup\$ Not entirely convinced, but ok. I was too fast downvoting (but I got your attention). If you make an (empty) edit to your answer I'll change my vote \$\endgroup\$ – edc65 Oct 12 '16 at 8:47
  • \$\begingroup\$ @edc65 Well, your comment made me reread the challenge very carefully. Notice that he also talks about the case of multidigit numbers clearly meaning you can e.g. just put a _ under the first digit which means that all characters inbetween would in fact be spaces). So I stand by my interpretation (unless the OP disagrees of course). Buit just to make you happy I added a version without space too :-) \$\endgroup\$ – Ton Hospel Oct 12 '16 at 8:54
9
\$\begingroup\$

JavaScript (ES6), 158 bytes

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}}

Bubble sort. Sample output:

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
\$\endgroup\$
  • \$\begingroup\$ @nimi Since I'm always swapping adjacent elements, I can always put the - under the , and then the two |s will always be under the adjacent numbers. \$\endgroup\$ – Neil Oct 10 '16 at 23:33
  • \$\begingroup\$ aah, clever! Thanks! \$\endgroup\$ – nimi Oct 10 '16 at 23:36
  • 1
    \$\begingroup\$ Bubble sort is a really judicious choice indeed to simplify the highlighting of the swapped numbers. Well done! \$\endgroup\$ – Arnauld Oct 11 '16 at 1:01
9
\$\begingroup\$

PHP, 248 Bytes

Bubblesort boring wins

<?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 Bytes a way with array_slice and min

modified output I X instead of *~~*

<?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 Bytes

<?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";}

How it works

Looks for the minimum in an array and take this on first position Look for the minimum without first position .... and so on If a value is double the first value will be swap

Output Example

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
\$\endgroup\$
  • \$\begingroup\$ Instead of echo$t."\n";, you can use echo"$t\n"; and save a byte. \$\endgroup\$ – Ismael Miguel Oct 9 '16 at 18:32
  • \$\begingroup\$ @IsmaelMiguel Feel free to edit my posts if you find something to improve \$\endgroup\$ – Jörg Hülsermann Oct 9 '16 at 18:34
  • 7
    \$\begingroup\$ Code edits on posts are usually frowned upon, which I totally agree with. \$\endgroup\$ – Ismael Miguel Oct 9 '16 at 18:36
3
\$\begingroup\$

Haskell, 165 164 162 bytes

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=""
([]#)

This visualizes selection sort. Usage example:

*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]
                                         |

How it works:

s % c is a helper function that makes length (show s) - 2 copies of character c. It's used for spacing before both |, one time with c == ' ' and one time with c == '-'.

The main function # takes a list p which is the sorted part of the list and x which is the yet to sort part. The pattern match (h,t:s)<-span(/=minimum x)x splits the list x at its minimum element and binds h to the part before the minimum, t to the minimum itself and s to the part after the minimum. The rest is formatting two lines: 1) the list at its current state (p++x) and 2) the |----| part followed by a recursive call of # with t appended to p and the head of h inserted between the tail of h and s.

PS: works also with negativ and/or floating point numbers:

*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]
                |

Edit: @BlackCap saved 2 bytes. Thanks!

\$\endgroup\$
  • \$\begingroup\$ id=<<[show$p++x,"\n ",[' '|p>[]],p%" ","|",h%"-",['|'|h>[]],"\n",(p++[t])#(drop 1h++take 1h++s)] \$\endgroup\$ – BlackCap Oct 31 '16 at 12:19
1
\$\begingroup\$

Python 2, 267 bytes

It works with decimals and negative numbers as well.

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))

Example:

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
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 147 155

Using n*n compares, but (I believe) the minimum number of swaps. And the swap positions are more variable compared to the boring bubble sort.

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)

Less golfed and hopefully more understandable

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

Test

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>

\$\endgroup\$
0
\$\begingroup\$

Java 7, 256 241 282 Bytes

Thanks to @Geobits and @Axelh for saving 15 bytes

 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();}}

Ungolfed

 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();        

}
}

output

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 
\$\endgroup\$
  • 4
    \$\begingroup\$ This is still missing the declaration of out, you need to put something like PrintStream out=System.out; somewhere in your code. \$\endgroup\$ – Loovjo Oct 9 '16 at 17:48
  • 2
    \$\begingroup\$ After fixing the import/declaration of out, you should use a ternary instead of if/else if you're going to be printing on both branches. Something like out.print(a>b?a:b); instead of if(a>b)out.print(a);else out.print(b); \$\endgroup\$ – Geobits Oct 10 '16 at 5:05
  • \$\begingroup\$ You can reduce the if else liek this : if(j==i|j==m)out.print(a[j]);out.print(" "); or even better with a ternary out.print((j==i|j==m?a[j]:" ")+" "); and then you can remove {} of the loop PS : I use a import static for the out instance, if that's ok ;) \$\endgroup\$ – AxelH Oct 10 '16 at 12:16
  • \$\begingroup\$ Hmm, apart from the golfing tips from the others, the output is incorrect.. Here is an ideone with your code copy-pasted (and added System. in front of the outs), and it's missing the 2 and 3 on the two last swap-lines. \$\endgroup\$ – Kevin Cruijssen Oct 11 '16 at 14:28
  • \$\begingroup\$ @KevinCruijssen I corrected it.Actually I mix up i variable with j variable(should be i)in this linefor(j=0;j<=m&i!=l-1;j++) \$\endgroup\$ – Numberknot Oct 11 '16 at 15:15
0
\$\begingroup\$

Jelly, 36 bytes

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

Try it online!

Explanation

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

The example shown in the TIO link is a particularly hard one for this program; the ;0 near the start is necessary to ensure that the loop ends just at the point where the input becomes sorted. This normally isn't necessary (because it will end after one more iteration), but if the last swap is of the first two elements (as seen here), the one-more-iteration won't happen and makes it impossible to finish the list consistently. As such, we need to ensure we don't swap anything on the last loop iteration.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.