A New Sorting Algorithm

By Posted on

Problem

I have designed an Algorithm for sorting numbers.
This algorithm works by sorting an array of any length with random, non-repeating whole numbers in a linear manner by ascending order.

Under the inspiration of Binary Search Algorithm, although inefficient the algorithm is able to sort the given array correctly. What is missing here is that the algorithm isn’t fast enough tho I modified it to bring the sence of being involved with the software.

Why All This…
Soon after knowing how to code in JavaScript I wanted to make a little awesome project with my programming skills.

I wanted to show it to the world and to other smart programmers out there but I never knew how…
So I stumbled upon here…

My hopes are that anyone will show some love and review it on their free time and give out their opinions about it on how to improve it and make it faster if possible.

The HTML page for it is

<!DOCTYPE html>
<html>
  <head>
    <title>P-sort Algo</title>
  </head>
  <body>
    <h1>Move To The Console</h1>
    <script type="text/javascript" src="Jsp-sort Algo.js"></script>
  </body>
</html>

And the Algo.js file for the JavaScript codes is

  ////////////////////////////// The Algorithim /////////////////////////////////

      

      //Variables...
      var oldNumb;
      var newNumb;
      
      var firstNo;
      var lastNo;
      
      var low;
      var high;
      var mean;
      
      var attachment;
      var phase1;
      var random;
      
      var counter;
      var pointer;
      
      var n;
      var z;
      
      ///// The Intro Of The User To The Program..... ///////////
      console.log("Hello There..... ");
      console.log('Welcome To "P-Sort Algorithim" Software!');
      console.log("Lets Get Started....");
      console.log("Please Generate Random Numbers By The Function rand(x , y)");
      console.log(
        'Where "x" is The Approximate Number Of Elements You Want To Generate &'
      );
      console.log('      "y" is The Range Of Your Numbers From 1!');
      console.log(
        'NOTE: For Better Review Of The Algorithim, It Is Recommended "y" > "x"'
      );
      
      /////// Random Number Generation...
      function rand(x, y) {
        oldNumb = [];
        newNumb = [];
        console.log("........... Working On It! ...........");
        console.log("This Might Take A While!!!");
        console.log("                             ");
        for (let i = 0; i < x; i++) {
          random = Math.floor(Math.random() * y + 1);
          if (!oldNumb.includes(random)) {
            oldNumb.push(random);
          }
        }
      
        counter = oldNumb.length - 1;
        z = oldNumb.length - 1;
      
        console.log("Completed!!!!");
      
        /////////////// Thus... Given Random Numbers Are........
        console.log("Random Batch");
        console.log(oldNumb);
        console.log(newNumb);
        console.log(
          "................................................................................."
        );
        console.log(
          "Good! Now You Can Sort That Array Of Numbers By A Function pSort()"
        );
        return "___________________________________________________________________________________";
      }
      
      ///////////////// The Algo.... /////////////////////////////
      function reco() {
        if (attachment < newNumb[mean]) {
          high = mean;
          mean = Math.round((low + mean) / 2);
        } else if (attachment > newNumb[mean]) {
          low = mean;
          mean = Math.round((mean + high) / 2);
        }
      
        if (low + 1 == high) {
          phase1 = newNumb.splice(high, newNumb.length);
          newNumb.push(attachment);
          newNumb = newNumb.concat(phase1);
          phase1 = [];
          oldNumb.pop();
          return -1;
        } else if (low + 1 != high) {
          reco();
        }
        return -1;
      }
      
      function universal() {
        pointer = Math.floor(z / 10);
        n = 1;
      
        console.log(
          ".......... Process='sorting-data'; Type='numbers'; Quantity ='" +
            (z + 1) +
            "'; Phase: " +
            n +
            "/10 .........."
        );
        console.log("                           ");
        n = n + 1;
      
        for (let i = 0; i < z + 1; i++) {
          counter = 0;
          firstNo = newNumb[counter];
          lastNo = newNumb[newNumb.length - 1];
          attachment = oldNumb[oldNumb.length - 1];
      
          if (attachment < firstNo) {
            newNumb.unshift(attachment);
            oldNumb.pop();
          } else if (attachment > lastNo) {
            newNumb.push(attachment);
            oldNumb.pop();
          } else if (attachment > firstNo && attachment < lastNo) {
            //Binary Search....
            low = 0;
            high = newNumb.length - 1;
            mean = Math.round((low + high) / 2);
            reco();
          }
      
          if (i == n * pointer) {
            console.log(
              ".......... Process='sorting-data'; Type='numbers'; Quantity='" +
                (z + 1) +
                "'; Phase: " +
                n +
                "/10 .........."
            );
            console.log("                           ");
            n = n + 1;
          }
        }
        console.log(
          "...................................................................................................."
        );
        console.log("Final Batch");
        console.log(newNumb);
        console.log(oldNumb);
      
        return -1;
      }
      
      function pSort() {
        /////////////////// Starter //////////////////
        firstNo = oldNumb[counter];
        lastNo = oldNumb[(counter = counter - 1)];
      
        if (firstNo > lastNo) {
          newNumb.unshift(lastNo);
          newNumb.push(firstNo);
        } else if (firstNo < lastNo) {
          newNumb.unshift(firstNo);
          newNumb.push(lastNo);
        }
      
        oldNumb.pop();
        oldNumb.pop();
      
        universal();
        console.log('Done');
        console.log('.......................................................................');
        console.log("           ")
        console.log('P-Sort Algorithim');
        return "_________________________________________________________________________________________";
      }

