Sort an array with a constant number of unsorted elements I am trying to sort an array that I know to have a constant number of unsorted elements (elements that are not in their right place).
In the solution I looked at they say you can do this in $O(n)$ time:
you can find any unsorted element in $O(n)$ and then move it to the right place in $O(n)$ also. I am not seeing how you can do these things in $O(n)$.
I mean, I thought of an algorithm that iterates from 1 to $n$ ($n$ is length of the array), checks if the element at the index is in it's sorted place and if the answer is no then you can use partition for bringing it to the right place (partition works in $O(n)$).
Because I have a constant number of elements that are not in their right place I will use partition constant $\times n$ times which means the algorithm is $O(n)$ as asked. Problem is that checking for every index if the element in the index is in his right place is $O(n)$ and doing it for every index is $O(n)$ so it sums up to $O(n^2)$ so maybe the solution is not right. (Every other solution I wrote also has this problem)
I will be glad for any help.
Denote the array by $A_1,\ldots,A_n$. If $A_i &gt; A_{i+1}$ then at least one of the two elements is out of place. We scan the array, and each time we find such a pair, we remove both elements. In $O(n)$ time, we obtain a sorted subarray $B$ together with $O(1)$ many unsorted elements, forming a set $C$. We sort $C$ in $O(1)$ and merge it with $B$ in $O(n)$.