Raindrop Sort

raindrop.txt

The algorithm has O(n*maximum_time) time complexity and O(n) space complexity and is a viable choice when Counting Sort's space complexity is a big issue and the numbers that will be sorted has many duplications and the maximum number isn't really far from the lowest(e.g. 1,1,1,2,2,2,2,3,3,4,5).

It works just like rain. The first raindrop that is more close to the ground(have less height) is the first to hit the ground and so on.

It works only with positive numbers but its possible to do it for negative, just use your head(big O complexity _is_ the same in this case).

It works for floating point and that's the reason why highestCommonFactor is used.

Pseudo-code(or pseudo-c++-code lol):

function raindropSort ( raindrops[] ) { //the raindrops is an unsorted array.

    raindrop_amount = raindrops[].size;
    minimum_velocity = highestCommonFactor(raindrops[]);
    maximum_height = maximumNumber(raindrops[]);
    maximum_time = height/maximum_velocity;

    //rain algorithm
    time = 0;
    while( time != maximum_time ) {
        for ( i=0 to raindrop_amount)  {
            raindrops[i]-=minimum_velocity; // on every second that passes the rain has less height.
            if( raindrop[i] == 0 ){
                sorted_array.push(raindrop[i]) // you can also print it as its already sorted.
                erase(raindrop[i]) // use linked lists as you can also decrease the raindrop_amount and loose less time as the raindrop is already on the ground!
                raindrop_amount--; // decreasing the amount as raindrop[i] is erased.
            }
        }
        time+=minimum_velocity;
    }
    return sorted_array;
}