bookmark_borderMerge Sort in C#

Merge sort is an algorithm used to sort a collection of items using the divide and conquer paradigm. The algorithm was conceived by John von Neumann in 1945.

The algorithm works by breaking down a list into n sublists until each list has a length of one. This is accomplished by recursively calling a mergeSort function whose task is to identify the middle point of a given list or if there is no middle point return the size one list. Once we have reached the end of a particular branch and have two sublists of size one, the algorithm begins to merge the sublists. These merges will bubble up a sorted list. The function call stack below gives a better picture of this “bubbling up” nature.

Here is an implementation of merge sort with C#. It is based off the C code in GeeksForGeeks.

// Divides a given array in half until length one and then merges
static void mergeSort(int[] arr)
{
   if (arr.Length > 1)
   {
      int middlePoint = arr.Length / 2;
      int[] leftArr = new int[middlePoint];
      int[] rightArr = new int[arr.Length - middlePoint];
      for (int i = 0; i < middlePoint; i++)
      {
         leftArr[i] = arr[i];
      }
      for (int i = 0; i < (arr.Length - middlePoint); i++)
      {
         rightArr[i] = arr[middlePoint + i];
      }
      mergeSort(leftArr);
      mergeSort(rightArr);

      merge(arr, leftArr, rightArr);
   }
}

// Merges to arrays in order
static int[] merge(int[] merged, int[] left, int[] right)
{
   int indexLeft = 0, indexRight = 0, indexMerged = 0;

   while (indexLeft < left.Length && indexRight < right.Length)
   {
      if(left[indexLeft] <= right[indexRight])
      {
         merged[indexMerged] = left[indexLeft];
         indexLeft++;
      }
      else
      {
         merged[indexMerged] = right[indexRight];
         indexRight++;
      }
         indexMerged++;
   }

   while(indexLeft < left.Length)
   {
      merged[indexMerged] = left[indexLeft];
      indexLeft++;
      indexMerged++;
   }

   while (indexRight < right.Length)
   {
      merged[indexMerged] = right[indexRight];
      indexRight++;
      indexMerged++;
   }

   return merged;
}

// Driver
static void Main(string[] args)
{
   int[] myArray = { 5, 22, 1, 2, 45 };
   mergeSort(myArray);
   foreach(int item in myArray)
   {
      Console.Write(item + ","); // 1,2,5,22,45,
   }
}

Below is a function call stack to sort the array [5, 22, 1, 2, 45]. Notice that the algorithm keeps halving the list until both sides are of size 1. Once leftArray and rightArray are of length one, we call the merge function. Due to merge sort’s recursive structure we bubble up merging the sublists into each other. I have used the => symbol to signify the value returned by the function.

mergeSort([5, 22, 1, 2, 45])
mergeSort(leftArray = [5, 22])
	mergeSort(leftArray = [5]) 
	mergeSort(rightArray = [22])
	merge(merged = [5, 22], leftArray = [5], rightArray = [22]) => [5, 22]
mergeSort(rightArray = [1, 2, 45])
	mergeSort(leftArray = [1])
	mergeSort(rightArray = [2, 45])
		megerSort(leftArray = [2]) 
		mergeSort(rightArray = [45]) 
		merge(merged = [2, 45], leftArray = [2], rightArray = [45]) => [2, 45]
	merge(merged = [1, 2, 45], leftArray = [1], rightArray = [2, 45]) => [1, 2, 45]
merge(merged = [5, 22, 1, 2, 45], leftArray = [5, 22], rightArray = [1, 2, 45]) => [1, 2, 5, 22, 45]

bookmark_borderJavaScript: Shallow Copy vs Deep Copy

While working through the exercises in Eloquent JavaScript, there was an exercise where we had to implement a prepend function for a list object. It appeared simple but there was a small detail that would completely change the output of my function. Can you spot the difference between the two functions below?

const prependShallow = (element, list) => {
  return { value: element, rest: Object.assign({}, list) };
}

