Sort Number Array

Question

Given array \$A\$ \$(a_0, a_1,... , a_n) \$ as a permutation of \$(0, 1,...,n)\$ where \$n ≥ 2\$. Sort array \$A\$ into array \$(0, 1,...,n\$) with \$2\$ caveats:

• \$1\$ swap is counted when swapping a non-zero value and \$0\$ in the array \$A\$. This is the only allowed way to swap.
• Swap as few times as possible.
  

The array will always be scrambled.

Sample I/O

Print only \$1\$ output if many equally optimal solutions exist.
Input and output format is flexible.

Input:
2 3 0 1 5 4
Output:
2 3 1 3 4 5 4

Visualization

Original A array: 2 3 0 1 5 4
1. (2): 0 3 2 1 5 4 #Swapped 2 and 0
2. (3): 3 0 2 1 5 4 #Swapped 3 and 0
3. (1): 3 1 2 0 5 4 #Swapped 1 and 0
4. (3): 0 1 2 3 5 4 #Swapped 3 and 0
5. (4): 4 1 2 3 5 0 #Swapped 4 and 0
6. (5): 4 1 2 3 0 5 #Swapped 5 and 0
7. (4): 0 1 2 3 4 5 #Swapped 4 and 0
#Swapping 7 times was the fewest swaps possible.

Winning Criterion

This is a code-golf challenge. The fewest bytes of source code wins.

Answer 1

Wolfram Language (Mathematica), 55 bytes

##~##&~#&@@@D@@PermutationCycles@Ordering@#/. 1->Set@$&

Try it online!

Input and output 1-indexed.

                                 Ordering@#             invert permutation
               PermutationCycles@                       convert to cycles
            D@@                                          as list of lists
##~##&~#&@@@                                            convert to 1-swaps
                                           /. 1->Set@$  remove 1s

Answer 2

JavaScript (V8), 59 bytes

x=>x.map(e=(c,u)=>u-c&&u-(q=x[u&&print(u),u])&&e(x[u]=u,q))

Try it online!

Assumes first step moving 0 to front is optimal

-2 bytes from Shaggy and -7 from Arnauld

Answer 3

Jelly, 15 bytes

nJ,i€1ṄḊ¡€ṚƬyµƬ

A monadic Link that accepts a list of 1-based values and prints each value to be swapped with 1 to stdout. Note, this also yields a list of lists which may be ignored by the caller (this is the states plus one extra, bogus state).

Try it online! (footer discards the yielded list of lists).

How?

nJ,i€1ṄḊ¡€ṚƬyµƬ - Link: list, P, of values [1..len(P)]
             µƬ - collect up while distinct, applying:
 J              -   indices -> [1..len(Current)] (==[1..len(P)])
n               -   {Current) not equal {that} (vectorises)
  ,             -   pair {that} with {Current}
   i€1          -   index of 1 in each of those -> ValuesToSwap
         €      -   for each:
        ¡       -     if...
       Ḋ        -     ...condition: dequeue -> truthy if ValueToSwap > 1
      Ṅ         -     ...then: print it
           Ƭ    -   collect up while distinct, applying:
          Ṛ     -     reverse
            y   -   translate {Current} using {that} -> swap the Values

Answer 4

Charcoal, 25 bytes

Ｗ∨⌕θ⁰⌊Φθ⁻κλ«ＵＭθ∧⁻κι∨κι⟦Ｉι

Try it online! Link is to verbose version of code. Explanation:

Ｗ∨⌕θ⁰⌊Φθ⁻κλ«

While a number can be found to swap 0 with, preferably the number that belongs where 0 is now, ...

ＵＭθ∧⁻κι∨κι

... swap 0 and that number, and...

⟦Ｉι

... output the number that 0 was swapped with.

Answer 5

05AB1E, 20 19 bytes

[ÐÅΔNÊ}D(#s0k+=0‚‡

Outputs the results on separated lines.

Try it online or verify multiple test cases at once.

Explanation:

(05AB1E uses 0-based indexing.)

[           # Start an infinite loop:
 Ð          #  Triplicate the current list
            #  (which will be the implicit input-list in the first iteration)
  ÅΔ        #  Pop one, and push the first index that's truthy for
            #  (or -1 if none are truthy):
            #   (implicitly push the current item of the list)
    NÊ      #   Check whether it's NOT equal to its index
   }D       #  Duplicate this first unsorted index
     (      #  Pop, and if it's -1 (aka the list is already sorted):
      #     #   Stop the infinite loop
  s         #  Swap so the current list is at the top again
   0k       #  Pop and get the index of the 0
     +      # †Add it to the found index
      =     #  Print it with trailing newline (without popping)
      0‚    #  Pair it with 0
        ‡  #  Swap those two values in the list:
        Â   #   Bifurcate; short for Duplicate & Reverse copy
         ‡  #   Transliterate

† The + acts as a ‚à (pair and keep the maximum) here, since either the first value in the list is unsorted, in which case ÅΔNÊ} results in this first index 0 and 0k results in the index we want to swap with, OR the first value is 0, in which case ÅΔNÊ} results in the index we want to swap with and 0k results in 0. In either case, one of the two is 0, so using the + here is fine to save a byte.

Answer 6

R, 94 91 80 79 bytes

f=\(a){i=max(j<-which(!a)-1,a[a>seq(a)-1]*!j)
a[a==i]=0
if(a[j+1]<-i)c(i,f(a))}

Attempt This Online!

Here is a link to a version that prints-out each stage of the swapping, and here is a link to various test cases concocted in Kevin Cruijssen's answer.

---

Ungolfed, original version

zeroswapsort=
f=function(a            # recursive function with argument
                        # a = array to sort
            ,j=1){      # set j = 1 
if(i<-which(!a)-1)      # if zero is not in the first position
                        #   set i = (zero-based) position of zero
                        #    (this is the number to swap)
                  j=i+1 #   set j = (one-based) index to swap
else                    # otherwise, leave j as position of zero = 1
     i=max(0,a[a>seq(a)-1])
                        #   and set i = 0 (if array is sorted)
                        #   or i = any value in the wrong position
                        #   (chosen as maximum difference to the sorted array)
a[a==i]=0               # now, do the swap
a[j]=i 
if(i)                   # and if the array wasn't already sorted
     c(i                # return the swapped value
        ,f(a))}         # and recursively sort the swapped array

Answer 7

Python 3.8 (pre-release),  147   146  144 bytes

-1 byte and bonus performance improvement by assigning q outside of the inner while loop.
-2 bytes by assigning o using tuple unpacking.

A=eval(input())
B=x=1
while B!=sorted(A):
 B,y,q,*o=A[:],x,len(A)
 while y:c=B.index(0);B[B.index(z:=y%q)]=0;B[c]=z;y//=q;o=[z]+o
 x+=1
print(o)

Inputs and outputs as a Python list.

Try it online!

Answer 8

Python 3.8 (pre-release), 109 bytes

def f(a):x=a.index;z=x(0);a[x(i:=z or[j for j in a if x(j)-j][0])]=0;a[z]=i;return[i][a>sorted(a):]or[i]+f(a)

Try it online!