<< | к задаче | главная | печатать | обсудить(0 сообщений) >>
Задача: Поразрядная сортировка массива подсчетом
Псевдокод: поразрядная сортировка подсчетом, общий алгоритм управление:
  1. // Наш исходный сортируемый массив
  2. x = {..<int> elements to be sorted...}
  3.  
  4. // Вспомогательная переменная
  5. rangepow = 1
  6.  
  7. // Вспомогательный массив,
  8. // копирующий исходный X
  9. source = array<int>[n] filled 0
  10.  
  11. for step = 0 to width-1
  12.  
  13. // массив подсчета
  14. count = array<int>[range] filled 0
  15.  
  16. // Копируем в source содержимое X
  17. // на текущей итерации
  18. source[] = copy of x[]
  19.  
  20. // Получаем в count пока просто
  21. // количества текущих разрядов
  22. for i = 0 to n-1
  23. // d - это значение текущего разряда
  24. // для каждого нашего числа
  25. d = (source[i] / rangepow) % range
  26. count[ d ]++
  27.  
  28. // Завершаем формирование count, т.е. получаем
  29. // количество элементов менших индекса
  30. summNum = 0 // вспомогательная переменная
  31. for i = 0 to range-1
  32. tmp = count[i]
  33. count[i] = summNum
  34. summNum += tmp
  35.  
  36.  
  37. // Завершающий этап "вставка"
  38. for i = 0 to n-1
  39. d = (source[i] / rangepow) % range;
  40. x[ count[d] ] = source[i];
  41. count[d]++; // Очень важная конструкция:
  42. // для случая посторяющихся чисел.
  43. }
  44. rangepow *= range
  45.  

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