const prependDeep = (element, list) => {
  return { value: element, rest: list };
}

The first function returns a completely new list object with no internal references. The second function also returns a list object but the value in the key rest references the parameter list. Is either answer more correct that the other? I would say it depends on your objective and how you will be using the object. The shallow implementation follows the concept of creating a “pure” function. This has the benefit of not having any side-effects and making testing easier. However, there can be cases where performance is of upmost importance and using a reference instead of creating a copy can save us processing time and memory.

Primitive and Composite/Complex Data Types

Before going into shallow vs deep copying let’s quickly review data types as they provide us with the necessary framework to process the why’s of shallow and deep copying.

A primitive data type is usually built-in to the language and is part of the building blocks of the language. These values are typically stored directly into a computer memory address and are often passed by value. JavaScript has seven primitive types:

  • Boolean
  • null
  • undefined
  • Number
  • BigInt
  • String
  • Symbol

A composite/complex data type consists of a grouping of primitive data types as seen in arrays or objects. These values typically contain a reference (a memory address) to the actual physical location where the grouping begins (i.e. arr[0]). JavaScript has one composite/complex type which is Object. Why do composite data types store a reference instead of a value? Imagine having an array with 10,000 elements, now imagine having to pass that array by value to a function. Passing these values by reference allows us to better use computer space (memory) and time (processor).

It is worth noting that in JavaScript the composite/complex data type Object is the ancestor of most non-primitive entities. The prototype of an array is the Array object whose prototype is Object. The prototype of a function is also Object.

Shallow Copy vs. Deep Copy

The concept of shallow and deep copying only applies to composite/complex data types as these entities are passed by reference.

A deep copy is when two objects, our original object and the copy object, point to the same memory location. This means any change to either object will be reflected in the other. Since they reference the same memory location, they will have the same keys and values.

A shallow copy may contain the same keys and values as the original but it points to its own memory location. It has no tie internally to the object it has copied. Therefore, a change in either object will not be reflected in the other.

Let’s follow through an example. We have a binding dog that will be our original object and two copies a dogDeepCopy and a dogShallowCopy. The image below illustrates how our bindings may look in memory. Note that dog and dogDeepCopy are pointing to the same memory address (rectangle).

let dog = {
  name: "Cookie",
  age: 5
};
let dogDeepCopy = dog;
let dogShallowCopy = Object.assign({}, dog);

JavaScript defines the use of the equality operator, ==, on two objects to test whether two objects are referencing the same memory location. An expression with this operator and two objects will return true if they point to the same memory location and false if they don’t. It does not do a comparison between the keys and values of the objects (more on that later).

console.log("dog == dogDeepCopy -> " + (dog == dogDeepCopy));
console.log("dog == dogShallowCopy -> " + (dog == dogShallowCopy));

/*
'dog == dogDeepCopy -> true'
'dog == dogShallowCopy -> false'
*/

Again since dogDeepCopy points to the same location as dog, any changes to either object will be reflected on the other object. However, since our shallow copy dogShallowCopy is operating on its own own memory block we do not exhibit that behavior. Try working through the statements below before seeing their output for a small exercise!

//Change dogDeepCopy name
dogDeepCopy.name = "Cookie";
console.log("dog.name -> " + dog.name);
console.log("dogDeepCopy.name -> " + dogDeepCopy.name);
console.log("dogShallowCopy.name ->" + dogShallowCopy.name);

//Change dog name
dog.name = "Brownie";
console.log("dog.name -> " + dog.name);
console.log("dogDeepCopy.name -> " + dogDeepCopy.name);
console.log("dogShallowCopy.name ->" + dogShallowCopy.name);

//Change dogShallowCopy name
dogShallowCopy.name = "Ice";
console.log("dog.name -> " + dog.name);
console.log("dogDeepCopy.name -> " + dogDeepCopy.name);
console.log("dogShallowCopy.name ->" + dogShallowCopy.name);

