sorted arrays, theory and practice
The average time to check if a random array is sorted is e - 1. This was not the result I was expecting, but it’s also easy to check.
#include <stdio.h>
#include <stdlib.h>
typedef unsigned int unt;
const unt length = 100;
unt
sortlen(unt *arr)
{
unt i;
for (i = 0; i < length - 1; i++)
if (arr[i] > arr[i + 1])
break;
return i + 1;
}
void
shuffle(unt *arr)
{
unt i;
for (i = 0; i < length - 1; i++) {
unt j = i + arc4random_uniform(length - i);
unt t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
int
main(int argc, char **argv)
{
const unt trials = 1000000;
unt arr[length];
unt i;
unt count = 0;
for (i = 0; i < length; i++)
arr[i] = i;
for (i = 0; i < trials; i++) {
shuffle(arr);
count += sortlen(arr);
}
printf("avg sort len %f\n", (double)count / trials);
} And the results:
carbolite:/tmp> ./sort
avg sort len 1.718539
carbolite:/tmp> ./sort
avg sort len 1.717483
carbolite:/tmp> ./sort
avg sort len 1.718032I’m not sure if it’s reasonable to expect the inputs to such a function to be uniformly random arrays. Any program which checks if an array is sorted probably deals with sorted arrays more frequently. But at least the math checks out.