Solution

  1. Line length: you want to avoid long lines of code when you can. With some lines this is unavoidable, but you shouldn’t have a long line just because you wanted to print a spacer to the console.
  2. You should prefer const when you can, and let when you can’t. I don’t think there are cases where you’d need to use var.
  3. Functions should do something or print something, but not both. (The idea is that you should be able to add the js file to a website and then just call the sort function without worrying about it printing stuff to the console.) There’s no reason to return "-------";
  4. reco and universal are bad function names. They should better describe what they’re doing. rand should probably be randInts. But it’s not really the point of the algorithm, so I’m going to just hard code that part and not worry about it. reco is a binary search and insertion, so I’ll name it binaryInsertion.
  5. Instead of console.log the instructions, you should put them in the comments.
  6. phase1 = []; is never used again and should be deleted.
  7. Your variable naming needs a little work. You should be able to look at a variable and know what it does. I’m going to do the following:
  • x -> size
  • y -> range
  • oldNumb -> oldNumbers
  • newNumb -> newNumbers
  • attachment -> newNumber
  • phase1 -> tail
  1. Avoid global variables as much as possible (“possible” should be “entirely” for a library function like sorting). The easiest of those to fix is if you are always assigning to it before using it, like firstno, lastno, phase1, pointer, random. binaryInsertion (aka reco) can pass itself the arguments it needs.
  2. oldNumb[(counter = counter - 1)] is asking for trouble. Don’t assign within an expression. But you always know what counter is, so just use that value instead of saving it to a variable.
  3. It seems like n and pointer are only there to help with logging how far you’ve progressed through the algorithm (and if z%10 is large, then you get interesting output like being in “Phase 15/10”). Let’s take out this logging. If we need to figure out what’s happening, developer tools like breakpoints can work almost as well, and that won’t print stuff to the console when we’re not debugging.
  4. You should return something useful, or not return at all. ------ was bad. -1 is also bad (unless it means something).
  5. You have a couple of if ( condition ) { ... } else if ( ! condition ) { ... }, leaving me wondering if the else if might not happen, and what that function would do in that case. Since you know it’s going to be one or the other, just have if ( condition ) { ... } else { ... }.
  6. The second argument to array.splice defaults to the rest of the elements. Let’s make use of that.
  7. binaryInsertion and univesal have 3 oldNumbers.pop();, but exactly one will happen. Let’s move them to the end of universal‘s for loop.
  8. If you have a base case initialization and then a loop or recursion, try to make the initialization as simple as possible by moving things into the loop or recusion. In this case, pSort only needs to put a single element into newNumbers, not two, before handing things off to universal.
  9. z is set to oldNumbers.length - 1 and then never changed again. And it’s only use is < z+1 in a for loop. Let’s get rid of z.
  10. someArray.pop() returns the value that was popped. We can use that instead of someArray[ someArray.length-1 ] and popping later. But if we iterate through oldNumbers instead of popping, then we don’t destroy the old array. That seems worthwhile.
  11. pSort is now short enough that we can move it into universal, and rename that to pSort.

