Task — Smaller than current

You are given a array of integers, @ints. Write a script to find out how many integers are smaller than each member of @ints, ie foreach ints[i], count ints[j] < ints[i] where i != j.

Examples

Example 1
Input: @ints = (5, 2, 1, 6)
Output: (2, 1, 0, 3)

For $ints[0] = 5, there are two integers (2,1) smaller 
   than 5.
For $ints[1] = 2, there is one integer (1) smaller than 2.
For $ints[2] = 1, there is none integer smaller than 1.
For $ints[3] = 6, there are three integers (5,2,1) 
   smaller than 6.

Example 2
Input: @ints = (1, 2, 0, 3)
Output: (1, 2, 0, 3)

Example 3
Input: @ints = (0, 1)
Output: (0, 1)

Example 4
Input: @ints = (9, 4, 9, 2)
Output: (2, 1, 2, 0)

Analysis

The obvious way to solve this is to have two nested loops, each looping over the entirety of @ints:

for $i (0 .. scalar @ints - 1) {
   $smaller[$i] = 0;
   for $j (0 .. scalar @ints - 1) {
      $smaller[$i] ++ if $ints[$j] < $ints[$i];
   }
}

The condition stated in the task, that $i != $j, does not need to be checked as $ints[$j] < $ints[$j] is obviously never true.

Could this, or should this, be optimised? I tried it with 10 000 random numbers and it completed in a few seconds, so unless there was a known need to handle much larger sets of numbers I would just leave the code unchanged.

However, if we knew that the number of numbers was of the order of the maximum number or less - say 500 numbers in the range 0 to 500 - then it might be worth caching the result so as not to have to execute the inner loop on an $ints[$i] value that had already been seen. Like this:

for $i (0 .. scalar @ints - 1) {
   if (defined $cached[$ints[$i]]) {
      $smaller[$i] = $cached[$ints[$i]];
   } else {
      $smaller[$i] = 0;
      for $j (0 .. scalar @ints - 1) {
         $smaller[$i] ++ if $ints[$j] < $ints[$i];
      }
      $cached[$ints[$i]] = $smaller[$i];
   }
}

I tried that, but it only makes a minimal saving, so I haven't included it in my submitted solution. As Donald Knuth (may have) said: ‘Premature optimisation is the root of all evil’.

Try it 

Try running the script with any input:

Your @ints =

example: 6, 3, 9, 7, 2, 0, 4

⤡

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2024-02-19
use utf8;     # Week 257 - task 1 - Smaller than current
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

smaller_than_current(5, 2, 1, 6);
smaller_than_current(1, 2, 0, 3);
smaller_than_current(158, 183, 309, 369, 314, 461, 235, 
464, 474, 116, 432, 323, 287, 445, 444, 345, 86, 218, 261, 
386, 470, 292, 91, 86, 472, 242, 134, 316, 244, 369, 288, 
207, 237, 406, 449, 377, 464, 346, 175, 302, 464, 27, 276, 
268, 409, 199, 206, 201, 106, 225, 323, 148, 306, 104, 
481, 1, 476, 143, 147, 206, 50, 97, 379, 478, 380, 73, 
321, 122, 290, 489, 120, 351, 175, 318, 448, 357, 44, 46, 
458, 259, 409, 313, 341, 118, 461, 358, 222, 336, 371, 
296, 72, 478, 286, 97, 137, 167, 163, 264, 169, 74, 386, 
82, 70, 478, 447, 6, 235, 451, 84);

sub smaller_than_current {
    
    my (@ints, $i, $j, @smaller);
    
    @ints = @_;
    
    # calculate result for $ints[$j]
    for $i (0 .. scalar @ints - 1) {
        $smaller[$i] = 0;
        
        # count all numbers less than $ints[$j]
        for $j (0 .. scalar @ints - 1) {
            $smaller[$i] ++ if $ints[$j] < $ints[$i];
        }
    }
    say qq[\nInput:  \@ints = (] . join(', ', @ints) . q[)];
    say qq[Output:         (] . join(', ', @smaller) . q[)];
}

Output

Input:  @ints = (5, 2, 1, 6)
Output:         (2, 1, 0, 3)

Input:  @ints = (1, 2, 0, 3)
Output:         (1, 2, 0, 3)

Input:  @ints = (158, 183, 309, 369, 314, 461, 235, 464, 
474, 116, 432, 323, 287, 445, 444, 345, 86, 218, 261, 386, 
470, 292, 91, 86, 472, 242, 134, 316, 244, 369, 288, 207, 
237, 406, 449, 377, 464, 346, 175, 302, 464, 27, 276, 268, 
409, 199, 206, 201, 106, 225, 323, 148, 306, 104, 481, 1, 
476, 143, 147, 206, 50, 97, 379, 478, 380, 73, 321, 122, 
290, 489, 120, 351, 175, 318, 448, 357, 44, 46, 458, 259, 
409, 313, 341, 118, 461, 358, 222, 336, 371, 296, 72, 478, 
286, 97, 137, 167, 163, 264, 169, 74, 386, 82, 70, 478, 
447, 6, 235, 451, 84)
Output:         (28, 34, 61, 76, 63, 95, 43, 97, 102, 19, 
87, 67, 54, 89, 88, 71, 12, 40, 49, 82, 100, 57, 14, 12, 
101, 46, 23, 64, 47, 76, 55, 39, 45, 84, 92, 79, 97, 72, 
32, 59, 97, 2, 52, 51, 85, 35, 37, 36, 18, 42, 67, 27, 60, 
17, 107, 0, 103, 25, 26, 37, 5, 15, 80, 104, 81, 8, 66, 
22, 56, 108, 21, 73, 32, 65, 91, 74, 3, 4, 94, 48, 85, 62, 
70, 20, 95, 75, 41, 69, 78, 58, 7, 104, 53, 15, 24, 30, 
9, 50, 31, 9, 82, 10, 6, 104, 90, 1, 43, 93, 11)