Algorithm Writeup #1: Chapter 3 - Push Front


#1

Limitations:

  • No built-in functions except the Array Prototype Function push.

Basic Section:

Exploratory:

This is a built-in Array Prototype Function known as unshift. The idea is that you pass unshift arguments, which get added to the front of the array. When adding, the order that you pass the arguments to unshift are preserved. The unshift function adds the arguments to the array in-place (acting directly upon the Array Object that called the unshift method) and returns the new length of the array.

Built-in example:

var newArr = [2, 4, 6];

newArr.unshift(1);
// newArr is now [1, 2, 4, 6];
console.log(newArr);

newArr.unshift(20, 30);
// newArr is now [20, 30, 1, 2, 4, 6];  Notice how 20 and 30 are added to the array with their order preserved (20 first, 30 second).
console.log(newArr);

var newLength = newArr.unshift(50);
// newArr is now [50, 20, 30, 1, 2, 4, 6]; and newLength is 7
console.log(newArr);
console.log(newLength);

Pseudo-code:

function unshift(arr, element) {
    // Create new space in array. (Note: Since we can only use push, this newly added space will be at the END of the array).
    // Move things one by one to the "right" (by 1 index).
    // Copy the element into the first (0th index) slot.
    // Return the new length of the array after adding our element.
}

Implementation:

function unshift(arr, element) {
    // Create new space in array. (Note: Since we can only use push, this newly added space will be at the END of the array).
    arr.push(null);
    // Note: It doesn't matter what we push really.

    // Move things one by one to the "right" (by 1 index).
    for (var i = arr.length - 1; i >= 0; i--) { // We start the loop at the "right" and move to the "left".
        arr[i] = arr[i - 1]; // Simply move the "left" index (by 1) to the current index's slot.  This is why the built-in method itself is called "unshift".
        // Note: when i = 0, it will attempt to move arr[0 - 1] or arr[-1], into arr[0].  This does not throw an error in JS, and is trivial, because we're going to copy our new element over arr[0] anyway.  Feel free to make the loop stop at 1 (inclusive) if this bothers you.
    }
    
    
    // Copy the element into the first (0th index) slot.
    arr[0] = element;
    // Note: Setting an element completely "removes" whatever it was holding previously, and replaces it with the new value.
    
    // Return the new length of the array after adding our element.
    return arr.length;
}

Manual testing:

var newArr = [2, 4, 6];

function unshift(arr, element) {
    // Create new space in array. (Note: Since we can only use push, this newly added space will be at the END of the array).
    arr.push(null);
    // Note: It doesn't matter what we push really.

    // Move things one by one to the "right" (by 1 index).
    for (var i = arr.length - 1; i >= 0; i--) { // We start the loop at the "right" and move to the "left".
        arr[i] = arr[i - 1]; // Simply move the "left" index (by 1) to the current index's slot.  This is why the built-in method itself is called "unshift".
        // Note: when i = 0, it will attempt to move arr[0 - 1] or arr[-1], into arr[0].  This does not throw an error in JS, and is trivial, because we're going to copy our new element over arr[0] anyway.
    }
    
    // Copy the element into the first (0th index) slot.
    arr[0] = element;
    // Note: Setting an element completely "removes" whatever it was holding previously, and replaces it with the new value.
    
    // Return the new length of the array after adding our element.
    return arr.length;
}

unshift(newArr, 20);
unshift(newArr, 40);
var newLength = unshift(newArr, 60);

console.log(newArr);
// Expected: [60, 40, 20, 2, 4, 6]
console.log(newLength);
// Expected: 6

Intermediate Section:

Now that we have a basic running function, we can extend our function to handle multiple inputs.

Exploratory:

A key component of extending our function to handle multiple inputs, is to learn how to handle a variable amount of inputs. In Javascript, every function has an available local variable called arguments that is an Array consisting of all arguments (hence the name).

Arguments example:

function example() {
    for (var i = 0; i < arguments.length; i++) {
        console.log(arguments[i]);
    }
}

var newArr = [1, 2, 3];

example(newArr, 20, 40, 60);

Pseudo-code:

function unshift() {
    // Pull out our array from arguments.
    // Calculate the number of spaces we need.
    // Add empty spaces at the end of the array, for however many arguments we're adding.
    // Shift each element to the "right" by however many spaces we're adding.
    // Copy all the new elements to the front of the array.
    // Return the new length.
}

