Target specific attributes with merge sort

1
votes

Implemented the merge sort algorithm in my javascript code.

I'm wonder how I can target specific attributes like date, title, name etc for sorting in an array when calling merge sort like mergeSort(array);.

function mergeSort(arr){
    var len = arr.length;
    if(len <2)
        return arr;
    var mid = Math.floor(len/2),
        left = arr.slice(0,mid),
        right =arr.slice(mid);

    return merge(mergeSort(left),mergeSort(right));
}

function merge(left, right){
    var result = [],
        lLen = left.length,
        rLen = right.length,
        l = 0,
        r = 0;
    while(l < lLen && r < rLen){
        if(left[l] < right[r]){
            result.push(left[l++]);
        }
        else{
            result.push(right[r++]);
        }
    }  

    return result.concat(left.slice(l)).concat(right.slice(r));
}

Using it in a sort options method. What I want is to print a sorted list. The way the list is sorted will be defined by the users chosen sort option.

function sortConfig(array, sortOption){
 if(sortOption == 'title') mergeSort(array.Title);
 //..etc
}
2
javascriptsortingmergesort
Hummm... What? Show us how you use this function - Alon Eitan
You don't really want to rewrite your mergeSort function each time you specify another attribute to sort by. Rather use a comparison callback equivalent to the native sort function. - le_m
I didn't downvoted, but those are for a reason. We don't know what's sortConfig is, nor array - Don't just show us your function, show us the parameters - What is the expected results vs. the actual, show us how you call those functions - Just add more context - Alon Eitan
@le_m Could you give an example? - Znowman
You could add a functional argument to your merge sort that returns the property you wish to use like (item) => item.title - Icepickle

2 Answers

1
votes

To implement the behavior with an optional argument, you could do it in the following way:

function mergeSort(arr, compare = (item => item))

This would set compare function to be the item itself when running the merge

and then we update the calling of the merge and mergeSort itself, where they now all get the compare argument

return merge(mergeSort(left, compare), mergeSort(right, compare), compare);

and ofcourse the declaration for your merge function itself

function merge(left, right, compare)

Which then calls the compare function upon comparison, like here:

if (compare(left[l]) < compare(right[r]))

This lets you choose wether you wish to give an argument or not wen you call your mergeSort function, like:

console.log(mergeSort(nrs).join(','));
console.log(mergeSort(nrs, n => -n).join(','));

console.log(mergeSort(arr, i => i.id));
console.log(mergeSort(arr, i => i.title));


function mergeSort(arr, compare = (item => item)) {
  var len = arr.length;
  if (len < 2)
    return arr;
  var mid = Math.floor(len / 2),
    left = arr.slice(0, mid),
    right = arr.slice(mid);

  return merge(mergeSort(left, compare), mergeSort(right, compare), compare);
}

function merge(left, right, compare) {
  var result = [],
    lLen = left.length,
    rLen = right.length,
    l = 0,
    r = 0;
  while (l < lLen && r < rLen) {
    if (compare(left[l]) < compare(right[r])) {
      result.push(left[l++]);
    } else {
      result.push(right[r++]);
    }
  }

  return result.concat(left.slice(l)).concat(right.slice(r));
}
var arr = [{
  title: 'test 5',
  id: 4
}, {
  title: 'test',
  id: 0
}, {
  title: 'test 3',
  id: 2
}, {
  title: 'test 4',
  id: 3
}];
var nrs = [5, 3, 7, 156, 15, 6, 17, 9];

// and call like
console.log(mergeSort(nrs).join(','));
console.log(mergeSort(nrs, n => -n).join(','));

// or like
console.log(mergeSort(arr, i => i.id));
console.log(mergeSort(arr, i => i.title));
1
votes

For the sake of brevity, these examples show how to sort an array of objects based on a property with a string value. You would most likely need to create some additional logic to handle different types of properties.

1. Array.sort()

You can do this with the Array.sort() method

Fiddle Example

myThings = [
  { alpha: 'a' },
  { alpha: 'x' },
  { alpha: 'p' },
  { alpha: 'orange' },
  { alpha: 'c' },
  { alpha: 'w' }
];

myThings.sort(function(a, b) {
  var alphaA = a.alpha.toUpperCase();
  var alphaB = b.alpha.toUpperCase();
  if (alphaA < alphaB) return -1;
  if (alphaA > alphaB) return 1;
  return 0;
});

console.log(myThings);

2. Or, compare array item property value instead of array item value

Fiddle Example

function mergeSort(arr, prop) {
    if (arr.length < 2)
        return arr;

    var middle = parseInt(arr.length / 2);
    var left   = arr.slice(0, middle);
    var right  = arr.slice(middle, arr.length);

    return merge(mergeSort(left, prop), mergeSort(right, prop), prop);
}

function merge(left, right, prop) {
    var result = [];

    while (left.length && right.length) {
        if (left[0][prop] <= right[0][prop]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

myThings = [
  { alpha: 'a' },
  { alpha: 'x' },
  { alpha: 'p' },
  { alpha: 'orange' },
  { alpha: 'c' },
  { alpha: 'w' }
];

console.log(mergeSort(myThings, 'alpha'));