The code so far:

let oldNumbers = [],
    newNumbers = [];
let low, high, mean, newNumber;

const size = 20,
    range = 100;

for ( let i = 0 ; i < size ; i++ ) {
    const random = Math.floor(Math.random() * range + 1);
    if ( !oldNumbers.includes(random) ) {
        oldNumbers.push(random);
    }
}
console.log(oldNumbers);
     
function binaryInsertion() {
    if ( newNumber < newNumbers[mean] ) {
        high = mean;
        mean = Math.round((low + mean) / 2);
    } else if ( newNumbers[mean] < newNumber ) {
        low = mean;
        mean = Math.round((mean + high) / 2);
    }
    if (low + 1 == high) {
        const tail = newNumbers.splice(high);
        newNumbers.push(newNumber);
        newNumbers = newNumbers.concat(tail);
    } else {
        binaryInsertion();
    }
}
     
function pSort() {
    const firstNo = oldNumbers.pop();
    newNumbers = [firstNo];
    for ( let i = 0 ; i < oldNumbers.length ; i++ ) {
        const firstNo = newNumbers[0];
        const lastNo = newNumbers[newNumbers.length - 1];
        newNumber = oldNumbers[i];
     
        if ( newNumber < firstNo ) {
            newNumbers.unshift(newNumber);
        } else if ( lastNo < newNumber ) {
            newNumbers.push(newNumber);
        } else {
            //Binary Search....
            low = 0;
            high = newNumbers.length - 1;
            mean = Math.round((low + high) / 2);
            binaryInsertion();
        }
    }
}
     
pSort();
console.log(newNumbers);
  1. We want to eliminate the global variables low, high, mean, and newNumber, which are primarily used by binaryInsertion. The thing to realize is that the function is doing two different things: finding the new location and doing the insertion. If we split finding the index into a separate binarySearch function, we can incorporate the variables as parameters instead of global variables.
  2. The newNumber < firstNo and lastNo < newNumber cases are handled by the general binaryInsertion, so it’s questionable whether you should actually separate them out. I’m going to remove them, because it simplifies the code.
  3. At this point, pSort is short enough that we can combine it with binaryInsertion. We can also remove the restriction that the numbers be unique. Finally, we can pass oldNumbers as a parameter to pSort, and have it return newNumbers, removing the last global variables. Here’s the final product:
let oldNumbers = [];

const size = 20,
    range = 100;

for ( let i = 0 ; i < size ; i++ ) {
    const random = Math.floor(Math.random() * range + 1);
    oldNumbers.push(random);
}
console.log(oldNumbers);

function binarySearch(haystack,needle,low,high) {
    if ( haystack.length===0 ) {
        return 0;
    }
    if ( low===undefined || high===undefined ) {
        low = 0;
        high = haystack.length-1;
    }
    if ( high <= low ) {
        if ( needle < haystack[low] ) {
            return low;
        }
        return low+1;
    }
    const mean = Math.floor((low + high) / 2);
    if ( needle < haystack[mean] ) {
        return binarySearch(haystack,needle,low,mean);
    }
    if ( haystack[mean] < needle ) {
        return binarySearch(haystack,needle,mean+1,high);
    }
    // at this point, haystack[mean] === needle
    return mean;
}
     
function pSort(oldNumbers) {
    let newNumbers = [];
    for ( let i = 0 ; i < oldNumbers.length ; i++ ) {
        newNumber = oldNumbers[i];
        const newLocation = binarySearch(newNumbers,newNumber);
        const tail = newNumbers.splice(newLocation,newNumbers.length);
        newNumbers.push(newNumber);
        newNumbers = newNumbers.concat(tail);
    }
    return newNumbers;
}
     
newNumbers = pSort(oldNumbers);
console.log(newNumbers);
  1. We now have a binarySearch function, and a sort function, which are worthwhile additions to any library (our implementation is probably not the best, but that’s another matter). If we’re feeling a bit cocky, we can even add them to the array prototype: Array.prototype.pSort = function() { return pSort(this); }, so that we can write oldNumbers.pSort()
  2. It’s been a long time since my computer science class, but I think this is an insertion sort.

Leave a Reply

Your email address will not be published. Required fields are marked *