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.

• Jörg Hülsermann: Could I assume that the integers are unique?
• orlp: n^4? You're being a bit generous here.
• xenia: @JörgHülsermann No
• exussum: If anyone is interested in sorting toptal.com/developers/sorting-algorithms
• Ton Hospel: 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)

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ドル.-2ドルwhile/\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)

• edc65: Given that The characters under the swapped can be any char except space. you should not have spaces between number in the mark line
• Ton Hospel: @edc65 The character(s) under the elements being swapped is not a space. Nothing is said about the characters between them
• edc65: 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
• Ton Hospel: @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 :-)

Answer 2

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

• Neil: @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.
• nimi: aah, clever! Thanks!
• Arnauld: Bubble sort is a really judicious choice indeed to simplify the highlighting of the swapped numbers. Well done!

Answer 3

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

• Ismael Miguel: Instead of echo$t."\n";, you can use echo"$t\n"; and save a byte.
• Jörg Hülsermann: @IsmaelMiguel Feel free to edit my posts if you find something to improve
• Ismael Miguel: Code edits on posts are usually frowned upon, which I totally agree with.

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!

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

Answer 5

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 6

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 7

Jelly, 36 bytes

I;0CMḢ;L‘ṬCœṗ1UF©μÐL·,n+32Ọ$\2円\;/®ṭG

Try it online!

Explanation

I;0CMḢ;L‘ṬCœṗ1UF©μÐL·,n+32Ọ$\2円\;/®ṭG
 μÐL· 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
 1 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 8

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 

• xenia: This is still missing the declaration of out, you need to put something like PrintStream out=System.out; somewhere in your code.
• Geobits: 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);
• AxelH: 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 ;)
• Kevin Cruijssen: 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.
• Numberknot: @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++)

Answer 9

J, ^{(削除) 66 (削除ここまで)} 65 bytes

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

Try it online!