Sort an array with a constant number of unsorted elements

Question

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.

Answer 1

Denote the array by $A_1,\ldots,A_n$. If $A_i > 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)$.

Answer 2

An important observation is that an un-sorted array $A$ must contain at least one index $i$, such that $A[i+1]<A[i]$ (assuming we are sorting in ascending order).

In particular, if you assume that the first $k$ elements are ordered (but the array is not fully ordered), then in the last $n-k$ elements you will have such a behavior, and in particular there will be a smallest index in which this behavior exists.

This allows us a way to find all "wrong" places in $O(n)$: start from scanning elements from the start, and scan until you find such an element. Then, fix the element's position in the array, and continue scanning again (its important to fix the element's position!)

Notice that the "fixing" process is assumed to take $O(1)$, since we are (currently) only interested in the scanning process.

---

Another way to sort elements (not using the quicksort and partitioning idea) is to use bubble sort. The total number of "bubble transfers" must be at most $c\cdot n$ where $c$ is the number of unsorted elements. Take a quick look at bubblesort to confirm that any other element will not take more than $O(1)$ time overall.