Pagini recente » Cod sursa (job #3139684) | Cod sursa (job #2588610) | Cod sursa (job #1402599) | Cod sursa (job #340530) | Cod sursa (job #2562626)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("radixsort.in");
ofstream out("radixsort.out");
void RadixSortBase256(vector<int>& v) {
//aflam numarul minimul din vector
int n = v.size(), mn = v[0];
for (int i = 0; i < n; i++) {
if (v[i] < mn) mn = v[i];
}
//daca vectorul contine elemente negative, scadem minimul pentru a sorta un vector doar de elemente pozitive
if (mn < 0) {
for (int i = 0; i < n; i++) v[i] -= mn;
}
vector<int> liste[256];
for (int i = 0; i < n; i++) {
liste[(v[i] & 255)].push_back(v[i]);
}
//mutam valorile din liste inapoi in vector
v.clear();
for (int i = 0; i < 256; i++) {
for (int j = 0; j < liste[i].size(); j++) v.push_back(liste[i][j]);
liste[i].clear();
}
int bits = 8;
bool ok = false;
while (!ok) {
for (int i = 0; i < n; i++) {
liste[((v[i] >> bits) & 255)].push_back(v[i]);
}
//mutam valorile din liste inapoi in vector
v.clear();
//daca am procesat cifrele tuturor numerelor, inseamna ca vectorul este sortat
if (liste[0].size() == n) ok = 1;
for (int i = 0; i < 256; i++) {
for (int j = 0; j < liste[i].size(); j++) v.push_back(liste[i][j]);
liste[i].clear();
}
bits += 8;
}
//daca vectorul continea initial valori negative, adaugam minimul acestora pentru a obtine valorile initiale din vector
if (mn < 0) {
for (int i = 0; i < n; i++) v[i] += mn;
}
}
int main() {
int n, a, b, c;
vector <int> v;
in >> n >> a >> b >> c;
v.push_back(b);
for (int i = 1; i < n; i++) {
v.push_back((a * v[i - 1] + b) % c);
}
RadixSortBase256(v);
for (int i = 0; i < n; i += 10) {
out << v[i] << ' ';
}
}