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

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