<< | к задаче | главная | печатать | обсудить(0 сообщений) >>
Задача: Поразрядная сортировка массива подсчетом
Исходник: Поразрядная сортировка массива подсчетом, неоптимизированная версия [C++, code #10, hits: 5764, рейтинг: 3/7,4.84(2476)] +
автор: this [добавлен: 21.01.2006] управление:
  1. // глобальные константы (значения заданы для примера)
  2. const int n = 10;
  3. const int width = 2;
  4. const int range = 10;
  5.  
  6. void RadixEnumSort(int x[]) {
  7. int source[n] = {0};
  8.  
  9. for (int step = 0, rangepow = 1; step < width; step++, rangepow *= range) {
  10.  
  11. int count[range] = {0};
  12. memcpy(source, x, sizeof(source));
  13.  
  14. for (int i = 0; i < n; i++) {
  15. int d = (source[i] / rangepow) % range;
  16. count[ d ]++;
  17. }
  18.  
  19. int summNum = 0;
  20. for (int i = 0; i < range; i++) {
  21. int tmp = count[i];
  22. count[i] = summNum;
  23. summNum += tmp;
  24. }
  25.  
  26. for (int i = 0; i < n; i++) {
  27. int d = (source[i] / rangepow) % range;
  28. x[ count[d] ] = source[i];
  29. count[d]++;
  30. }
  31. }
  32. }
Производительность: ~ О(width*(2n + range))
Расход памяти: ~ (2n + range)

+добавить реализацию
 
каталог | задачи | паттерны | исходники | стат | форумы | карта сайта | контакты | ссылки 
© 2000-2017 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.01393 секунд
Количество запросов к БД: 9, gzip: 3.1kb/11.0kb(72%)