Cod sursa(job #2618821)

Utilizator radustn92Radu Stancu radustn92 Data 26 mai 2020 13:04:34
Problema Sortare prin comparare Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstdlib>
#include <ctime>
using namespace std;

const int NMAX = 500505;
const int LMAX = (1 << 8);
int N, A[NMAX], aux[NMAX];
vector<int> orderedByByte[LMAX];

inline int getBits(int& value, int from, int to) {
	long long temp = ((1LL << to) - 1) & value;
	return temp >> from;
}

void sortArray() {
	for (int byteIdx = 0; byteIdx < 4; byteIdx++) {
		for (int byteValue = 0; byteValue < LMAX; byteValue++) {
			orderedByByte[byteValue].clear();
		}
		for (int idx = 1; idx <= N; idx++) {
			int byteValue = getBits(A[idx], byteIdx * 8, ((byteIdx + 1) * 8 - 1));
			orderedByByte[byteValue].push_back(A[idx]);
		}

		int nextPos = 1;
		for (int byteValue = 0; byteValue < LMAX; byteValue++) {
			for (auto& entry : orderedByByte[byteValue]) {
				A[nextPos++] = entry;
			}
		}
	}
}

int main() {
	freopen("algsort.in", "r", stdin);
	freopen("algsort.out", "w", stdout);

	srand(time(0));

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;
	for (int idx = 1; idx <= N; idx++) {
		cin >> A[idx];
	}

	sortArray();
	for (int idx = 1; idx <= N; idx++) {
		if (idx > 1) {
			cout << " ";
		}
		cout << A[idx];
	}
	cout << "\n";
	return 0;
}