[Все сортировки]
Теория: habrahabr.ru, код реальных мужиков на С (зеркало)
Практика: informatics.mccme.ru
Немного размышлений:
1) Не так давно общественность была взбудоражена малоизвестной сортировкой Tim Sort, которая творит чудеса. Поэтому возникло желание попробовать сделать ее реализацию. Когда разбирался в описании, представленном на хабре и в wikipedia, как в русской, так и в английской, возникли вопросы, на которые я не смог найти ответы. Больше всего вызывала вопросов та часть, в которой происходит эффективное слияние подмассивов, примерно равной длины. Т.к. я писал сортировку для случайного набора данных, поэтому хотелось избежать непоняток с волшебными длинами X,Y и Z, а именно просто сливать два последних подмассива, если они имеют одинаковую длину. Как показала практика в оригинальном алгоритме преследовалась та же идея.
Разбираясь в реализации на С(см. теория), было выведено правило грамотного слияния подмассивов с поддержанием баланса длин. Пусть X,Y,Z - длины верхних трех интервалов, которые лежат в стеке. Причем X – это последний элемент стека.
Правило следующее:
1. Повторяем пока выражение (Z > X + Y && Y > X) не станет истинным
2. Если количество элементов в стеке не меньше 3 и Z <= X + Y – сливаем Y c min(X,Z).
Иначе Если Y<=X – сливаем X c Y
3. Возвращаемся в п.1.
В wikipedia и на habr’e написано другое правило, в котором X и Z поменены местами, и по которому ничего путного сделать у меня не получилось.
2) В оригинальной идее предполагалось, что во временный массив помещается меньший из сливаемых подмассивов. При этом, если это левый подмассив, то формирование результирующего массива идет слева направо + используется бинарный поиск по не убыванию. В противном случае, когда правый подмассив имеет размер меньше чем левый, ответ формируется справа налево + используется бинарный поиск по не возрастанию. Скажу честно, мне было лень замачиваться на такие вещи, поэтому в приведенной реализации всегда копируется левый подмассив.
3) Для меня осталась загадкой, откуда у автора алгоритма Тима Петерсона такая любовь к сортировке вставками, которая требует в худшем случае n(n-1)/2 обменов. Хотя конечно, для худшего случая, когда массив упорядочен в обратном порядке, стоят нужные механизмы, которые реверснут массив за n/2 обменов, но все равно вопрос для меня остался открытым. В этом плане мне больше импонирует сортировка выбором, которая требует не более n обменов, которая и была приведена в реализации.
Реализация:
- struct segment {
- int beg; // индекс первого элемента
- int len; // длина интервала
- segment(){}
- segment(int b, int l) : beg(b), len(l){}
- };
- // ответ должен быть в диапазоне (32,64]
- inline int get_min_size(int n) {
- int r = 0;
- while (n >= 64) {
- n >>= 1;
- r |= n &1;
- }
- return n + r;
- }
- // Да простит меня Тим Петерсон, но вместо сортировки вставками
- // я использую сортировку выбором
- void selection_sort(vector<int> &mas, int beg, int last) {
- for (int i=beg; i<last;++i) {
- int min_pos = i;
- for (int j=i+1; j<last; ++j) {
- if (mas[j] < mas[min_pos])
- min_pos = j;
- }
- swap(mas[i],mas[min_pos]);
- }
- }
- const int dx = 1, dy = 2, dz = 3;
- void merge(vector<int> &mas, vector<segment> &seg, bool isXY, vector<int> &tmp) {
- segment f = seg[seg.size() - dy];
- segment s = isXY ? seg[seg.size() - dx] : seg[seg.size() - dz];
- if (f.beg > s.beg) swap(f,s);
- int posF = 0, posS = s.beg, pos = f.beg-1;
- int lstF = f.len, lstS = s.beg + s.len;
- copy(mas.begin() + f.beg + posF, mas.begin() + f.beg + lstF, tmp.begin());
- int fAmount = 0, sAmount = 0;
- while (posF < lstF && posS < lstS) {
- if (tmp[posF] < mas[posS]) {
- mas[++pos] = tmp[posF++];
- ++fAmount; sAmount=0;
- if (fAmount == 7) {
- vector<int>::iterator it = upper_bound(tmp.begin() + posF, tmp.begin() + lstF, mas[posS]);
- copy(tmp.begin() + posF, it, mas.begin() + pos + 1);
- pos += it - (tmp.begin() + posF);
- posF += it - (tmp.begin() + posF);
- }
- }
- else {
- mas[++pos] = mas[posS++];
- fAmount=0; ++sAmount;
- if (sAmount == 7) {
- vector<int>::iterator it = upper_bound(mas.begin() + posS, mas.begin() + lstS, tmp[posF]);
- copy(mas.begin() + posS, it, mas.begin() + pos + 1);
- pos += it - (mas.begin() + posS);
- posS += it - (mas.begin() + posS);
- }
- }
- }
- copy(tmp.begin() + posF, tmp.begin() + lstF, mas.begin() + pos + 1);
- }
- void try_merge(vector<int> &mas, vector<segment> &seg, vector<int> &tmp, bool is_merge = false) {
- while (seg.size() > 1) {
- int x = seg[seg.size() - dx].len;
- int y = seg.size() < 2 ? 0 : seg[seg.size() - dy].len;
- int z = seg.size() < 3 ? 0 : seg[seg.size() - dz].len;
- if (seg.size() >= 3 && z <= x + y) {
- if (z < x) {
- merge(mas,seg,false,tmp);
- seg[seg.size() - dz].len += seg[seg.size() - dy].len;
- seg[seg.size()- dy] = seg[seg.size()- dx];
- goto POP_BACK;
- }
- else {
- merge(mas,seg,true,tmp);
- seg[seg.size() - dy].len += seg[seg.size() - dx].len;
- goto POP_BACK;
- }
- }
- else if (is_merge || y <= x) {
- merge(mas,seg,true,tmp);
- seg[seg.size() - dy].len += seg[seg.size() - dx].len;
- goto POP_BACK;
- }
- else
- break;
- POP_BACK: seg.pop_back();
- }
- }
- void tim_sort(vector<int> &mas) {
- int n = mas.size();
- vector<int> tmp(n);
- int min_size = get_min_size(n);
- int beg = 0, size = min_size;
- vector<segment> seg;
- seg.reserve((n-1)/min_size + 1);
-
- for (int i=0;i<n;i+=min_size) {
- size = min(min_size,n-i);
- selection_sort(mas,i,i+size);
- seg.push_back(segment(i,size));
- try_merge(mas, seg, tmp);
- }
- while (seg.size() != 1) {
- try_merge(mas, seg, tmp, true);
- }
- }
* This source code was highlighted with Source Code Highlighter.P.S: Признаюсь я изначально не возлагал больших надежд на эту сортировку(особенно на свою эффективную реализацию), но должен признать, что был не прав. Данная реализация зашла за 0.061 с, в то время, когда быстрая работал за 0.059 с. Учитывая, что в данную реализацию можно добавить копирование меньшего подмассива + дописать бинарный поиск по не возрастанию, данная сортировка становится пожалуй лучшей для сортировки случайного набора данных. Разработчики Python не могли ошибаться =).
На втором этапе все временные файлы сливаются в один: 
После выполнения первых двух этапов мы получаем информацию о времени, которое было затрачено на их выполнение: 
Корректность сгенерированного файла можно проверить с помощью команды –check: 
Если файл сгенерирован, согласно требованиям условия задачи(см. 
