java - Using simple arrays to sort numbers by stacking them? -

this homework question (sorry, know these frowned upon), neither nor teacher knows how solve efficiently, wanted put here see if wonderful brains on out.

an array of unspecified size given, containing random numbers. must sorted increasing order. each element can either moved adjacent empty space, or moved on top of adjacent larger element. need write method returns minimum number of moves needed sort given array.

the question has been labeled 'optional', since teacher realized problem far difficult, i'm curious how might solved. suggestions arrays of size (it can arrays of length 3 care) appreciated.

edit: pointing out unclear. i'm using array represent hypothetical real world situation. let's use example of coins: laid out on table in row, , there specified number of 'spaces' can put in. can put on top of adjacent larger coins, or slide adjacent empty space (which has been vacated coin had presumably moved on top of pile).

i decided examine problem few assumptions/changes, because made more interesting problem me:

1) can move elements left or right part of pile.

2) can stack element onto pile no matter if it's bigger, smaller or same size.

3) array considered sorted long never encounter bigger number before smaller number no matter how go through stacks. _ 11 2 3 sorted _ _ 12 3 not because interpret 2 being before 1.

this leads interesting problem, in spite of axiom:

axiom a: order in make moves irrelevant, , can re-arranged in way still achieve same final result.

axiom ab: if array has no repeats in it, move every element towards final position.

in particular, developed strategy hoping solve local examination , no recursiveness/backtracking, i've proven fruitless , show later.

my strategy is:

1) proceed left right looking pairs flipped wrong way (a higher number before lower number).

2a) when find one, if there empty spot or stack right hand value fill, move left until fill it.

2b) else, move left value right one. creates situation have stack of indifferent numbers - first, compare value moved right value on new right according logic of 1) before comparing downwards.

2bii) treat downwards comparison same way pair comparison - move lower value left if can fit empty spot or stack, else move higher value right , continue.

examples:

1231 -> shift 1b left because fit onto stack. 11 2 3 _

1321 -> shift 3 right because 2 not fit empty spot/onto stack. shift 1b left twice because fit empty spot/fit onto stack, shift 3 right because 2 not fit empty spot/onto stack. 1 1 2 3

1132 -> shift 3 right 2 can't go left. shift 2 left because fit in empty spot. 1 1 2 3

2311 -> shift 3 right 1a can't go left. shift 1b left twice because fit in empty spot. shift 1a left because stack. shift 2 right because 1a1b can't go left. shift 1a2b left fill empty spot. 11 2 3 _

however, run problem these 2 starting arrays:

23411 10 moves optimal, 2r 3r 4r 1al*3 1bl*4 make 11 2 3 4 _.

23111 9 moves optimal, 2r*3 3r*3 1bl 1cl*2 make _ _ 111 2 3 - opposite of 23411 strategy! move 1s less , 23 more because there more 1s , save moves moving them little possible.

which shows can't simple local comparison solve new problem.

i'm still thinking problem, seems non-trivial in intriguing way, , hope of enjoy contemplating me :)