5
\$\begingroup\$

Index & Sorting

Index

• Counting: when the index, or the position, is dependent on the item. Count from one. (Zero-based index is mathematically wrong.)

• Grid: when the index, or the position, is independent on the item. (e.g. JavaScript array)

Counting arrays are used in bubble sort, merge sort, quick sort, etc. Because of the nature of the index, sorting techniques using counting arrays require comparing the items and moving the items around.

Grid arrays are better suited for sorting.

Grid Sort

• Assigning the number (or other value associated with the number, such as name) to the corresponding index’s item

• Filtering out the undefined for print, iterate, length, etc.

• Assigning is sorting

• No comparing. No swapping. No moving around items.

• No need for indexOf()

• Stable

• Limitations : whole numbers only, size of an array

• An example using JavaScript

https://code.sololearn.com/WWuuXR9rO45U/?ref=app


var test = [57, 285, 0, 854, 0, 27, 5, 5, 2885, 497, 57, 16, 803, 653, 62, 905, 975, 367, 147, 99, 58, 207643, 73, 83, 95, 24, 3, 1986, 47, 954, 1, 99, 954, 36, 67, 2, 753, 97, 3689, 79864, 5788, 479, 9865, 8900, 73, 753, 588, 19537, 489964, 30674, 578, 55, 99999, 578, 1000000, 58, 279, 3, 75, 975, 46, 785, 6789, 164, 5538, 744, 85, 2, 579, 753, 5538, 975, 158, 689, 379, 965, 57, 803, 84, 653, 85, 73, 864, 8643, 9047, 864, 783, 7, 4, 932, 5, 80, 97, 79, 849, 7, 3, 5, 10, 0];

document.write(test+”<br />”);
document.write(“Count: “+test.length+”<br />”);
document.write(“<br />”);

var test_original = [];
var x = 0;
while (x < test.length){
    if (test_original[test[x]] === undefined){
        test_original[test[x]] = [];
        test_original[test[x]][0] = test[x];
    }
    else{
        test_original[test[x]].push(test[x]);
    }
    x = x + 1;
}

var test_defined = [];
var defined_from = 0;
var defined_to = test_original.length;
var x = defined_from;
while (x < defined_to){
    if (test_original[x] !== undefined){
        test_defined.push(x);
    }
    x = x + 1;
}

var definedIndex = 0;
while (definedIndex < test_defined.length){
    document.write(definedIndex + 1);
    document.write(“. “);
    document.write(test_defined[definedIndex]);
    document.write(“: “);
    document.write(test_original[test_defined[definedIndex]]);
    document.write(“<br />”);

    definedIndex = definedIndex + 1;
}

\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to Code Review! What would this look like in a function? Your naming is a bit odd. First you declare a test variable with test input, then you copy it into a variable called test_original in an odd manner. test_original is not the original data, so where does the name come from? \$\endgroup\$ – Mast Jul 30 at 6:11
  • \$\begingroup\$ I meant to differentiate it from test_defined. Grid Sort is like sorting into mailboxes. \$\endgroup\$ – Julia Kim Jul 30 at 6:18
  • \$\begingroup\$ test_original is the sorted form. test_defined is to print. \$\endgroup\$ – Julia Kim Jul 30 at 6:22
  • 2
    \$\begingroup\$ I'd really like to see this code inside of a function with defined inputs and outputs. E.g.: Input some array, output the sorted array (or alternatively, the indices of how the input is traversed in sorted order). I challenge the statement Grid arrays are better suited for sorting: The algorithm uses additional memory proportional to the input array, since each value is copied to test_original. This can be a show stopper for large inputs. You mention "moving items around" as a problem of common sorting algorithms, however, this can be circumvented by sorting indices instead. \$\endgroup\$ – pschill Jul 30 at 10:28
  • \$\begingroup\$ Instead of copying test to test_original, how about test_original holding the indices of test? \$\endgroup\$ – Julia Kim Jul 31 at 19:24
5
\$\begingroup\$

Zero based indexing

Counting: when the index, or the position, is dependent on the item. Count from one. (Zero-based index is mathematically wrong.)

I will disagree. The index does not represent a count but rather it is a position. When we measure something we start at 0. For example a length of 5 units. Unit 0 the 1st unit is at 0 to < 1, and the last unit, the 5th is at 4 to < 5. The set of 5 units does not contain the unit 5.

