ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Serge Nozhenko                       2:5020/175.1   02 Jan 2002  17:58:26
 To : Stepan M. Pechkin
 Subject : CountSort
 -------------------------------------------------------------------------------- 
 

  SP>     CountSort - это, насколько я понимаю, что-то вроде BucketSort, хотя в
  SP> изложении нашего дурного препода он больше похож на RadixSort. То есть,
  SP> алгоритм сортировки численных данных, где используется массив-счетчик и
  SP> данные высыпаются в результирующий массив сообразно счетчику.
  SP>     Вопрос такой: сортируются числа от 0 до 999. Один раз прогоняется эта
  SP> радость по всему массиву, второй раз - сначала по старшей цифре, потом по
  SP> средней, потом по младшей, а третий раз - сначала по младшей, потом по
  SP> средней, а потом по старшей. Требуется доказать, что во всех трех случаях
  SP> получится отсортированный массив, а потом сказать, какой способ лучше.
  SP>     Пробовали - третий вариант ни у кого не получился, в том числе и у
  SP> препода. Hо препод такой дурной, что это ни о чем не говорит. Я вот
  SP> думаю-думаю, и кажется мне, что получится. Развейте сомнения.
 
   Должно получиться. Второй и третий случаи - это просто разновидность
 RadixSort, в которой процедура подсчета, аналогичная применяемой в CountSort для
 всего массива, используется для экономичного распределения памяти при сортировке
 по одному разряду.
 
  Serge
 
 P.S. У Кнута это во всех подробностях описано.
 
 --- Golded 2.41+
  * Origin: Moccoletto (2:5020/175.1)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    CountSort   Stepan M. Pechkin   02 Jan 2002 00:26:00   CountSort   Serge Nozhenko   02 Jan 2002 17:58:26