How about something like this:
#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>
typedef std::vector<int> iVec_t;
typedef iVec_t::iterator iVec_i;
int main( int argc, char* argv[] )
{
// load up a vec with numbers and shuffle them
iVec_t v(20);
for( iVec_i i = v.begin() ; i != v.end() ; ++i )
*i = 1 + ( i - v.begin() );
std::random_shuffle(v.begin(),v.end());
// pick two and zero them out
v[3] = v[15] = 0;
// dump it for a peek
std::copy(v.begin(),
v.end(),
std::ostream_iterator<int>( std::cout, " " ) );
std::cout << std::endl;
// use special knowledge of the data to perform a linear
// time sort.
for( int i = 0 ; i < v.size() ; ++i )
{
while( ( v[i] != 0 ) && ( v[i] != (i+1) ) )
std::swap( v[i], v[v[i]-1] );
}
for( int i = 0 ; i < v.size() ; ++i )
if( v[i] == 0 )
std::cout << "Missing element " << (i+1) << std::endl;
std::copy(v.begin(),
v.end(),
std::ostream_iterator<int>( std::cout, " " ) );
std::cout << std::endl;
return 0;
}
You make one linear pass through the vector and examine the element at
each position. If it is 0, do nothing. If it is not, put it in the
"right" place in the vector by swapping, and examine the element you
swap in.
It looks like it could be O(n2) but I would argue that it is not, that
it is in fact linear. Worst case, say for the first element in the
vector you end up examining and swapping every other element. So you've
done order n compares (value to expected value in this position) and
order n swaps. Now you proceed through the vector and find everything
in place. So you do order n compares and no more swaps. Overall, you
end up comparing each element twice, and moving it at most twice. So it
is 2N... Then one more linear pass to find the zeros.
