prove an O(n) algorithm exists for 10 swaps

user_8178498 0
Viewed 117

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

swap sorting algorithm
2 Answers

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

user_37688710

If we know that 10 swaps is enough for sorting an array then this array is nearly sorted with maximum 10*2 = 20 elements out of order. So if we find some sort algorithm that has O(n) on nearly sorted arrays then it is enough for proving your statement.

For example we can use 2 step solution:

  1. find all out of order elements in array, remove and save them

  2. insert saved elements in resulting array in right positions

With such “naive” algorithm it will take one pass for first step and 20 or less passes (20 out of order elements) for second step in worst case. So if n >> 10 than it gets O(n) for you case. This proof is correct for any constant number of swaps if it doesn’t depend on n

user_49157070
Related