Fairly often we have to sort the sequence of objects during solving of problem. I think that Divide and Conquer algorithms are the most effective in solving problem of sortings, here is two of them:

Quick sort algorithm [C++]:

template <typename T>
void quick_sort(T* a, std::size_t begin, std::size_t end) {
	std::size_t i = begin, j = end;
	T x = a[ (begin+end)/2 ];
		do {
		while (a[i] < x) ++i;
		while (a[j] > x) --j;
			if (i <= j) {
			if (i < j) { std::swap(a[i], a[j]); }
			++i; --j;
		}
	} while (i <= j);

	if (i < end)
		quick_sort(a, i, end);
	if (begin < j)
		quick_sort(a, begin, j);
}

Merge sort algorithm [C++]:

template <typename T>
void merge(T * a, std::size_t begin, std::size_t center, std::size_t end) {
	std::size_t i = begin, j = center+1, t = 0;  
	T* buf = new T[end-begin+1];

	while (i <= center && j <= end) {
		if (a[i] < a[j])
			buf[t++] = a[i++];
		else
			buf[t++] = a[j++];
	}

	while (j <= end)	buf[t++] = a[j++];
	while (i <= center)	buf[t++] = a[i++];

	for (t = 0; t < end-begin+1; t++)
		a[begin+t] = buf[t];

	delete [] buf;
}

template <typename T>
void merge_sort(T* a, std::size_t begin, std::size_t end) {
	if (begin < end) {
		std::size_t split = (begin+end)/2;
		merge_sort(a, begin, split);
		merge_sort(a, split+1, end);
		merge(a, begin, split, end);
	}
}

Perfomance:

         | quick sort | merge sort 
---------|------------|------------
best     | O(n log n) | O(n log n)
average  | O(n log n) | O(n log n)
worst    | O(n^2)     | O(n log n) 

As you can see in theory quick_sort not so effective beside merge_sort. But some test and measuring of used time, gives:

Merge sort practice tests
1000000 elements 0.24 sec
	+ 0.20
2000000 elements 0.44 sec
	+ 0.20
3000000 elements 0.64 sec
	+ 0.20
4000000 elements 0.84 sec
	+ 0.22
5000000 elements 1.06 sec
	+ 0.17
6000000 elements 1.23 sec
	+ 0.24
7000000 elements 1.47 sec
	+ 0.21
8000000 elements 1.68 sec
	+ 0.20
9000000 elements 1.88 sec
	+ 0.20
10000000 elements 2.08 sec

Quick sort practice tests
1000000 elements 0.19 sec
	+ 0.18
2000000 elements 0.37 sec
	+ 0.16
3000000 elements 0.53 sec
	+ 0.18
4000000 elements 0.71 sec
	+ 0.17
5000000 elements 0.88 sec
	+ 0.23
6000000 elements 1.11 sec
	+ 0.15
7000000 elements 1.26 sec
	+ 0.16
8000000 elements 1.42 sec
	+ 0.21
9000000 elements 1.63 sec
	+ 0.17
10000000 elements 1.80 sec

Here is code of tests, please, share with results of test on your local machine at comments.

#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cstdio>
#include <ctime>

#include "sort.hpp"

#define SIZE			10000000
#define START			1000000
#define DIFF			1000000

using namespace std;

/* merge sort testing */
void test_merge_sort() {

	printf("\nMerge sort practice tests\n");
	uint8_t * a = new uint8_t [SIZE];
	for (uint8_t * i = a; i < a+SIZE; ++i)
		*i = rand()%256;
	float elapsed_time, prev_elapsed_time = 0;

	for (size_t size = START; size <= SIZE; size += DIFF) {
		clock_t begin = clock();
		merge_sort(a, 0, size-1);
		clock_t end = clock();

		elapsed_time = float(end - begin) / CLOCKS_PER_SEC;

		if (prev_elapsed_time != 0)
			printf("\t+ %.2f\n", elapsed_time-prev_elapsed_time);

		prev_elapsed_time = elapsed_time;

		for (uint8_t * i = a; i+1 < a+size; ++i) assert(*i <= *++i);

		printf("%d elements %.2f sec\n", size, elapsed_time);
	}
}

