How to determine to which extent/level an array of integers is already sorted

Question

Consider an array of any given unique integers e.g. [1,3,2,4,6,5] how would one determine the level of "sortedness", ranging from 0.0 to 1.0 ?

Answer 1

One way would be to evaluate the number of items that would have to be moved to make it sorted and then divide that by the total number of items.

As a first approach, I would detect the former as just the number of times a transition occurs from higher to lower value. In your list, that would be:

3 -> 2
6 -> 5

for a total of two movements. Dividing that by six elements gives you 33%.

In a way, this makes sense since you can simply move the 2 to between 1 and 3, and the 5 to between 4 and 6.

Now there may be edge cases where it's more efficient to move things differently but then you're likely going to have to write really complicated search algorithms to find the best solution.

Personally, I'd start with the simplest option that gave you what you wanted and only bother expanding if it turns out to be inadequate.

Answer 2

I would say the number of swaps is not a very good way to determine this. Most importantly because you can sort the array using a different number of swaps. In your case, you could switch 2<-->3 and 6<-->5, but you could also do a lot more switches.

How would you sort, say:

1 4 3 2 5

Would you directly switch 2 and 4, or would you switch 3 and 4, then 4 and 2, and then 3 and 2.

I would say a more correct method would be the number of elements in the right place divided by the total number of elements.

In your case, that would be 2/6.