loading...

Using Array prototypes in strange ways #1

bugmagnet profile image Bruce Axtens Updated on ・2 min read

Greg Bulmash wrote a posting recently entitled JavaScript Bubble Sort in the fewest lines. This got me thinking about ways to get around .forEach()'s insistence on iterating over every item. I still haven't found a solution, but I did discover an interesting way to sort an array using .reduce()!

The code here is V8 JavaScript but with some infrastructure provided by C# using my Lychen project.

First step is to pull from the command-line the length of the test array, defaulting to 10.

const aLen = CSSettings.ContainsKey("/LENGTH") ? parseInt(CSSettings("/LENGTH"), 10) : 10;

We then initialise the array: allocate space, fill with zero, then map some random numbers in.

const array = Array(aLen).fill(0).map(function (item, index) {
  return Math.floor(Math.random() * (index * aLen))
});

Next, the main block of code:

First of all check the accumulator (acc) to see how many items it has. If zero, then push the current value (cur) in.

If one, then compare the value in acc with cur and if cur is less that or equal to, unshift it into acc. Otherwise push it.

if acc is longer than one, check to see if cur is less than or equal to the first item in acc, in which case unshift into acc, or if greater than the last item in acc, push it into acc.

If the value is neither pushed nor unshifted, then iterate backwards through acc until cur is greater than the acc value. Add one to the offset and splice cur into acc at that point.

const sorted = array.reduce(function (acc, cur, idx, src) {
    if (acc.length === 0) {
      acc.push(cur);
    } else {
      if (acc.length === 1) {
        if (cur <= acc[0]) {
          acc.unshift(cur)
        } else {
          acc.push(cur);
        }
      } else {
        if (cur <= acc[0]) {
          acc.unshift(cur);
        } else {
          if (cur > acc[acc.length - 1]) {
            acc.push(cur);
          } else {
            for (let i = acc.length - 2; i >= 0; i--) {
              if (cur > acc[i]) {
                acc.splice(i + 1, 0, cur);
                break;
              }
            }
          }
        }
      }
    }
    return acc;
  },
    []);

Finally, display the results.

CS.System.Console.WriteLine(JSON.stringify(array));
CS.System.Console.WriteLine(JSON.stringify(sorted));

This is not a replacement for .sort(). I haven't done any timings but I'm not expecting it to win any prizes for speed. It's just ... well ... interesting.

Posted on by:

bugmagnet profile

Bruce Axtens

@bugmagnet

Programmed Canon Canola calculators in 1977. Assorted platforms and languages ever since. Assisting with HOPL.info. I am NOT looking for work -- I've got more than enough to do.

Discussion

markdown guide