Anonymous user
Sorting algorithms/Cycle sort: Difference between revisions
no edit summary
(Added Ruby) |
No edit summary |
||
Line 112:
0 0 1 1 2 2 2 2 3 4 5 5 6 7 8 9
writes: 10
</pre>
=={{header|C++}}==
Based on example code on Wikipedia
<lang Cpp>
#include <time.h>
#include <iostream>
#include <vector>
using namespace std;
class cSort
{
public:
void doIt( vector<unsigned> s )
{
sq = s; display(); c_sort();
cout << "writes: " << wr << endl; display();
}
private:
void display()
{
copy( sq.begin(), sq.end(), ostream_iterator<unsigned>( std::cout, " " ) );
cout << endl;
}
void c_sort()
{
wr = 0;
unsigned it, p, vlen = static_cast<unsigned>( sq.size() );
for( unsigned c = 0; c < vlen - 1; c++ )
{
it = sq[c];
p = c;
for( unsigned d = c + 1; d < vlen; d++ )
if( sq[d] < it ) p++;
if( c == p ) continue;
doSwap( p, it );
while( c != p )
{
p = c;
for( unsigned e = c + 1; e < vlen; e++ )
if( sq[e] < it ) p++;
doSwap( p, it );
}
}
}
void doSwap( unsigned& p, unsigned& it )
{
while( sq[p] == it ) p++;
swap( it, sq[p] );
wr++;
}
vector<unsigned> sq;
unsigned wr;
};
int main(int argc, char ** argv)
{
srand( static_cast<unsigned>( time( NULL ) ) );
vector<unsigned> s;
for( int x = 0; x < 20; x++ )
s.push_back( rand() % 100 + 21 );
cSort c; c.doIt( s );
return 0;
}
</lang>
{{out}}
<pre>
38 119 38 33 33 28 24 101 108 120 99 59 69 24 117 22 90 94 78 75
writes: 19
22 24 24 28 33 33 38 38 59 69 75 78 90 94 99 101 108 117 119 120
</pre>
| |||