flak rss random

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.718032

I’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.

Posted 30 Oct 2016 23:34 by tedu Updated: 30 Oct 2016 23:34
Tagged: math programming