3 ms·
Sigh, don't have an SO account but if I did, I would suggest this code which I call randsort -- #include <stdint.h> #include <stdio.h> #include <stdli
by ChuckMcM 13y ago
Sigh, don't have an SO account but if I did, I would suggest this code which I call randsort --
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
int
main(int argc, char *argv[]) {
int i, ndx;
double my_numbers[10];
double sorted_numbers[10];
uint16_t picked;
for (i = 1; i < argc; i++) {
my_numbers[i-1] = atof(argv[i]);
}
while (1) {
picked = 0;
ndx = 0;
/* sort the numbers */
while (picked != 0x3ff) {
i = (rand() / 100) % 10;
if ((picked & (1 << i)) == 0) {
picked |= (1 << i);
sorted_numbers[ndx++] = my_numbers[i];
}
}
/* verify they sorted correctly */
for (i = 8; i >= 0; i--) {
if (( i == -1) || (sorted_numbers[i] > sorted_numbers[i+1])) {
break;
}
}
if (i == -1) {
printf(" Sorted: \n");
for (i = 0; i < 10; i++) {
printf(" %d: %f\n", i, sorted_numbers[i]);
}
exit(0);
}
}
}
- demallien 13y agoNice. Is that O(e^n)? Out of curiosity, why do you divide the rand() by 100 before applying the mod?
- ChuckMcM 13y agoNo reason on the divide. Just because. That is probably a reasonable guess on the big O value. Clearly O(rand) is cheeky but in accurate. And the PRNG will walk the number space so it will eventually succeed, but computing how long it will take for 'n' numbers eludes my math reasoning skills.
- emilv 13y ago> the PRNG will walk the number space Are you sure? What if there's an infinite amount of tries to get to a certain number? You can of course reason about the average case, but maybe the worst case (when there's an input number which is never found by the PRNG) does never halt. > O(rand) For sorting algorithms we usually compare in the number of input elements. You can reason about the average case where the numbers are found in average time so you can consider the number of iterations to find the correct number a constant (a very large constant but a constant nonetheless).
- akx 13y agoAnd since `srand(time(NULL))` isn't ever called, it's deterministic, too!
- nitrogen 13y agoIs that the case for all platforms and C libraries? Also, isn't seeding with the current time a way to guarantee deterministic behavior? An attacker of such an algorithm probably knows what time it is, and users probably don't expect all invocations within a given second to return the same results.