/*
'dog.name -> Cookie'
'dogDeepCopy.name -> Cookie'
'dogShallowCopy.name ->Brownie'
'dog.name -> Brownie'
'dogDeepCopy.name -> Brownie'
'dogShallowCopy.name ->Brownie'
'dog.name -> Brownie'
'dogDeepCopy.name -> Brownie'
'dogShallowCopy.name ->Ice'
*/

Object.create() vs Object.assign()

A newbie mistake I made when first learning this concept with objects was using the Object.create() and Object.assign() functions interchangeably. JavaScript will go look for a property in it’s prototype (and so forth) if it does not directly find it in it’s own direct properties. I initially believed I had created a shallow copy with Object.create() however, a closer inspection showed I had no direct properties and my “copy’s” prototype contained a reference to my original object. This meant changing the original object reflected the change on my “copy’s” prototype which led me to become aware of my mistake. (A true shallow copy would have not exhibited this behavior.)

Object.create() is to be used when you want to create a new object and have it’s prototype be an existing object. Object.assign() is used to copy the properties of a source object into a target object.

The code below is erroneous. It uses Object.create() to try and create a shallow copy but we can see that the original object is copied into the copied object’s prototype. Note that we can still access the property name in dogCopy even though it is part of it’s prototype and not a direct property.

let dog = {
  name: 'Brownie',
  age: 5
};
let dogCopy = Object.create(dog);

console.log("dog.name -> " + dog.name);
console.log("dogCopy.name -> " + dogCopy.name);

// Change dog name, notice the error: we didn't want dogCopy to change name
dog.name = 'Ice';
console.log("dog.name -> " + dog.name);
console.log("dogCopy.name -> " + dogCopy.name);

// See object's direct properties
console.log("dog keys -> " + Object.keys(dog));
console.log("dogCopy keys -> " + Object.keys(dogCopy));
console.log("dogCopy prototype property 'name' -> " + dogCopy.__proto__.name);

/*
'dog.name -> Brownie'
'dogCopy.name -> Brownie'
'dog.name -> Ice'
'dogCopy.name -> Ice'
'dog keys -> name,age'
'dogCopy keys -> '
'dogCopy prototype property 'name' -> Ice'
*/

Arrays

The concept of shallow and deep copying is also relevant to arrays. Recall arrays are also of type Object in JavaScript. You can create a shallow copy of an existing array with the spread operator: ‘…’. The example below shows the same properties described above with arrays.

let arr = [1, 2, 3];
let arrDeepCopy = arr;
let arrShallowCopy = [...arr];

console.log("arr == arrDeepCopy -> " + (arr == arrDeepCopy));
console.log("arr == arrShallowCopy -> " + (arr == arrShallowCopy));

console.log("Push '4' to arr");
arr.push(4);
console.log("arr -> " + arr);
console.log("arrDeepCopy -> " + arrDeepCopy);
console.log("arrShallowCopy -> " + arrShallowCopy);

console.log("Push '5' to arr");
arrShallowCopy.push(5);
console.log("arr -> " + arr);
console.log("arrDeepCopy -> " + arrDeepCopy);
console.log("arrShallowCopy -> " + arrShallowCopy);

/*
'arr == arrDeepCopy -> true'
'arr == arrShallowCopy -> false'
'Push '4' to arr'
'arr -> 1,2,3,4'
'arrDeepCopy -> 1,2,3,4'
'arrShallowCopy -> 1,2,3'
'Push '5' to arr'
'arr -> 1,2,3,4'
'arrDeepCopy -> 1,2,3,4'
'arrShallowCopy -> 1,2,3,5'
*/

Shallow/Deep Copy vs Shallow/Deep Comparison

The concepts of shallow copy and deep copy is to be separated from the concept of shallow and deep comparison. These types of comparison check whether the contents of two objects are the same, that is they contain the same keys and the same values. A deep comparison will delve deeper by following through a reference until it reaches a value. A shallow comparison will not delve deeper if it encounters a reference. JavaScript does not have the built-in functionality to do these types of comparisons but you can write your own function or use an existing library. Remember the built-in functionality of using the equality operator, ==, with two objects is to check if the objects refer to the same memory location.

