<< | к задаче | главная | печатать | обсудить(0 сообщений) >>
Задача: Поразрядная сортировка, общий принцип
Псевдокод: поразрядная сортировка на односвязном списке управление:
  1. // Возвращает ссылку на отсортированный односвязный список
  2. // Передается: та же ссылка list, но на неотсортированный список и width
  3. function radixList(list, width, range)
  4.  
  5. // Дополнительные переменные типа списка(listtype)
  6. // out - результирующий список, который пока идиентичен
  7. // исходному
  8. out = list;
  9.  
  10. // Массивы ссылок на головы и хвосты списков карманов
  11. head = newArrayOfList[range]
  12. tail = newArrayOfList[range]
  13.  
  14. // Вспомогательная переменная
  15. rangepow = 1;
  16.  
  17. for step = 0 to (width - 1)
  18. // Обнуляем все карманы
  19. for i = 0 to range - 1
  20. head[i] = NULL
  21. tail[i] = NULL
  22.  
  23. // РАСПРЕДЕЛЕНИЕ >>
  24. // Проходимся по всему исходному списку
  25. // пока не будет достигнут конец
  26. //(ссылка на текущий элемент - в никуда)
  27. while list != NULL
  28. // Получаем значение step-го разряда текущего элемента(ключа)
  29. // ("/" - целочисленное деление)
  30. currDigit = (list->val / rangepow) % range;
  31.  
  32. // получаем ссылку на хвост текущего кармана
  33. temp = tail[currDigit];
  34.  
  35. // Если карман пуст, то текущий элемент
  36. // будет его головой, иначе добавляем текущий элемент
  37. // в конец кармана
  38. if head[currDigit]=NULL head[currDigit] = list;
  39. else temp->next = list;
  40.  
  41. // Обновляем хвост текущего кармана
  42. // чтобы теперь он указывал на новый добавленный
  43. // элемент
  44. temp = tail[currDigit] = list;
  45. temp->next = NULL;
  46.  
  47. // Переходим к следующему элементу списка
  48. list = list->next;
  49. end while
  50.  
  51.  
  52. // Находим в переменную i первый непустой карман,
  53. // чтобы с него начать сборку.
  54. for i = 0 to (range - 1)
  55. if ( head[i] != NULL ) break;
  56.  
  57. // СБОРКА >>
  58. list = head[i];
  59. temp = tail[i];
  60. for currDigit = i+1 to range
  61. if head[currDigit] != NULL
  62. temp->next = head[currDigit];
  63. temp = tail[currDigit];
  64.  
  65. // !!! важный момент: чтобы на след. итерации в currDigit
  66. // при "распределении" получить следующий разряд - возводим
  67. // в степерь вспомогательную переменную:
  68. rangepow *= range;
  69. end for
  70.  
  71. // Возвращаем ссылку на первый элемент отсортированного списка
  72. return out;
  73.  

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