Tim Sort

[Все сортировки]

Теория: 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 обменов, которая и была приведена в реализации.

Реализация:

1. struct segment {
2.   int beg; // индекс первого элемента
3.   int len; // длина интервала
4.   segment(){}
5.   segment(int b, int l) : beg(b), len(l){}
6. };
7. // ответ должен быть в диапазоне (32,64]
8. inline int get_min_size(int n) {
9.   int r = 0;
10.   while (n >= 64) {
11.     n >>= 1;
12.     r |= n &1;
13.   }
14.   return n + r;
15. }
16. // Да простит меня Тим Петерсон, но вместо сортировки вставками
17. // я использую сортировку выбором
18. void selection_sort(vector<int> &mas, int beg, int last) {
19.   for (int i=beg; i<last;++i) {
20.     int min_pos = i;
21.     for (int j=i+1; j<last; ++j) {
22.       if (mas[j] < mas[min_pos])
23.         min_pos = j;
24.     }
25.     swap(mas[i],mas[min_pos]);
26.   }
27. }
28. const int dx = 1, dy = 2, dz = 3;
29. void merge(vector<int> &mas, vector<segment> &seg, bool isXY, vector<int> &tmp) {
30.   segment f = seg[seg.size() - dy];
31.   segment s = isXY ? seg[seg.size() - dx] : seg[seg.size() - dz];
32.   if (f.beg > s.beg) swap(f,s);
33.   int posF = 0, posS = s.beg, pos = f.beg-1;
34.   int lstF = f.len, lstS = s.beg + s.len;
35.   copy(mas.begin() + f.beg + posF, mas.begin() + f.beg + lstF, tmp.begin());
36.   int fAmount = 0, sAmount = 0;
37.   while (posF < lstF && posS < lstS) {
38.     if (tmp[posF] < mas[posS]) {
39.       mas[++pos] = tmp[posF++];
40.       ++fAmount; sAmount=0;
41.       if (fAmount == 7) {
42.         vector<int>::iterator it = upper_bound(tmp.begin() + posF, tmp.begin() + lstF, mas[posS]);
43.         copy(tmp.begin() + posF, it, mas.begin() + pos + 1);
44.         pos += it - (tmp.begin() + posF);
45.         posF += it - (tmp.begin() + posF);
46.       }
47.     }
48.     else {
49.       mas[++pos] = mas[posS++];
50.       fAmount=0; ++sAmount;
51.       if (sAmount == 7) {
52.         vector<int>::iterator it = upper_bound(mas.begin() + posS, mas.begin() + lstS, tmp[posF]);
53.         copy(mas.begin() + posS, it, mas.begin() + pos + 1);
54.         pos += it - (mas.begin() + posS);
55.         posS += it - (mas.begin() + posS);
56.       }
57.     }
58.   }
59.   copy(tmp.begin() + posF, tmp.begin() + lstF, mas.begin() + pos + 1);
60. }
61. void try_merge(vector<int> &mas, vector<segment> &seg, vector<int> &tmp, bool is_merge = false) {
62.   while (seg.size() > 1) {
63.     int x = seg[seg.size() - dx].len;
64.     int y = seg.size() < 2 ? 0 : seg[seg.size() - dy].len;
65.     int z = seg.size() < 3 ? 0 : seg[seg.size() - dz].len;
66.     if (seg.size() >= 3 && z <= x + y) {
67.       if (z < x) {
68.         merge(mas,seg,false,tmp);
69.         seg[seg.size() - dz].len += seg[seg.size() - dy].len;
70.         seg[seg.size()- dy] = seg[seg.size()- dx];
71.         goto POP_BACK;
72.       }
73.       else {
74.         merge(mas,seg,true,tmp);     
75.         seg[seg.size() - dy].len += seg[seg.size() - dx].len;
76.         goto POP_BACK;
77.       }
78.     }
79.     else if (is_merge || y <= x) {
80.       merge(mas,seg,true,tmp);
81.       seg[seg.size() - dy].len += seg[seg.size() - dx].len;
82.       goto POP_BACK;
83.     }
84.     else
85.       break;
86. POP_BACK: seg.pop_back();
87.   }
88. }
89. void tim_sort(vector<int> &mas) {
90.   int n = mas.size();
91.   vector<int> tmp(n);
92.   int min_size = get_min_size(n);
93.   int beg = 0, size = min_size;
94.   vector<segment> seg;
95.   seg.reserve((n-1)/min_size + 1);
96.  
97.   for (int i=0;i<n;i+=min_size) {
98.     size = min(min_size,n-i);
99.     selection_sort(mas,i,i+size); 
100.     seg.push_back(segment(i,size));
101.     try_merge(mas, seg, tmp);
102.   }
103.   while (seg.size() != 1) {
104.     try_merge(mas, seg, tmp, true);
105.   }
106. }

* This source code was highlighted with Source Code Highlighter.

P.S: Признаюсь я изначально не возлагал больших надежд на эту сортировку(особенно на свою эффективную реализацию), но должен признать, что был не прав. Данная реализация зашла за 0.061 с, в то время, когда быстрая работал за 0.059 с. Учитывая, что в данную реализацию можно добавить копирование меньшего подмассива + дописать бинарный поиск по не возрастанию, данная сортировка становится пожалуй лучшей для сортировки случайного набора данных. Разработчики Python не могли ошибаться =).