Last Words

If you are interested in reading through the book, Eloquent JavaScript, yourself it is available for free. Much gratitude to the author Marijn Haverbeke for creating this resource. The book is also available in print for those that prefer to handle a physical book (me).

bookmark_borderNotes to Self for Future Debian Installation

It hurt my heart to see my old PC gathering dust in my parent’s closet so I decided it would be good idea to turn it into a Linux workstation because my main PC has become clunky after installing new software for work. I know very little about Linux but I enjoy a challenge and tinkering with things. Plus, running a VM with Oracle VirtualBox gets old once you actually really start working. I know I could have started with a more user friendly OS like Ubuntu but I wanted to play around with an OS I would more likely encounter in a professional space. I’m also lazy about updating software so Debian sounded right.

I read the first few sentences off the main Debian installation page and decided to try the net install. I cleared my 4GB USB from 2010 and used the portable version of Rufus to make my USB bootable.

I opened my old PC’s UEFI and made my USB the main boot device and began the installation process. It was all going well until we reached the network part. Debian could detect my devices but couldn’t make use of them since the firmware was not installed (brcm/bcm43xx-0.fw and rtl_nic/rtl8168e-2.fw). It turns out, Debian does not ship with support for non-free firm/software and I was doing a net install so I couldn’t continue with the installation until I got my internet connection setup.

After scouring around for another spare USB, I downloaded the firmware off Debian’s site, enabled the command line tools on the Mac laptop and extracted them into the USB. I later found out those last two items were probably unnecessary since we have access to a terminal during our installation. After a while of searching, I found this beautiful post perfectly outlining all the necessary steps to get Debian to find the firmware for my network adapter.

After setting up the firmware the rest of the installation was almost pain free except I received a “Debootstrap error Failed to determine the codename for the release” error after having the wizard partition my hard drive. After following the instructions from this StackOverflow thread I was able to continue with the “Install the base system” step and finish my installation.

After the installation completed, I attempted to boot into my new system. However, now I needed firmware for my graphic card (Error encountered read: ” Radeon kernel modesetting requires firmware”) so I was only able to use the tttyl terminal. Since I had provided the firmware for my network adapter during installation, I thought I could get the missing firmware with apt-get however, none of the network things that had been configured during installation were there! So there I was again, with no internet connection and the firmware I had loaded in previously was gone. I stepped through the process again mounting the same USB with the firmware files into a temporary folder in lib/firmware and moving the necessary files into lib/firmware. The missing firmware error cleared. However, I was still unable to connect to the internet.

The remaining process was actually quite backwards. My internet search led to a variety of different possible causes but as a newbie, I had trouble discerning what even applied to my case. Even though my network adapter was now being recognized, I needed to set it up as a network. After setting up the network, I was still unable to connect to the internet. I came across this article that said I need to provide my WPA password and network name. The question had previously popped into my mind: how can I log into a network that is locked behind a password? But ignored my gut feeling, believing I would get an error that would say specify the network name. After setting up my network, entering the username and password into /etc/network/interfaces and rebooting my system, I was able to connect to the internet! My routes table was no longer empty and a default gateway had been automatically entered by the system. There was no need to edit anything in my resolvd.config table as many of the threads recommended.

Finally, I could go back and continue with the package I wanted to install through apt-get. The package included firmware for my graphics card so I could use the GUI. After making some small changes to /sources.list to allow non-free package installation, I was able to install the firmware-amd-linux package. After another reboot, I was finally booted into my chosen DE and could also see the Wicd Network Manager.

In retrospect, the experience brought me to appreciate what more user friendly OS’s have done to allow computers and the internet become more accessible.

Lastly, this one is a given, but I kind of dived into this without reading any documentation. I believe the experience would have been smoother would I have at least skimmed through the Debian installation guide. In other words, the “errors” I encountered would have been expected as they are documented.