Понимание Radix Sort in C

Question

Я использую этот program here для ознакомления, как реализуется алгоритм. Я понимаю большую часть этой части, кроме этой части:

/* 
* update all the buckets. If bucket[8] has 2, 
* then there are 2 elements present till bucket 8 
*/ 
for (i = 1; i < 10; i++) 
     bucket[i] = bucket[i] + bucket[i-1]; 

Я не понимаю, что автор делает в этом цикле. Может кто-нибудь объяснить, что происходит?
И да, я использую ручку-бумагу, чтобы посмотреть, что происходит. Просто подумал, что я могу уточнить, что

Answer 1

Если вы в замешательстве с этой строкой, вы можете прочитать о сортировке. Одна из важных вещей, которые нужно понять, заключается в том, что она не сортируется сама по себе. Существует под-алгоритм, который должен использоваться, и он часто учитывает сортировку.

Ссылка, которую вы указали, не говорит об этом, и это, по-моему, важное замешательство. Когда вы читаете

«Во время первого прохода, сортировки все данные на основе наименьшего значащего бита»

Он не говорит, как вам разобраться. Вы можете сортировать с любым другим стабильным типом, и код сильно изменится.

Все это, чтобы сказать, что если это единственная линия, которую вы не понимаете, вы получили разовое определение радикса. Читайте о подсчете сортировки, чтобы понять, как это работает, и убедитесь, что вы понимаете, почему это хороший выбор в качестве подпрограммы сортировки radix.

Answer 2

Эта функция принимает суммарную сумму, теперь ведро [i] содержит кумулятивную сумму самого себя и всех ковшей перед ним. Что означает комментарий, так это то, что ведро [8] == 2 означало бы, что сумма от ковшей от 0 до 8 = 2

Редактировать: Лично я думаю, что http://www.youtube.com/watch?v=Nz1KZXbghj8&noredirect=1 имеет отличное объяснение рода radix.