How to make an array slightly sorted?

Question

PHP

There is such an array (50 elements):

$data = [
  ['id' => 123, 'price' => 665],
  ['id' => 143, 'price' => 95],
  ['id' => 113, 'price' => 765],
 ...
];

Task: write a function that will completely sort the data in a maximum of 6 calls, with the condition that in 1 call no element will move more than 5 positions.
I will be very grateful for your help.
I suspect that with each function call, it is necessary to somehow partially order the elements, but I can’t figure out how to do this ...

Answer 1

There is such an array (50 elements):
Task: write a function that will completely sort the data in a maximum of 6 calls, with the condition that no element will move more than 5 positions in 1 call.

It is obvious that the problem in this formulation is generally unsolvable, since the maximum element standing first should be shifted in the process of sorting to the very end, i.e. by 49 positions, and 49 > 6 * 5.

Answer 2

And how to calculate how much the element has shifted? By absolute index?
Well, yes, do you need to make the array "completely" or "slightly" sorted?
Criteria are not clear from the statement of the problem. It is impossible to completely sort any array in the specified number of steps with the specified restrictions.
We can only increase the degree of order.
We return again to the criteria for the degree of order.
You can come up with several of them:
- the number of "knocked out" elements
- minimizing the sum of the distances of the elements from their optimal position.
- the average distance of the element from the optimal position.
- the total distance of the elements from the optimal position.