/* quick sort test */
void test_quick_sort() {

	printf("\nQuick sort practice tests\n");
	uint8_t * a = new uint8_t [SIZE];
	for (uint8_t * i = a; i < a+SIZE; ++i)
		*i = rand()%256;
	float elapsed_time, prev_elapsed_time = 0;

	for (size_t size = START; size <= SIZE; size += DIFF) {
		clock_t begin = clock();
		quick_sort(a, 0, size-1);
		clock_t end = clock();

		elapsed_time = float(end - begin) / CLOCKS_PER_SEC;

		if (prev_elapsed_time != 0)
			printf("\t+ %.2f\n", elapsed_time-prev_elapsed_time);

		prev_elapsed_time = elapsed_time;

		for (uint8_t * i = a; i+1 < a+size; ++i) assert(*i <= *++i);

		printf("%d elements %.2f sec\n", size, elapsed_time);
	}
}

int main() {
	test_merge_sort();
	test_quick_sort();

	return 0;
}

Давайте делиться своими макросами и функциями

Вот некоторые макросы которые заранее прописаны в шаблон моего кода ;) Иногда надо просто повторять некоторые действия, но не хочется расписывать для этого цикл for.

#define repeat(a) for (size_t i___ = 0; i___ < (a); ++i___)

repeat(10) cout << "hi";

Довольно часто мы сортируем весь контейнер.

#define whole(a) a.begin(), a.end()

sort(whole(vector_dots));

Получение комнаты числа:

inline int digit_of(int n, int i) {
    while (i-- && n /= 10); return n%10;
}

Hi. I'm beginner at competitive programming and there is 100% that this topic is not original, but, in spite of this, I decided to publish it. So, (you are still reading, that's achievement for me :D). Sometimes we need to associate string with some object and then quickly find it by those key string. prefix trees are good thing to do it. For more information about them read this http://en.wikipedia.org/wiki/Prefix_tree, or this http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D1%84%D0%B8%D0%BA%D1%81%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE.

Algorithm complexities:

Add element O(1) // iterations are equal to length of string

Remove element O(1)

Search element O(1)

Memory: In worse case each bound's weight is 300 bytes, but you can reduce this by using function to get child id by character (see in code), and saving pointer to object you are pushing.

Need a more detailed analysis, but, in generally we can see that this structure is very fast, but not so effective in memory usage, you can use it when you are need to balance memory and time.

Here is realization, hope some will use in their solution:

template <class T, std::size_t ALPHA_SIZE>
class Npi {
        public:
		prefix(std::size_t (* f)(char))
			: I(f), m_root(new node)
		{}

		~prefix() {
			rec_del(m_root);
		}

		T & operator[] (std::string s) {
			node * curr = m_root;
			for (auto e: s) {
				size_t i = I(e);
				if (curr->next[i] != nullptr) {
					curr = curr->next[i];
				} else {
					curr = curr->next[i] = new node;
				}
			}
			curr->used = 1;
			return curr->val;
		}

		bool thereis(std::string s) {
			node * curr = m_root;
			for (auto e: s) {
				size_t i = I(e);
				if (curr->next[i] != nullptr) {
					curr = curr->next[i];
				} else {
					return 0;
				}
			}
			return curr->used;
		}

	private:
		struct node {
			T val;
			uint8_t used;
			node * next[ALPHA_SIZE];
			node(): used(0) {
				for (size_t i = 0; i < ALPHA_SIZE; ++i)
					next[i] = nullptr;
			}
			~node() {}

		} * m_root;
		std::size_t (* I)(char);

		void rec_del(node * curr) {
			if (curr == nullptr) {
				return;
			} else {
				for (size_t i = 0; i < ALPHA_SIZE; ++i)
					rec_del(curr->next[i]);
			}

			delete curr;
		}
};

And this is test program.

#include <iostream>
#include <cassert>
#include <cstdio>
#include <string>

#include "prefix_tree.hpp"

inline std::size_t iofc(char c) {
	return static_cast<std::size_t>(c);
}

int main() {
	using namespace std;

	tree::prefix<int, 127> tree(iofc);

	tree["hello this is where you are!"] = 2;

	assert(tree.thereis("0000000000000000000000000000") == 0);
	assert(tree.thereis("hello this is where you are!") == 1);


	return 0;
}

Yes, many useful functions are absent, (such as remove for example, iterators). But the first step is made, so, let's improve it, good luck and have fun!

Hello, Codeforces!