2
\$\begingroup\$

Here is a vanilla JS module that I wrote for sorting and searching an array.

I would appreciate feedback on the design of the module as I'm new to writing javascript in modules and don't know if I'm missing the point.

"use strict";

/**
* Find is an outer function
* @param  {int}    needle      Value received from the user
* @param  {array}  haystack    An array returned by the user up to 100
* @return {obj}                returns an object that contains the sort and search functions
*/

function find(needle, haystack) {

//keeps track of the array length
var haystackLength = haystack.length;

 //Sort the array using Counting Sort O(n), so we can search the array faster
 function sort() {

 //INIt sorted array
 var sorted = [];

 //Create a counting array filled with zeros
 var maxLength = 1000;
 var countArray = (function buildCountArray(length) {
   var array = [];
   for( let i = 0; i < length; i++  ) {
     array[i] = 0;
   }
   return array;
 })(maxLength);

 //run through the haystack and add a count to the corresponding index in the couting array
 for( let i = 0, n = haystackLength; i < n; i++ ) {
   countArray[ haystack[i] ]++;
 }

 //At each index in the counting array add the summation of previous indexes
 for( let i = 0, n = countArray.length; i < n; i++ ) {
   countArray[ i + 1 ] =  countArray[i] + countArray[ i + 1 ];
 }

 //run through the haystack and match it up with the counting array and store it in the sorted array
 for( let i = 0, n = haystackLength; i < n; i++ ) {
   sorted[countArray[haystack[i]] - 1] = haystack[i];
   countArray[haystack[i]]--;
 }

 //sucess
 haystack = sorted;
 console.log("Here is your awesome sorted array:\n" + haystack);
 }

 //Uses Binary Search O(log n), to find the needle in the haystack
 function search() {

 //Track the index of the start of the haystack and the end of the haystack
 var left = 0;
 var right = haystackLength - 1;

 //A recursive IIFE that uses the left and right to determine the middle and then cuts the array
 //in half depending on where the needle lies compared to the middle
 return ( function binarySearch( left, right ) {

   //Once we search the haystack and we can't find the needle
   if( right < left) {
     console.log("Nope, Go fish!");
     return false;
 }

   //track the middle of the haystack
   var mid = Math.trunc( left + ( right - left ) / 2 );
   console.log("Chopping your array in half, chop....chop..:\n" + haystack[mid]);

   //Compare the middle of the haystack to the needle
   //Then move the start or end of the haystack to depend on the needle value
   if( needle === haystack[mid] ) {

     console.log("We found it!");
     return true;

   } else if ( needle < haystack[mid] ) {
     right = mid - 1;
   } else {
     left = mid + 1;
   }

   return binarySearch( left, right );

 })(left, right);

 }

 //Functions that will be available to use
 var publicAPI = {
   sort: sort,
 search: search
 }

 return publicAPI;
 }
\$\endgroup\$
  • \$\begingroup\$ I find the code to be overly complex and the style is an eye sore. The code is also not general enough. \$\endgroup\$ – Rafael Mar 4 '17 at 17:56
  • \$\begingroup\$ I feel the same. Any recommendations on how you would break it up or design it? \$\endgroup\$ – Joseph Palomino Mar 4 '17 at 18:00
1
\$\begingroup\$

arrays in js already have a sort method, all it needs is a compare function. I made a similar api for a general binary search. It takes an array as its first arg and the compare func as the second. The binary search function could be bound to the Array prototype too. But people complain too much about extending the native prototypes, so we'll just pass the array in.

The style here is consistent. The indentation is the same and the variable names are short yet descriptive enough. Each function does 1 thing and nothing more.

var FIND = 100;
var arr = [ 9, 8, 10, 100, 60, 1 ];

var sorted = arr.sort((a, b) => a - b);
console.log(sorted);

var i = binary_search(sorted, n => FIND - n);
console.log('FOUND AT', i);

//https://github.com/MrOutput/learning/blob/master/js/binary_search.js
function binary_search(array, fn) {
    var low, mid, high;
    low ^= low;
    high = array.length - 1;
    while (low <= high) {
        mid = (low + high) >> 1;
        var cmp = fn(array[mid]);
        if (cmp < 0) {
            high = mid - 1;
        } else if (cmp > 0) {
            low = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

Binding it to the array prototype has its benefits though. Consider....

//https://github.com/MrOutput/learning/blob/master/js/binary_search.js
Array.prototype.bsearch = function (fn) {
    var low, mid, high;
    low ^= low;
    high = this.length - 1;
    while (low <= high) {
        mid = (low + high) >> 1;
        var cmp = fn(this[mid]);
        if (cmp < 0) {
            high = mid - 1;
        } else if (cmp > 0) {
            low = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
};

var FIND = 100;
var arr = [ 9, 8, 10, 100, 60, 1 ];
var i = arr .sort((a, b) => a - b).bsearch(n => FIND - n);

console.log('FOUND AT', i);
\$\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.