Pagini recente » Rezultatele filtrării | Cod sursa (job #1104326) | Cod sursa (job #2082880)
#include <bits/stdc++.h>
using namespace std;
namespace algsort {
constexpr int DIM = 500005;
int buffer[DIM];
constexpr int RADIX_LOG = 8;
constexpr int RADIX_STEPS = sizeof(int) * 8 / RADIX_LOG;
constexpr int RADIX_SIZE = (1 << RADIX_LOG);
constexpr int RADIX_MASK = (1 << RADIX_LOG) - 1;
int radix_freq[RADIX_SIZE];
class heap {
public:
heap(size_t max_size) :
data_(max_size + 1, -INF),
last(1) {
}
int top() {
return data_[1];
}
void push(int value) {
data_[last++] = value;
int curr = (int)last - 1;
while (curr != 1 && data_[curr] < data_[curr / 2]) {
swap(data_[curr], data_[curr / 2]);
curr /= 2;
}
}
void pop() {
last--;
swap(data_[1], data_[last]);
int curr = 1;
while (2 * curr < (int)last) {
if (2 * curr + 1 >= (int)last) {
if (data_[curr] <= data_[2 * curr])
break;
swap(data_[curr], data_[2 * curr]);
curr *= 2;
continue;
}
if (data_[2 * curr] <= data_[2 * curr + 1] && data_[curr] > data_[2 * curr]) {
swap(data_[curr], data_[2 * curr]);
curr *= 2;
continue;
}
if (data_[2 * curr] > data_[2 * curr + 1] && data_[curr] > data_[2 * curr + 1]) {
swap(data_[curr], data_[2 * curr + 1]);
curr *= 2; curr++;
continue;
}
break;
}
}
private:
static constexpr int INF = numeric_limits< int >::max();
vector< int > data_;
size_t last;
};
void merge_sort(int v[], size_t size) {
if (size <= 1)
return;
size_t split = size / 2;
merge_sort(v, split);
merge_sort(v + split, size - split);
//merge
size_t buffer_size = 0;
size_t i = 0, j = split;
while (i < split && j < size)
if (v[i] <= v[j])
buffer[buffer_size++] = v[i++];
else
buffer[buffer_size++] = v[j++];
while (i < split)
buffer[buffer_size++] = v[i++];
while (j < size)
buffer[buffer_size++] = v[j++];
for (size_t index = 0; index < size; ++index)
v[index] = buffer[index];
}
void radix_sort(int v[], size_t size) {
for (int step = 0; step < RADIX_STEPS; ++step) {
for (size_t i = 0; i < size; ++i)
++radix_freq[(v[i] >> (step * RADIX_LOG)) & RADIX_MASK];
for (int i = 1; i < RADIX_SIZE; ++i)
radix_freq[i] += radix_freq[i - 1];
for (int i = int(size) - 1; i >= 0; --i)
buffer[--radix_freq[(v[i] >> (step * RADIX_LOG)) & RADIX_MASK]] = v[i];
for (size_t i = 0; i < size; ++i)
v[i] = buffer[i];
memset(radix_freq, 0, sizeof radix_freq);
}
}
void heap_sort(int v[], size_t size) {
heap h(size);
for (size_t i = 0; i < size; ++i)
h.push(v[i]);
for (size_t i = 0; i < size; ++i) {
v[i] = h.top();
h.pop();
}
}
void dumb_sort(int v[], size_t size) {
for (size_t i = 0; i < size; ++i)
for (size_t j = i + 1; j < size; ++j)
if (v[i] > v[j])
swap(v[i], v[j]);
}
void sqrt_sort(int v[], size_t size) {
size_t sqrt_size = size_t(sqrt(size));
vector< size_t > start_indexes;
for (size_t i = 0; i < size; i += sqrt_size) {
dumb_sort(v + i, min(sqrt_size, size - i));
start_indexes.push_back(i);
}
for (size_t i = 0; i < size; ++i) {
size_t pos_minimum = 0;
int minimum = -1;
for (size_t j = 0; j < start_indexes.size(); ++j) {
if (start_indexes[j] < (j + 1) * sqrt_size && start_indexes[j] < size
&& (minimum > v[start_indexes[j]] || minimum == -1))
minimum = v[start_indexes[j]], pos_minimum = j;
}
buffer[i] = minimum;
start_indexes[pos_minimum]++;
}
for (size_t i = 0; i < size; ++i)
v[i] = buffer[i];
}
void quick_sort(int v[], size_t size) {
if (size <= 1)
return;
size_t pivot_position = rand() % size;
int pivot = v[pivot_position];
int i = -1, j = (int)size;
while (true) {
do {
++i;
} while (v[i] < pivot);
do {
--j;
} while (v[j] > pivot);
if (i >= j)
break;
swap(v[i], v[j]);
}
quick_sort(v, (size_t)i);
quick_sort(v + j + 1, size - j - 1);
}
}
void solve() {
size_t size;
cin >> size;
vector< int > values(size);
for (auto& it : values)
cin >> it;
//algsort::merge_sort(values.data(), values.size());
//algsort::radix_sort(values.data(), values.size());
//algsort::sqrt_sort(values.data(), values.size());
algsort::quick_sort(values.data(), values.size());
//algsort::heap_sort(values.data(), values.size());
for (auto&& it : values)
cout << it << ' ';
cout << endl;
};
int main() {
assert(freopen("algsort.in", "r", stdin));
assert(freopen("algsort.out", "w", stdout));
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
srand((unsigned int)time(0));
solve();
return 0;
}