patternMinor
What is a partially sorted array?
Viewed 0 times
partiallyarraywhatsorted
Problem
I come across this definition but it's not so clear for me !
An array is partially sorted if the number of inversions is less or
equal a constant times the array length. if array length is N then
(number of inversions) <= c*N, with c constant.
For me c should be <= 1 is this what they meant ?
For more context : insertion sort running time is linear for partially sorted arrays.
An array is partially sorted if the number of inversions is less or
equal a constant times the array length. if array length is N then
(number of inversions) <= c*N, with c constant.
For me c should be <= 1 is this what they meant ?
For more context : insertion sort running time is linear for partially sorted arrays.
Solution
The definition you quote is rather meaningless. More accurately, a sequence of arrays, one of each length $n$, is partially sorted if for some constant $c$, the number of inversions of the array of length $n$ is at most $cn$. (More succinctly, a sequence of arrays is partially sorted if the number of inversions is $O(n)$.) The running time of insertion sort on such a sequence of arrays is $O(n)$, that is, linear.
It doesn't make much sense to say that a single array is partially sorted, since we can always choose $c$ to make the definition hold. If we want to talk about a single array then we need to fix $c$ in advance. Note that $c$ doesn't have to be at most $1$.
It doesn't make much sense to say that a single array is partially sorted, since we can always choose $c$ to make the definition hold. If we want to talk about a single array then we need to fix $c$ in advance. Note that $c$ doesn't have to be at most $1$.
Context
StackExchange Computer Science Q#47442, answer score: 8
Revisions (0)
No revisions yet.