Да се напише програма, която сортира (в нарастващ ред) масив от цели, неотрицателни числа в интервала [0, 134217728]. Размерът на масива е <= 134217728.
Нека масивът е глобална променлива. Попълването му с данни и другите инициализации направете в main функцията, а самото сортиране изнесете в отделна функция sort().
Използвайте това, че масивът се състои само от цели неотрицателни числа, за да направите максимално бърза функцията sort().
Числата в масива ще са случайни, но еднакви за всички тестове.
Размерът на масива ще е голям, примерно от 50 000 000 до 134 217 728, за да могат да се отличат по-добре разликите във времената. Ако желаете да ползвате статична памет може да се наложи да увеличите системния стек. Примерно под Debian по подразбиране той е 8192 kbytes. За да го увеличите ползвайте командата ulimit -s value, където value е: размер в kbytes или unlimited, за да премахнете ограничението.
Програмите ще се тестват на 32 битов, едноядрен процесор от фамилията x86. Максималната памет, която програмите могат да ползват е 1GiB.
Първите 3-ма от вас, които направят по-бърза функция sort() от асистента, ще получат пълния брой точки от упражненията.
Изпращайте решенията си (само изходния код) на e-mail-а до 8:03 часа на 8 март 2010 г. След като програмите бъдат тествани резултатите ще се публикуват тук. Тогава ще бъде публикуван и кодът на асистента.
Съществува алгоритъм за сортиране на цели, неотрицателни числа, в интервала [0, max] със сложност O(n). n е броят на числата, а max - най-голямото от тях. Алгоритъмът се нарича броене на честоти. За да го приложим ни е нужна достатъчно памет за масив с max на брой елемента, в който запазваме честотата на срещане на всяко число.
Ако масивът, който искаме да сортираме се казва „a“, а този, в който пазим честотите на срещане - freq то алгоритъмът е следният:
Зануляваме масива freq.
За всяко число num от масива „a“, увеличаваме с 1 стойността на елемента на позиция num в масива freq.
Започваме да запълваме от началото масива „a“, като за всяко число f, което е на позиция num от масива freq, добавяме числото num, f на брой пъти в масива „a“.
Пример 1: Масивът „a“ преди сортирането: 2 2 1 2 1 Масивът freq, след преброяването: 0 2 3 Масивът „a“ след сортирането: 1 1 2 2 2
Пример 2: Масивът „a“ преди сортирането: 4 1 3 6 4 1 1 10 1 Масивът freq, след преброяването: 0 4 0 1 2 0 1 0 0 0 1 Масивът „a“ след сортирането: 1 1 1 1 3 4 4 6 10
Алгоритъмът е реализиран във файла counting_sort.cpp. Той използва файловете sort.h и stopwatch.h
Други подобни алгоритми са bucket sort и radix sort.
Още връзки към материали за radix sort и сравнение между различни алгоритми, предостави колегата Калин Венков: 1, 2, 3.
Програмите са леко променени, за да могат да бъдат тествани при едни и същи условия. Това не би трябвало да се е отразило на бързодействието им. За интересуващите се, честотата на процесора използван за тестването е 1.6 GHz.
Кодът на Константина Граматова е написан на Java и не влиза в официалното класиране. Нейните времена не са съпоставими с другите, поради различната среда, в която се изпълнява програмата ѝ.
| Масив от числа <= 1000 | Масив от числа <= 134217728 | ||||||||||
| Размер на масива | 40 | 50000 | 1000000 | 50000000 | 134217728 | 40 | 50000 | 1000000 | 50000000 | 134217728 | |
| Асистентът | 0 с | 0 с | 0.030 с | 1.290 с | 3.460 с | 2.690 с | 2.790 с | 3.500 с | 16.700 с | 38.900 с | |
| Павел Кюркчиев | 0 с | 0.010 с | 0.170 с | 8.730 с | 23.500 с | 0 с | 0.010 с | 0.210 с | 11.250 с | 36.150 с | |
| Калин Венков | 0 с | 0.010 с | 0.190 с | 10.350 с | 27.480 с | 0 с | 0.010 с | 0.230 с | 12.610 с | 39.810 с | |
| Кристиан Милев | 0 с | 0.010 с | 0.360 с | 22.370 с | 1 мин 2.800 с | 0 с | 0.010 с | 0.400 с | 24.240 с | 1 мин 7.940 с | |
| qsort() cstdlib.h | 0 с | 0.040 с | 0.850 с | 52.610 с | 2 мин 26.380 с | 0 с | 0.040 с | 0.870 с | 55.400 с | 2 мин 38.610 с | |
| Васил Рангелов | 0 с | 0.170 с | 5.600 с | 5 мин 34.390 с | --- | 0 с | 0.170 с | 5.300 с | > 5 мин | --- | |
| Нина Хъркова | 0 с | 14.940 с | > 5 мин | --- | --- | 0 с | 14.930 с | > 5 мин | --- | --- | |
| К. Граматова (Java) | 0 с | 0.053 с | 0.427 с | 17.700 с | 48.198 с | 0 с | 0.101 с | 0.402 | 21.853 с | 1 мин 0.373 с | |
Павел Кюркчиев и Калин Венков получават пълния възможен брой точки от упражненията - 45.
Останалите получават по 1 точка бонус за участие.