It is not mathematically wrong to use zero based indexing, what is wrong is using the index to represent a count.

Array V Grid AKA hash table

Grid: when the index, or the position, is independent on the item. (e.g. JavaScript array)

I think you understanding of how arrays work is leading to some bad assumptions.

Arrays

Computers use RAM that is a continuous array of addresses. We use arrays because they are very fast when we need to get or set a item at an index.

To locate an item we get the RAM address of the array and add the index multiplied by the size of each item (JS arrays hold references so all array items are the same size) . In one addition and multiplication (a shift if item size is a power of two) we have the memory address of the data we want.

Almost all modern CPUs have special instructions (indexed addressing) to speed up array use.

Hash table

A grid is a little more complicated.

As the index can be any value we can not just offset a RAM address to find an item. We need to know where the item associated with an index is in RAM. That means that another array is needed to hold all the indexes and RAM addresses.

So if you want the item of grid index 10000000, we need the address of the index 10000000 which must be found by searching the array of indexes one at a time. Then we can get the RAM offset of the item we are after.

However computers have been around for a long time and some cleaver people have come up with ways to make "grids" somewhat faster. In javascript we call them Map in computer science we use the term hash table.

Hash tables avoid the need to search for the index by applying a hash function to the index (key). This provides an offset that we can use to get the RAM address of the data we are after.

Still slower than an array as the hash function needs to be applied each time we index into the table, its a lot faster than searching all indexes each time we want an item.

When JS arrays are not arrays.

On a side note. JavaScript arrays come in two flavors

  1. Dense arrays, each item is held one after the other in a continuous section of memory.
  2. Sparse arrays. Sparse arrays look from the code perspective like dense array, but under the hood sparse array are actually hash tables.

A dense array is converted to a sparse array if you add an item above the array length. Different engines have different rules but generally its a bad idea to add items to an array at random indexes (as you do in your grid sort)

Review

I am not going to review your code as I think it is moot if you consider the above information.

I will say, you saw some institutionalized flaws and you created a better solution (sadly your assumptions were off). You demonstrate an initiative and a healthy skepticism of the status quo.

Most people will just keep at the same old same old and nothing great ever comes from that.

Keep at it.

