# Sort Number Array

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.

• Is it acceptable for us to use 1 rather than 0 as our minimum input value? Commented Jul 3 at 12:55
• @JonathanAllan Any number as minimum input would be fine. Commented Jul 3 at 14:25

# 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

# 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

• this doesn't seem right for e.g. [1,2,0]
– att
Commented Jul 3 at 5:55
• @att Reversed order is fine. Fixed
– l4m2
Commented Jul 3 at 6:40
• 66 bytes Commented Jul 3 at 8:15
• 59 bytes? (from @Shaggy's) Commented Jul 3 at 12:13

# 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

# 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.

# 05AB1E, 20 19 bytes

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

Outputs the results on separated lines.

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.

# R, 949180 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

# 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!

# 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!