Карманная сортировка (Bucket_sort)

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

Теория: Wikipedia + Кормен[п.8.4. Второе издание]

Практика: informatics.mccme.ru

Реализация:

1. const int MAX_VALUE = 2000; // значения массива [0, MAX_VALUE]
2. const int BUCKETS = 10;     // количество карманов
3. ...
4. void bucket_sort(vector<int> &mas) {
5.   vector<list<int> > mem(BUCKETS);
6.   for (int i=0;i<mas.size();i++) {
7.     int pos = (mas[i] - 1) / (MAX_VALUE / BUCKETS);
8.     list<int>::iterator it = mem[pos].begin();
9.     while (it != mem[pos].end() && *it < mas[i])
10.       it++;
11.     mem[pos].insert(it,mas[i]);
12.   }
13.   int pos = 0;
14.   for (int i=0;i<BUCKETS;i++) {
15.     for(list<int>::iterator it = mem[i].begin();it!= mem[i].end();it++)
16.     {
17.       mas[pos++] = *it;
18.     }
19.   }
20. }

* This source code was highlighted with Source Code Highlighter.