Cod sursa(job #2433356)

Utilizator ShayTeodor Matei Shay Data 26 iunie 2019 23:49:05
Problema Sortare prin comparare Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.1 kb
#include <fstream>
#include <algorithm>
#include <math.h>
#include <assert.h>

inline void swap(int *a, int *b) {
	int *temp = std::move(a);
	a = std::move(b);
	b = std::move(temp);
}

inline void insertion_sort(int v[], int *begin, int *end) {
	int left = begin - v;
	int right = end - v;

	for (int i = left + 1; i <= right ; ++i) {
		int element = v[i];
		int j = i - 1;

		while ( j >= left && v[j] > element) {
			v[j + 1] = v[j];
			--j;
		}

		v[j + 1] = element;
	}

	return;
}

inline int* partition(int v[], int low, int high) {
	int pivot = v[high];
	int i = low - 1;

	for (int j = low ; j < high ; ++j) {
		if (v[j] <= pivot) {
			++i;
			std::swap(v[i], v[j]);
		}
	}

	std::swap(v[i + 1], v[high]);

	return (v + i + 1);
}

inline int* median(int v[], int *a, int *b, int *c) {
	if (*a < *b && *b < *c) 
        return b; 
  
    if (*a < *c && *c <= *b) 
        return c; 
  
    if (*b <= *a && *a < *c) 
        return a; 
  
    if (*b < *c && *c <= *a) 
        return c; 
  
    if (*c <= *a && *a < *b) 
        return a; 
  
    return b;
}

inline void intro_sort_utils(int v[], int *begin, int *end, int max_depth) {
	int size = end - begin;

	if (size < 32) {
		insertion_sort(v, begin, end);
		return;
	}

	if (max_depth == 0) {
		std::make_heap(begin, end + 1);
		std::sort_heap(begin, end + 1);
		return;
	}

	int *pivot = median(v, begin, begin + size / 2, end);

	swap(pivot, end);
	int *partition_point = partition(v, begin - v, end - v);
	intro_sort_utils(v, begin, partition_point - 1, max_depth - 1);
	intro_sort_utils(v, partition_point + 1, end, max_depth - 1);

	return;
}

inline void intro_sort(int v[], int *begin, int *end) {
	int max_depth = 2 * log(end - begin);
	intro_sort_utils(v, begin, end, max_depth);
	return;
}

int main() {
	std::ifstream cin("algsort.in");
	std::ofstream cout("algsort.out");
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n;
	cin >> n;

	assert(1 <= n && n <= 500000);
	int v[n];

	for (int i = 0 ; i < n ; ++i) {
		cin >> v[i];
	}

	intro_sort(v, v, v + n - 1);

	for (int i = 0 ; i < n ; ++i) {
		cout << v[i] << " ";
	}

	cout << '\n';
	return 0;
}