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
– ASDFGerte, Commented Nov 6, 2019 at 12:37
@Nina Ah, that would be more obvious with an example that wouldn't end up sorted numerically… — deceze
– deceze ♦, Commented Nov 6, 2019 at 12:38

Nina Scholz · Accepted Answer · 2019-11-06 12:52:43Z

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 6, 2019 at 12:52

answered Nov 6, 2019 at 12:40

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Isaac Over a year ago

this solution is still consider O(n^2) right? With a for and a sort

Nina Scholz Over a year ago

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.

Isaac Over a year ago

Can you please explain a little bit on why is it a log n for sort?

Isaac Over a year ago

According to 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)

Nina Scholz Over a year ago

right, but the target is to get a better O. mabe you have a look here: en.wikipedia.org/wiki/Sorting_algorithm

Abito Prakash · Accepted Answer · 2019-11-06 12:42:21Z

0

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

answered Nov 6, 2019 at 12:42

Abito Prakash

4,8002 gold badges16 silver badges28 bronze badges

Comments

Aditya · Accepted Answer · 2019-11-06 12:47:47Z

0

Try something like

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

answered Nov 6, 2019 at 12:47

Aditya

8016 silver badges11 bronze badges

Comments

tevemadar · Accepted Answer · 2019-11-06 14:07:45Z

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;

Collectives™ on Stack Overflow

How to sort an array efficiently

4 Answers 4

5 Comments

Comments

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

5 Comments

Comments

Comments

Comments

Linked

Related