0
$\begingroup$

I just came up with a simple sorting algorithm that is faster than ShellSort when the range of values is smaller than the number of elements. Is this new? And if so, what should I do with it?

https://github.com/Frazer/hashSort

let hashSortNonUnique = (unsortedArray)=>{
  let myHash = {}
  let min = Infinity;
  let max = -Infinity;

  unsortedArray.forEach(val=>{
    myHash[val]=myHash[val]?myHash[val]+1:1;
    if(val>max) max = val;
    if(val<min) min = val;
  });

  let count = 0;

  for (let sorter = min; sorter <= max; sorter++) {
    let num = myHash[sorter];
    while(num--){
      unsortedArray[count]=sorter;
      count++;
    }
  }
  return unsortedArray;
}

let hashSortObjectsWithNonUniqueVals = (unsortedArray,valFunction)=>{
  let myHash = {}
  let min = Infinity;
  let max = -Infinity;

  unsortedArray.forEach(val=>{
    v= valFunction(val);
    myHash[v]=myHash[v]?myHash[v].push(val):[val];
    if(v>max) max = v;
    if(v<min) min = v;
  });

  let count = 0;

  for (let sorter = min; sorter <= max; sorter++) {
    let vals = myHash[sorter];
    for (let index = 0; index < vals.length; index++) {
      unsortedArray[count]= vals[index];
      count++;      
    }
  }
  return unsortedArray;
}
$\endgroup$
  • 4
    $\begingroup$ This is not a site for programming questions, so we'd prefer it if you give a high-level description of your algorithm instead of an implementation. This also makes it easier to see if you algorithm is a (variant of) another sorting algorithm. $\endgroup$ – Discrete lizard May 3 at 5:08
3
$\begingroup$

The first is a counting sort with the change that you use a hashtable instead of an array to hold the mapping between element value and the number of elements of that value.

The second is a near textbook Bucket Sort with the change that you don't sort the bucket.

$\endgroup$
2
$\begingroup$

This algorithm is known, however it is not used widely. Essentially this algorithm is
O(max - min + n), which as you state if max-min is approximately n then this algorithm runs in O(2n + e) where e is the small cost of making a hash table, which while read/writes are essentially O(1) they are not always.

But as you can guess the reason this is not used except in special cases is because for most of your data you will have ranges that exceed n lg(n) in which case, quickSort/heapSort/mergeSort/binaryInsertionSort would all out perform it.

Note that even if all but 1 of your elements are in the range [1, n] but you have a single value of n^4 then this algorithm becomes O(n^4). So while highly efficient for closely packed values it is not useful for general purpose where we expect to see large ranges within the list.

For those who dont want to read the code:

function hash_sort( S )

    create a hash table H
    place the counts of elements of S into H

    min := smallest element of S
    max := largest element of S

    T := array
    for each number from min to max
        if number is in H
           place number into T based on H[number]

$\endgroup$

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.