Count fragments or sequence of contiguous numbers in an array

Question

Say you have an array of integers, eg: [0,1,2, 5,6,7, 9,10,11]. In an ideal world they would be sorted, but if the algorithm can work with unsorted, even better.

I need to know how many "fragments" are in this group. Imagine the array makes up an array of bytes of a file; how fragmented is this file?

In the above example, I count 3 groups/fragments.

My goal is to add up the total number of "files" on a disk, then the total number of "fragments" and then calculate the fragmentation (1 - (files / fragments), I think. 10 files, 10 fragments = 0% fragmentation - however if each file is broken into two making 20 fragments, that would bd 50% fragmentation).

So the algorithm I am looking for needs to look at an array of ints and work out how many continuous groups of numbers there are.

Any ideas?

Answer 1

I have come up with this algorithm (ObjectiveC)...

-(NSInteger) numberOfFragments {
    NSInteger fragments = 1;

    NSArray *sortedBytes = [_bytes sortedArrayUsingComparator:^NSComparisonResult(GameFileByte *a, GameFileByte *b) {
        return ([a bytePosition] < [b bytePosition]) ? NSOrderedAscending : ([a bytePosition] > [b bytePosition]) ? NSOrderedDescending : NSOrderedSame;
    }];


    NSInteger lastBytePosition = -1;
    for (GameFileByte *byte in sortedBytes) {
        if (lastBytePosition > 0 && ((byte.bytePosition - lastBytePosition) > 1)) {
            fragments++;
        }
        lastBytePosition = byte.bytePosition;
    }


    return fragments;
}

This seems to work for me... It ensures the bytes are in the right order and then cycles through them, increasing a counter every time the current byte is more than 1 away from its predecessor.