Now, as we can see, this is not very different than our basic implementation, with a few caveats.

Implementation:

function unshift() {
    // Pull out our array from arguments.
    var arr = arguments[0];
    // Note: The first argument is our array.

    // Calculate the number of spaces we need.
    var newElesLength = arguments.length - 1; 
    // Note: The length of all our new arguments (the first element is the array, so we subtract 1).

    // Add empty spaces at the end of the array, for however many arguments we're adding.
    for (var i = 0; i < newElesLength; i++) { 
        arr.push(null);
    }

    // Shift each element to the "right" by however many spaces we're adding.
    for (var i = arr.length - 1; i >= newElesLength; i--) { // We start the loop at the "right" and move to the "left".
        //Note: There's no point in shifting all the way to 0, since we're going to copy over the first couple of elements anyway (indicated by newElesLength).

        arr[i] = arr[i - newElesLength];
        // Note: We're shifting it by an offset of newElesLength (not just 1, as we've seen in the Basic version).
    }

    // Copy all the new elements to the front of the array.
    for (var i = 1; i < arguments.length; i++) { // We know that indexes 1-> arguments.length - 1 contain our new elements.
        arr[i - 1] = arguments[i];
        // Note: Since i is 1, subtracing 1 will give us the correct index for our corresponding arr index.
    }
    
    // Return the new length.
    return arr.length;
}

Manual testing:

function unshift() {
    // Pull out our array from arguments.
    var arr = arguments[0];
    // Note: The first argument is our array.

    // Calculate the number of spaces we need.
    var newElesLength = arguments.length - 1; 
    // Note: The length of all our new arguments (the first element is the array, so we subtract 1).

    // Add empty spaces at the end of the array, for however many arguments we're adding.
    for (var i = 0; i < newElesLength; i++) { 
        arr.push(null);
    }

    // Shift each element to the "right" by however many spaces we're adding.
    for (var i = arr.length - 1; i >= newElesLength; i--) { // We start the loop at the "right" and move to the "left".
        //Note: There's no point in shifting all the way to 0, since we're going to copy over the first couple of elements anyway (indicated by newElesLength).

        arr[i] = arr[i - newElesLength];
        // Note: We're shifting it by an offset of newElesLength (not just 1, as we've seen in the Basic version).
    }

    // Copy all the new elements to the front of the array.
    for (var i = 1; i < arguments.length; i++) { // We know that indexes 1-> arguments.length - 1 contain our new elements.
        arr[i - 1] = arguments[i];
        // Note: Since i is 1, subtracing 1 will give us the correct index for our corresponding arr index.
    }
    
    // Return the new length.
    return arr.length;
}

var newArr = [1, 2, 3];

unshift(newArr, 40, 50, 80);
var newLength = unshift(newArr, 100);

console.log(newArr);
//Expected: [100, 40, 50, 80, 1, 2, 3]
console.log(newLength);
//Expected: 7

Advanced Section:

Excellent, now we have almost a fully fledged unshift function.

Exploratory:

Now, we can attach our function to the protoype (to finish emulation of the built-in function). In order to do so, we must understand that attaching a function object to a protoype is akin to setting a variable. In this case, we must attach it to Array.prototype. In order to successfully achieve our goal, we must understand the keyword this. this references the object of which the method is called upon.

Pseudo-code:

Array.prototype.our_unshift = function() {
    // Calculate the number of spaces we need.
    // Add empty spaces at the end of the array, for however many arguments we're adding.
    // Shift each element to the "right" by however many spaces we're adding.
    // Copy all the new elements to the front of the array.
    // Return the new length.
}

Implementation:

Array.prototype.our_unshift = function() {
    // Note: We do not need to pull out our array from arguments, since the keyword "this" IS our array.

    // Calculate the number of spaces we need.
    var newElesLength = arguments.length;
    // Note: No need to subtract 1 anymore, since all of the elements in arguments are new elements to be pushed.
    
    // Add empty spaces at the end of the array, for however many arguments we're adding.
    for (var i = 0; i < newElesLength; i++) {
        this.push(null);
    }

    // Shift each element to the "right" by however many spaces we're adding.
    for (var i = this.length - 1; i >= newElesLength; i--) { // We start the loop at the "right" and move to the "left".
        //Note: There's no point in shifting all the way to 0, since we're going to copy over the first couple of elements anyway (indicated by newElesLength).

        this[i] = this[i - newElesLength];
        // Note: The same as in the intermediate version.
    }

    // Copy all the new elements to the front of the array.
    for (var i = 0; i < newElesLength; i++) {
        this[i] = arguments[i];
        // Note: No offset necessary, since it's a direct index copy 0 -> 0, 1 -> 1...etc.
    }
    
    // Return the new length.
    return this.length;
}

