prove an O(n) algorithm exists for 10 swaps

Question

A famous problem is finding the minimum amount of swaps for sorting an array. My problem is that we have array of size n and we know we can sort it with 10 swaps(we don't know the moves, only the number of the moves). I want to prove that There exists an O(n) algorithm (for time) that sorts this array.

First of all, for proving this statements should I present some code? I don't know how to prove it And Second of all, is this related to minimum amount of swaps for sorting an array?

Thanks for your help

Answer 1

Your solution is in Adaptive sorts algorithms.

A classic example of an adaptive sorting algorithm is Straight Insertion Sort. In this sorting algorithm, we scan the input from left to right, repeatedly finding the position of the current item, and insert it into an array of previously sorted items.

We know that:

The performance of this algorithm can be described in terms of the number of inversions in the input, and then T(n) will be roughly equal to I(A)+(n-1), where I(A) is the number of Inversions.

So, as in your case, the number of inversions is constant, the complexity of this algorithm will be Theta(n).