How to sort an array efficiently

Question

I'm trying to sort an array [3,3,2,1,3,2,2,2,1] to [1,1,3,3,3,2,2,2,2].

I'm trying to handle it using object, using the number as key, and the occurrence as value.

const sortNums = (arr) => {
  const result = {}

  for (let i = 0; i < arr.length; i++) {
    const num = result[arr[i]] || 0;
    result[arr[i]] = num + 1;
  }
  //The above will gives me { '1': 2, '2': 4, '3': 3 }

  //How to convert back to array?
}

console.log(sortNums([3,3,2,1,3,2,2,2,1]))

Of course I can use the Object.entries to map back to an array, but then the entire algorithm will be consider O(n^2) right? I'm trying to explore if it can be achieve in O(n) instead. Or I shouldn't use object to begin with?

@deceze he is doing a limited integer sort in O(n), similar to radix sort, he's doing the count sort thingy. — ASDFGerte, Nov 06 '19 at 12:37
@Nina Ah, that would be more obvious with an example that wouldn't end up sorted numerically… — deceze, Nov 06 '19 at 12:38
related: https://stackoverflow.com/questions/2352313/is-there-an-on-integer-sorting-algorithm in case people are still confused. — ASDFGerte, Nov 06 '19 at 12:39
I don't think he wants to sort by occurrence, but actually numerically - can OP maybe clarify? — ASDFGerte, Nov 06 '19 at 12:43
maybe Timsort? search on google for some implementations examples. — danielpopa, Nov 06 '19 at 12:50
Then, lets make things slightly interesting: as the spec guarantees ascending order for integer index properties, for certain methods, how can you know, that using an object, and certain methods for accessing its properties, won't internally use an O(n*log(n)) sort, where n is the amount of different integers in the array, worst case, length of the array? :) — ASDFGerte, Nov 06 '19 at 13:10

Nina Scholz · Accepted Answer · 2019-11-06T12:52:43.143

3

You could get the count for sorting the array.

const sortNums = array => {
    const count = {};
    for (let v of array) count[v] = (count[v] || 0) + 1;
    return array.sort((a, b) => count[a] - count[b] || a - b);
}

console.log(sortNums([3, 3, 2, 1, 3, 2, 1]));

An approach by using the object for sorting.

const sortNums = array => {
    var count = {},
        result = {};
    for (let v of array) (count[v] = count[v] || []).push(v);
    for (let a of Object.values(count)) (result[a.length] = result[a.length] || []).push(a);
    return Object.values(result).flat(Infinity)
}

console.log(sortNums([3, 3, 2, 1, 3, 2, 1]));

edited Nov 06 '19 at 12:52

answered Nov 06 '19 at 12:40

Nina Scholz

376,160
25
347
392

this solution is still consider O(n^2) right? With a `for` and a `sort` – Isaac Nov 06 '19 at 12:43
1

not really, more O(nlogn) ... but for any other solution, you need some sorting, either an array with smaller subset of same values, or directy, as in this answer. – Nina Scholz Nov 06 '19 at 12:44
Can you please explain a little bit on why is it a `log n` for `sort`? – Isaac Nov 06 '19 at 12:53
According to https://blog.shovonhasan.com/time-space-complexity-of-array-sort-in-v8/ , **For arrays containing 10 or fewer elements, time complexity of .sort is O(n^2)** – Isaac Nov 06 '19 at 12:55
right, but the target is to get a better O. mabe you have a look here: https://en.wikipedia.org/wiki/Sorting_algorithm – Nina Scholz Nov 06 '19 at 12:55

score 0 · Answer 2 · answered Nov 06 '19 at 12:42

You can do this

const sortNums = (arr) => {
    const result = {}

    for (let i = 0; i < arr.length; i++) {
      const num = result[arr[i]] || 0;
      result[arr[i]] = num + 1;
    }

    const a = [];
    for(let i = 0; i <= 9; i++) {
        if(result[i]) {
            a.push(...Array.from({length: result[i]}, x => i));
        }
    }
    return a;
  }

score 0 · Answer 3 · answered Nov 06 '19 at 12:47

0

Try something like

var curIndex = 0;
for i in result {
   arr.fill(i, curIndex, curIndex + result[i]);
   curIndex = curIndex + result[i];
}

answered Nov 06 '19 at 12:47

Aditya

771
5
11

score 0 · Answer 4 · answered Nov 06 '19 at 14:07

Assuming that the numbers are small non-negative integers, you can count them as you have done already, and then generate the result on the fly when someone (Array.from() in this example) requests for it, with a simple pair of loops:

function *sortNums(array){
  let stats=[];
  for(var i of array)
    stats[i]=(stats[i]||0)+1;

  for(let i=0;i<stats.length;i++)
    while(stats[i]>0){
      stats[i]--;
      yield i;
    }
}

console.log(Array.from(sortNums([3, 3, 10, 2, 1, 0, 3, 2, 1])).join());

Of course it is possible to just collect the pieces into an array, in the direct, "traditional" way:

let ret=[];
for(let i=0;i<stats.length;i++)
  while(stats[i]>0){
    stats[i]--;
    ret.push(i);//yield i;
  }
return ret;

How to sort an array efficiently

4 Answers4

Linked

Related