Our computers are not very smart. They are very good at computing, but if you ask a computer to do something, it can’t just figure it out. If we were to ask our computers a simple question at a low level right now, we could ask,

Hal, sort this list for me

And the computer would just say

I’m sorry Dave, I’m afraid I don’t know what sorting is

Even a five year old could hypothetically put things in order from smallest to largest on his or her own, but computers need a bit more help. We can think of our computers as very obedient dogs, that don’t necessarily know anything about sorting or human language inherently, but will do whatever you say if you say easy specific steps. We have to teach our computers everything.

Instructions

That is where algorithms come in. Algorithms represent the set of instructions for your obedient dog to follow in order to trick it into producing the output you want. If you’d like your dog to get you a Diet Coke from the refrigerator, you’d have to teach it what the refrigerator is, how to open it, how to tell the difference between Diet Coke and Pepsi, and how to bring it back to you. Each of these steps would take months of training, but eventually you could summon Diet Coke with one command, if you have a sick and twisted relationship with your dog.

With the computer, it has no inherent idea about “sorting”, but it does know about looking at elements in a list and comparing them. So how do we tell this machine to sort things if that’s all it knows?

It turns out there are a lot of different ways. We will start with the slowest, yet simplest one: selection sort.

Selection Sort

The idea behind selection sort is to go through a list with a comb and sort everything to the left of the list as you go, and when you come across the next element, find where it belongs, and move on to the next element. This will eventually produce the correct response. We will talk about what makes this effective or not in the future.

In order to teach our computer what “Go through the list and put them in order as you go” means, we have to write code. In JavaScript, the basic form of describing a list is called an Array. If you don’t know anything about arrays, check out this documentation.

Here is a quick implementation with comments:

module.exports = function selectionSort(array) {
	// Clone the array so that we don't change the original one
	var sortedArray = array.slice(0);
	// Walk through the list from the second item to the end
	for ( var j = 1; j < sortedArray.length; j++ ) {
		// Each time you get to an item, store it's value in "temp"
		var temp = sortedArray[j];
		// Start i one to the left of j
		var i = j - 1;

		// Walk through the list to the left from j until one 
		// of two things happen:
		//   1. We find an item that is less than temp, in
		//			which case we stop because we found where temp
		//			belongs
		//	 2. We reach the bottom of the list in which case
		//			temp is the smallest element
		// Otherwise, we keep shifting the items to the right,
		// making room for where temp eventually will belong.
		while ( i > -1 && sortedArray[i] > temp ) {
			// Shift the value one space to the right
			sortedArray[i+1] = sortedArray[i];
			// Move left and perform the check again
			i--;
		}

		// After going through that loop, we're left at a point
		// where the place temp belongs is one space to the right
		// of i. We put temp there and do the whole thing over for
		// the next item in the list
		sortedArray[i+1] = temp;
	};
	// Return the sortedArray.
	return sortedArray;
};

This code is able to take the unsorted array that we were given, and output a sorted array that has every element in order. Pretty cool!

Pet project

So now that I’ve written that in JavaScript, I’m going to write it again in C++, a language that is a bit different. I will be showcasing it tomorrow, and doing a comparison between the pain points of each language implementation.

Overall, my goal is to create a library of JavaScript algorithms and C++ algorithms that will add to my utility belt of code and improve my general code-writing abilities in each language. Interviewers often ask a lot about algorithms, and if they think it’s important for getting a job as a developer, then it probably is important for being a developer.

Keep track of the progress on this blog or check out the code yourself at algorithm-js and algorithm-plus-plus!

---

Tweet

---