CODEWITHSUNDEEP
javascriptsortingmergesort
Znowman
Znowman

Reputation: 395

Target specific attributes with merge sort

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
}

Upvotes: 1

Views: 243

Answers (2)

Icepickle
Icepickle

Reputation: 12806

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

Upvotes: 1

Jbird
Jbird

Reputation: 2886

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'));

Upvotes: 1

Related Questions