search

divyang4481 / mipt-hw

Automatically exported from code.google.com/p/mipt-hw
0 stars 0 forks source link

task05 RadixSort (Mishatkin) #10

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
mishatkin_vladimir/task04_RadixSort/

Original issue reported on code.google.com by sane.vova on 29 Sep 2012 at 10:52

GoogleCodeExporter commented 9 years ago 
mishatkin_vladimir/task05_RadixSort/

В предыдущем коммите неправильно указал 
номер задания. Теперь исправил.

Original comment by sane.vova on 29 Sep 2012 at 11:24

GoogleCodeExporter commented 9 years ago 
Решение корректное, но мудреное и 
неэффективное.

1. Вы выделяете память под отрицательные + 
положительные числа. Это уже 2n. Далее 
выделяете память в векторе векторов. Где в 
числах типа int хранятся десятичные разряды 
всех чисел. Это overkill...

2. В принципе операции деления и получения 
остатка от деления - затратные по времени. 
Поэтому radix-sort как правило реализуют по 
двоичным разрядам. Тогда получение нужного 
разряда - всего лишь логическое И по маске 
(пара тактов). А сортировка подсчетом в этом 
случае вырождается в разделение чисел на 2 
группы: с битом 1 и с битом 0.

В итоге у Вас и получилось (судя по заданию 
7), что Radix проигрывает всем, кроме InsertSort.

Решение принято.

Original comment by aivyu...@gmail.com on 28 Oct 2012 at 5:05