Manual testing:

Array.prototype.our_unshift = function() {
    // Note: We do not need to pull out our array from arguments, since the keyword "this" IS our array.

    // Calculate the number of spaces we need.
    var newElesLength = arguments.length;

    // Add empty spaces at the end of the array, for however many arguments we're adding.
    for (var i = 0; i < newElesLength; i++) {
        this.push(null);
    }

    // Shift each element to the "right" by however many spaces we're adding.
    for (var i = this.length - 1; i >= newElesLength; i--) {
        this[i] = this[i - newElesLength];
    }

    // Copy all the new elements to the front of the array.
    for (var i = 0; i < newElesLength; i++) {
        this[i] = arguments[i];
    }
    
    // Return the new length.
    return this.length;
}

var newArr = [1, 2, 3];

newArr.our_unshift(20, 40);
var newLength = newArr.our_unshift(60);

console.log(newArr);
//Expected: [60, 20, 40, 1, 2, 3]
console.log(newLength);
//Expected: 6

Optional Notes:

  • This implementation does have to touch every element in the array.
  • It is slow (both the built-in function as well as this implementation are slow).
  • Instead of for looping and pushing null, you can choose to “forcefully extend” the array by adding directly to this.length (warning: kind of hacky).
  • It is very possible to shift by looping from “left to right” (incrementing), by starting at newElesLength and shifting by length of the original array (before adding new spaces).
  • It is also possible to copy the new elements by looping through arguments from “right to left” (decrementing) by starting at arguments.length - 1 and copying until 0 (inclusive).

Full Algorithm Writeups
#2

The examples above display a beauty of JavaScript. In the last advanced case, we create a new constructor function called our_unshift, which becomes a new property of the Array prototype object. Now, any array can inherit this property, so this proves that ANY array is an object in Javascript, because it is just an instance of the our_unshift constructor function shown above… for, example, we can declare arrays and they will inherit a new proprerty of Array.prototype, var arr = new Array() or var arr = []; arr.our_unshift(1); var arr = [1,2,3]; arr.our_unshift(1); In both cases arrays ARE objects, which inherit a new property in this case. But, even if we don’t create this new prototype property, Javascript engine still assigns a prototype object to any declared array, which has a blank constructor function.


#3

Request: Arrays - Min to Front (Chapter 3): Given an array of comparable values, move the lowest element to array’s front, shifting backward any elements previously ahead of it. Do not otherwise change the array’s order. Given [4,2,1,3,5], change it to [1,4,2,3,5]. Do so without using built-in functions.


#4

ij
Here is my advanced algorithm for pushing a singular or duplicate minimum values to the front of an array… This method should be working for any case whether there is a singular minimum or multiple of them exist in an array. It should also work if an array already contains minimum(s) at the front.

Please, leave comments, suggestions if this algorithm can be improved.


// Advanced Algorithm for pushing minimum value to the front of the array...

    function PushFront(arr){
		if (!Array.isArray(arr)){
			throw Error;
		}
		if (arr.length <= 1){
			return arr;		
		}
		let min = arr[0];
		let idx = 0;		
		let found = false;
		
		
		//Find a singular or duplicate minimum value by looping thru an array...
		
		for (var i=0; i<arr.length; i++){
			if ((arr[i+1] <= min) && (arr[i] != arr[i+1])){
				min = arr[i+1];
				idx = i+1;				
				found = true;							
			}
		}

		//Push a singular or duplicate minimum value to the front of the array if found...
		if(found){
			for (var j=idx; j>0; j--){
				arr[j] = arr[j-1];			
			}
			arr[0] = min;
			//Recursive Search for any duplicate(s) of a minimum value if exists... 
			PushFront(arr);			
		}		
		return arr;		
	}    
	console.log(PushFront([0,0,0,0,4,5,0,6,1,8,0,0,0,0,-1]));