вторник, 1 февраля 2011 г.

Карманная сортировка (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.

Комментариев нет:

Отправить комментарий