CODEWITHSUNDEEP
javascriptarraysalgorithmsorting
Yeysides
Yeysides

Reputation: 1292

Javascript Double sorting algorithm

I recently went through an interview where they asked me to come up with a sorting algorithm that really thew me off. Does anyone know the solution to this if it were to be done in javascript?

Problem 1: Double Sort

Please write a method which accepts an array of strings. Each element can either be a number ("165") or a word ("dog"). Your method should sort and print the array such that (1) The words are printed in alphabetical order and the numbers in numerical order, and (2) the order of words and numbers within the array is the same.

Examples (input => output):

sort(['5', '4', 'dog', '1', 'cat'])
=> ['1', '4', 'cat', '5', 'dog']

sort(['dog', 'cat'])
=> ['cat', 'dog']

sort('5', '3')
=> ['3', '5']

You can use standard library sort functions, and should assume that all inputs will be valid. If you make any other assumptions, please document those as well. You can use any programming language that you'd like.

Additionally, you may assume that you'll be given a utility method that returns whether a given String is a valid number (e.g. isNumber(), where isNumber('dog') returns false, and isNumber('15') returns true).

Upvotes: 1

Views: 1238

Answers (3)

גלעד ברקן
גלעד ברקן

Reputation: 23945

Here's a clumsy variation on quicksort that will sort either the numbers or the words in situ. (I modified a regular JavaScript quicksort posted by Paul Lewis; not sure if all the kinks are completely ironed out...).

function isNumber(x,y) {
  return y ? Number(x).toString() !== x : Number(x).toString() === x;
}

function less(a,b,y){
  return y ? a < b : Number(a) < Number(b)
}

function swap(a, i, j) { var t = a[i]; a[i] = a[j]; a[j] = t; }

function partition(array, pivot, left, right, what) {
  var store = left,
      pivotValue = array[pivot];

  swap(array, pivot, right);

  for (var v = left; v < right; v++) {
    if (less(array[v],pivotValue,what) && isNumber(array[v],what)) {
      swap(array, v, store);
      store++;
    }
  }

  while(!isNumber(array[store],what))
    store++;

  swap(array, right, store);

  return store;
}

function doubleQSort(array, left, right, what) {
  while(!isNumber(array[right],what) && right > left)
    right--;
  while(!isNumber(array[left],what) && left < right)
    left++;

  var pivot = null;

  if (left < right) {
    pivot = (right + left) >> 1;

    while(!isNumber(array[pivot],what))
      pivot--;

    newPivot = partition(array, pivot, left, right, what);

    doubleQSort(array, left, newPivot - 1,what);
    doubleQSort(array, newPivot + 1, right,what);
  }
}

Output:

var things = ['dog', 'asdf','31','11','6','fat','cat', '4'];

doubleQSort(things,0,things.length - 1,'words');
doubleQSort(things,0,things.length - 1);
console.log(things);

[ "asdf", "cat", "4", "6", "11", "dog", "fat", "31" ]

Upvotes: 1

Farzher
Farzher

Reputation: 14583

Same idea and performance as the other answer. But written in something like coffeescript so it's easier to read

enter image description here

Upvotes: 1

maerics
maerics

Reputation: 156524

Here's a simple approach - filter the input array into separate arrays of only strings and only numbers. Then sort the homogeneously typed arrays per their natural ordering. Then produce a final sorted array populated by the type of the indices in the original array.

For example:

function doubleSort(arr) {
  // Separate the values by type.
  var numbers=[], strings=[];
  arr.forEach(function(x) {
    if (isNumber(x)) {
      numbers.push(Number(x));
    } else {
      strings.push(x);
    }
  });
  // Sort strings and numbers separately.
  strings.sort();
  numbers.sort(function(a, b) { return a - b; });
  // Merge the sorted arrays by type from the input array.
  var sorted=[], nextNumber=0, nextString=0;
  arr.forEach(function(x) {
    if (isNumber(x)) {
      sorted.push(String(numbers[nextNumber++]));
    } else {
      sorted.push(strings[nextString++]);
    }
  });
  return sorted;
}

// XXX: lots of pitfalls but good enough for this exercise.
function isNumber(x) {
  return Number(x).toString() === x;
}

The Big-O performance is bound by the underlying sort algorithm, so likely O(n log n).

Upvotes: 4

Related Questions