Visualize sorting

Question

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 n⁴, 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.

Answer 1

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)

Answer 2

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

Answer 3

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

Answer 4

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!

Answer 5

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.

Answer 6

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

Answer 7

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>

Answer 8

J, ⁶⁶ 65 bytes

[:(>@,@(2({.;'^ '{~=/)\])@,{:)@":]C.~a:,[:<"1\@;({.,.}.)&.>@C.@/:

Try it online!

Answer 9

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