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.

If anyone is interested in sorting toptal.com/developers/sorting-algorithms — exussum, 2 days ago
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) — Ton Hospel, 5 hours ago

Neil · Answer 1 · 2016-10-09 16:29:59Z

up vote 9 down vote

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

answered 2 days ago

Neil

20.5k21054

@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. – Neil yesterday

aah, clever! Thanks! – nimi yesterday

1

Bubble sort is a really judicious choice indeed to simplify the highlighting of the swapped numbers. Well done! – Arnauld yesterday

add a comment |

Ton Hospel · Answer 2 · 2016-10-12 09:22:32Z

up vote 9 down vote

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:

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)

edited 4 hours ago

answered 2 days ago

Ton Hospel

7,060324

Given that The characters under the swapped can be any char except space. you should not have spaces between number in the mark line – edc65 6 hours ago

@edc65 The character(s) under the elements being swapped is not a space. Nothing is said about the characters between them – Ton Hospel 5 hours ago

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 – edc65 5 hours ago

@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 :-) – Ton Hospel 5 hours ago

add a comment |

Jörg Hülsermann · Answer 3 · 2016-10-09 21:28:56Z

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

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

Peter · Answer 4 · 2016-10-10 14:34:29Z

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

nimi · Answer 5 · 2016-10-10 23:49:48Z

Haskell, 165 164 bytes

s%c=drop 2$show s>>c
p#x|(h,t:s)<-span(/=minimum x)x=concat[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 the 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]
                |

Numberknot · Answer 6 · 2016-10-11 15:31:47Z

up vote 0 down vote

Java 7, 256,241 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+" ");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++)out.print(j==i|j==m?a[j]+" ":"  ");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)
        out.print(k+" ");
    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++)
      out.print(j==i|j==m?a[j]+" ":"  ");
      out.println();        

}
}

output

edited 22 hours ago

answered 2 days ago

Numberknot

25916

4

This is still missing the declaration of out, you need to put something like PrintStream out=System.out; somewhere in your code. – Loovjo 2 days ago

2

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); – Geobits 2 days ago

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 ;) – AxelH 2 days ago

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. – Kevin Cruijssen 23 hours ago

@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++) – Numberknot 23 hours ago

| show 1 more comment

edc65 · Answer 7 · 2016-10-12 08:04:22Z

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>

asked	3 days ago
viewed	942 times
active	today

current community

your communities

more stack exchange communities

Visualize sorting

Input

Task

Other rules

7 Answers 7

JavaScript (ES6), 158 bytes

Perl, 62 bytes

PHP, 248 Bytes

How it works

Output Example

Python 2, 267 bytes

Haskell, 165 164 bytes

Java 7, 256,241 Bytes

Ungolfed

output

JavaScript (ES6), 147 155

Your Answer

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

Visit Chat

Hot Network Questions

current community

your communities

more stack exchange communities

Visualize sorting

Input

Task

Other rules

7 Answers 7

JavaScript (ES6), 158 bytes

Perl, 62 bytes

PHP, 248 Bytes

How it works

Output Example

Python 2, 267 bytes

Haskell, 165 164 bytes

Java 7, 256,241 Bytes

Ungolfed

output

JavaScript (ES6), 147 155

Your Answer

Sign up or log in

Post as a guest

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

Visit Chat

Related

Hot Network Questions