\$\endgroup\$
  • \$\begingroup\$ Counting is done from 1 because 0+0=0, 0-0=0. Python has an error. String method Count() does not count overlapping motifs. One of the simplest way was to check for the motif and delete up to the first character. When adding the indexes to get the original indexes, +1 had to be done because 0+0=0. If arrays, lists, etc. where the index is removed when the item is removed, it is counting. Counting should be done from 1. \$\endgroup\$ – Julia Kim Jul 31 at 20:06
  • \$\begingroup\$ In length, 0 is an imaginary line where the length begins behind. The first piece of the length is 0 <= 1. 0 is not a part of the length. \$\endgroup\$ – Julia Kim Jul 31 at 22:55
  • \$\begingroup\$ @JuliaKim How old do you turn on your first birthday, or how far have you run at the start of a race. The first piece if 0 to < 1 not <= 1. The first is everything before the second and the second starts at 1 \$\endgroup\$ – Blindman67 Jul 31 at 23:43
  • \$\begingroup\$ @JuliaKim regarding 1-based collections, I can tell you from experience with Lua that they are great for some things and not so great for others. You'll almost never have to worry about fencepost errors with them or things like that, but they're more awkward for things like representing a 1D array as a 2D grid, or things involving modulo operator, where you always end up subtracting 1. There are pros and cons for each; some languages even have facilities for dealing with both (Prolog's nth0 and nth1). \$\endgroup\$ – user11536834 Aug 2 at 3:57
  • \$\begingroup\$ I used both counting type and grid type. What I call counting and grid types are based on the relationship between index and item. If the index is removed when the item is removed, the index is dependent on the item. It is counting. If the index is not removed when the item is removed, the index is independent of the item. It is a grid. Both are needed for different uses. \$\endgroup\$ – Julia Kim Aug 4 at 17:29
1
\$\begingroup\$

There's another answer here with a great assessment of your solution. The upshot of that answer (and this one) is that you'd be better off doing a test.sort() and calling it a day.

Even though you should probably consider scrapping this solution, as explained in the other answer, a few things here may be worth commenting on anyway.

Overall, the style of your code looks about right for JavaScript written 5 to 10 years ago, but feels a bit archaic by modern standards.

Let's look at the last bit first:

var test_defined = [];
var defined_from = 0;
var defined_to = test_original.length;
var x = defined_from;
while (x < defined_to){
    if (test_original[x] !== undefined){
        test_defined.push(x);
    }
    x = x + 1;
}

Unless you want to target ancient browsers, you should get rid of function-scoped var and go for block-scoped let or const instead. Most languages use block scoping, and the function-scoped var has been an infamous source of confusion and bizarre workarounds in JavaScript.

Also, there are lots of useful tools in the Array toolbox these days, and there's usually something suitable for small jobs like this. But let's back up for a second: there's an issue here; this code leaves our sorted array in a weird state, with nested elements. I'd expect a gridSort function to do something similar to Array.prototype.sort, returning an array of the same length, and with the same elements (in a different order). In other words, the resulting array should be flattened -- and there is an array method called flat to do just that. Incidentally, it will also condense the array.

So that entire block of code could be replaced with this:

let test_defined = test_original.flat()

Now for the first bit of code:

var test_original = [];
var x = 0;
while (x < test.length){
    if (test_original[test[x]] === undefined){
        test_original[test[x]] = [];
        test_original[test[x]][0] = test[x];
    }
    else{
        test_original[test[x]].push(test[x]);
    }
    x = x + 1;
}

This looks to me like a job for reduce. You could replace these 12 lines of code with 2:

var test_original = test.reduce((a, v) =>
    (a[v] ? a[v].push(v) : a[v] = [v], a), [])

Someone might argue that this looks like a subversion of reduce, or an abuse of obscure language features, or that it's less readable -- and they might be right. But, you could use forEach instead, if you're not worried about impure callbacks, or give your variables more descriptive names, or scribble a few mustaches on it, or anything else that floats your boat. This is just an example.

That could leave our final gridSort function looking something like this:

const gridSort = a =>
    a.reduce((a, v) => (a[v] ? a[v].push(v) : a[v] = [v], a), []).flat()

Not the most readable thing in the world, to be sure... but even so, I'd bet most people would grok these 2 lines more quickly than the original 20+ lines (and this leaves you ~20 new lines to comment in excruciating detail before it adds any extra bloat to your source file).

All that said, the most useful tool in the Array toolbox for this situation is Array.prototype.sort, and you should probably just use that instead.

\$\endgroup\$
1
\$\begingroup\$

First off, what @Blindman67 said.

However, if you were to use this approach in production code, there are a few things to consider:

  • You probably want to create a class/function with a functions like add
  • I see a few issues with your add code:

    if (test_original[test[x]] === undefined){
      test_original[test[x]] = [];
      test_original[test[x]][0] = test[x];
    }
    else{
      test_original[test[x]].push(test[x]);
    }
    
    • Accessing test[x] is slower than assigning it to a temp variable, and use that temp variable
    • Even accessing several times test_original[test[x] is slow, you should reduce that to a maximum as well
    • You can assign an array with 1 element like this:

      test_original[test[x]] = [test[x]];
      
  • JavaScript is all about lowerCamelCase, so test_original should be testOriginal, and really I think <adjective><noun> is better than <noun><adjective>, so originalTest would be even better
  • The Spartan naming convention has a place in JavaScript, but I would have gone with i(nteger) over x
  • Your looping over arrays is not idiomatic, I would go for for(;;) loops or use the forEach method

Also, just a thought, but in your output you have

  1. 73: 73,73,73
  2. 75: 75
  3. 79: 79
  4. 80: 80

You could just store the counts in the array, instead of arrays

test_original[73] would then contain 3 instead of [73,73,73] which saves space and is faster

\$\endgroup\$
  • \$\begingroup\$ For the statement: "JavaScript is all about lowerCamelCase" should we call that idiomatic Javascript? And for the statement "The Spartan naming convention has a in JavaScript," should there be a word or something else between a and in? \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Aug 1 at 16:01
  • \$\begingroup\$ Re: word missing: yep, fixed. Re: lowerCamelCase, no, JavaScript is lowerCamelCase, period. \$\endgroup\$ – konijn Aug 1 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.