I created a sorting algorithm, called Grid Sort

Question

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; } 

Answer 1

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.

Answer 2

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.

Answer 3

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

20. 73: 73,73,73
21. 75: 75
22. 79: 79
23. 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