DEV Community: chrisding7

Basic Sorting Algorithms

chrisding7 — Tue, 22 Nov 2022 21:15:30 +0000

Whether in real life or in the world of programming, being able to sort through data is tremendously useful. Think of how many times you have wished a mess would clean itself up on its own! Sorting algorithms are commonly written as a solution to these types of problems in programming.

So, what is a sorting algorithm? A sorting algorithm is an algorithm that is used to rearrange and sort a given array or list of elements. There are dozens of well-known sorting algorithms, each with their own unique manner of sorting and rearranging elements. Some are chosen over others for their ease of implementation, while others are chosen for their superior time complexity when run against larger collections of data. Today, we will focus on a few of the more basic sorting algorithms and visualize how they differ from one another.

Selection Sort

Selection sort is often viewed as the most basic of sorting algorithms, and chances are that if you have sorted an array at a beginner level, it was likely using selection sort (or something similar). Think of holding playing cards in your hand--to sort them in ascending order, most people would look for the lowest numbers first (in this case let's say 2's) and place them towards the left of their hand. Next, they would look for all of the next highest numbers and place them towards the left, and so on.

In coding terms, imagine an unsorted array [34, 25, 14, 22, 11]. Starting at the index of the first unsorted value, selection sort will traverse the entire array from left to right, replacing the first unsorted value with the local minimum of the traversed elements. Everything to the left of the next unsorted value will be considered sorted.

34 25 14 22 11

11 25 14 22 34

11 25 14 22 34

11 14 25 22 34

11 14 25 22 34

11 14 22 25 34

11 14 22 25 34

11 14 22 25 34

SelectionSort Demo

Insertion Sort

Insertion sort is also a relatively basic sorting algorithm that is widely used for smaller datasets. It also involves splitting a collection of elements into a sorted and unsorted portion and comparing elements between the two. Let us use our previous unsorted array for this example: [34, 25, 14, 22, 11]

Insertion sort will initially compare the first two elements of the array and swap them if unsorted. in this case, 25 has been swapped with 34 and is considered part of a sorted sub-portion of our array.

34 25 14 22 11

25 34 14 22 11

Next, 34 is compared with 14, the next unsorted element in our array, and they are swapped. Now, 14 will be compared with our "sorted" sub-portion and will be swapped with 25.

25 34 14 22 11

25 14 34 22 11

14 25 34 22 11

This process repeats until the collection has been sorted:

14 25 34 22 11

14 25 22 34 11

14 22 25 34 11

14 22 25 11 34

14 22 11 25 34

14 11 22 25 34

11 14 22 25 34

11 14 22 25 34

InsertionSort Demo

Merge Sort

Merge sort is a slightly more complex algorithm that utilizes recursion to sort data. If you haven't worked with recursion, learning about the merge sort algorithm is also a great introduction to recursion. Let's use an array with a couple of more elements to demonstrate merge sort: [38, 27, 43, 3, 9 , 82, 10]

Merge sort will initially split the array into equal halves (or in the case of odd-numbered elements, almost-equal halves). Then, it will recursively split each half into smaller halves again and again until each split "half" cannot be split anymore, such that each recursively-split "half" represents a single element of the original array. The halves are then compared with their prior-split counterparts and sorted in small groups. These small groups are then compared with the next prior-split small group and sorted again--this process is repeated until all of the groups have been merged back together in sorted order. It is important to note that merge sort will prioritize completely sorting each "half" or "split-group" before merging halves back together. The diagram below shows the steps in which the merge sort algorithm acts.

MergeSort Demo

Why so many algorithms?

The main reason sorting algorithms are implemented are to save time in the long-run, but what happens when you have to choose between these different sorting algorithms to save time? Using our playing card example, it is easy to imagine looking through 5 or so cards and sorting them using an algorithm like selection sort--but how about when the hand gets to 20, 100, even 1000 cards? It's much easier to imagine dividing that hand up between 2, 4, even 8 or more people and utilizing something like merge sort!

Some sorting algorithms perform more efficiently than others on average, and that's just the way it is. However, some algorithms are easier to implement when saving time is not an issue, such as implementing selection sort and insertion sort when working with very small sets of data. While saving time is important, saving the hassle of writing difficult code is also crucial to many programmers!

Introduction to Linked Lists

chrisding7 — Tue, 25 Oct 2022 08:52:49 +0000

Linked lists are a relatively common type of data structure that you may run into throughout your programming journey. They are especially common in technical job interviews as well as acting as building blocks for some more complex data structures. As a result, they are very important for budding programmers to familiarize themselves with.

Linked lists can be compared to arrays, as they have similar structures and functions. However, each will have its own distinct advantages and disadvantages that will dictate how and when you utilize them.

As shown above, you can visualize an array as one large "box" that is partitioned into several smaller sections that each contain a data point, such as an integer. Linked lists are very similar--instead of one big box, think of a linked list as several small boxes that are connected to each other. Each box will contain data and "point" to the next box in the list, hence the name: linked lists:

Each "box" in a linked list is oftentimes referred to as a node. Additionally, the first and last node in a linked list are usually called the head and tail nodes respectively.

Now that we know what a linked list is, how do we implement it with code? With object-oriented programming in mind, we will want to eventually have a class for both our Node and our Linked List, but for simplicity's sake, we will be building a simple linked list with only Node objects. Starting with our Node class, we want to define a Node to have two properties: data and next. Data will hold the actual data within the node, and next will hold the pointer to the next node in the list (which will be initialized as null).

class Node {
    constructor(data)
    {
        this.data = data;
        this.next = null
    }
}

If we wanted to recreate the linked list pictured above, we would create our first Node and assign it to a new variable, head, with its initial value of 1. We would then have to create the rest of the nodes and assign their pointers to each other, as shown below:

const head = new Node(1);
const nodeB = new Node(2);
const nodeC= new Node(3);
const nodeD = new Node(4);
const nodeE= new Node(5);

head.next = nodeB;
nodeB.next = nodeC;
nodeC.next = nodeD;
nodeD.next = nodeE;

Note that nodeE never has its .next assigned to a Node and remains null. We have created a singly linked list, which means our linked list is one-directional and only points forward. This makes it easy for us to write code that will recognize when the end of the linked list has been reached. For example, if we wanted to write a function that counted the number of nodes in a linked list (think 'length of an array' as a comparison), we could implement it as such:

function countNodes(head) {
    let counter = 1;
    let currentNode = head;
    while (currentNode.next != null) {
        currentNode = currentNode.next;
        counter += 1;
    }
}

We have just implemented a function that steps through a linked list from its head node and increments a counter variable each time a node successfully points to another node that is not null! The code snippets above are oversimplified, and creating a LinkedList class would clean up our code and allow us to write more complex functions for other purposes, such as inserting and removing nodes from a linked list. However, the basics of linked lists include the structure of a node and how the pointers affect the interactions between nodes.

The next question you may have is, "when would I use a linked list?" A small disadvantage of linked lists is that indexing or searching through a linked list takes linear time, meaning that it has to traverse the entire structure (and therefore every element) while indexing or searching. However, linked lists are able to insert and delete nodes with more efficient time complexity than arrays. They are also used as a foundation for other complex data structures, such as trees. Try and see if you can recognize the linked list structure in the tree pictured below!

Stacks and Queues in JavaScript

chrisding7 — Tue, 11 Oct 2022 10:27:44 +0000

Once you have familiarized yourself with arrays in JavaScript, it's time to learn about some more types of data structures! Stacks and queues are quite similar in functionality to arrays, but have specific instances in which they can achieve better performance. Stacks and queues are relatively intuitive, and have plenty of real-world cases in which developers will find themselves implementing these useful data structures.

Stacks

Instead of visualizing a stack as a "horizontal" structure like an array, try and imagine a stack as a "vertical" structure, like a stack of plates piling on top of one another. You can think of a stack as a data structure in which you only insert and delete elements from one side of the structure. This is a common principle in programming called last in first out (LIFO). In other words, the elements inserted the latest at the top of the stack are also the first to be accessed and deleted. Using our plate analogy, the plates placed on top of the stack will be the easiest to grab and remove.

When working with stacks, the two most important operations used are push and pop--methods that we should recognize from working with arrays. Push is a destructive method that will insert a new element to the end (top) of our stack. Pop is also a destructive method, and will remove the most recent element from the stack.

While hard to notice at first, real-world examples of stacks are extremely common in web development. When searching the web and using a browser, your browsing history is constantly being logged using a stack. If you wish to return to your most recently visited page, a simple click of the "back" button will take you there. Additionally, we have all made use of the "undo" functionality when typing a document or using a text editor. Similar to browsing history, actions are tracked so that they can easily be accessed and "undone" using stacks.

Implementation

The simplest way to implement a stack in JavaScript is to utilize the push and pop array methods that the language already provides us with. Therefore, we can create an array and use the push and pop methods to create our operations and give us a working stack:

const stack = [];
const firstElement = 1;
const secondElement = 2;

const push = (element) => stack.push(element);
const pop = () => stack.pop();

push(firstElement);
push(secondElement);

console.log(stack) // [1, 2]
pop();
console.log(stack) // [1]

Now, you may be thinking that this just looks like an ordinary array that solely uses the push and pop methods--and you would be correct. In such a case that we can utilize an array as a stack, we should! This is because the time complexity of the push and pop methods will always be O(1). In simple terms, no matter what the size of the stack is, the time spent executing these operations will remain the same. (More on time complexity can be read here)

Queues

Now that we understand stacks, queues should also be relatively intuitive to understand. Instead of a stack of plates, a queue can simply be thought of as a line of people waiting for something. They could be waiting in line for movie tickets, a restaurant reservation, or even the restroom, but will follow the same rule of thumb--first come, first served. If stacks were associated with last in first out (LIFO), queues are associated with first in first out (FIFO).

When working with queues, the two most important operations used are enqueue and dequeue. Enqueue will be responsible for adding a new element to the end of our queue (back of the line), and dequeue will be responsible for removing the oldest element from the front of our queue (first person in line).

Implementation

Like implementing a stack, the simplest way to implement a queue in JavaScript is to utilize existing methods provided to us. Since the enqueue operation works the same as the push operation, we will use the push array method to implement enqueue. For dequeue, JavaScript yet again provides us with an existing array method to remove the first element of an array: shift.

const queue = [];
const firstElement = 1;
const secondElement = 2;

const enqueue = (element) => queue.push(element);
const dequeue = () => queue.shift();

enqueue(firstElement);
enqueue(secondElement);

console.log(queue) // [1, 2]
dequeue();
console.log(queue) // [2]

It should be noted that this is a simple method of creating a queue, but may not necessarily be the most efficient. One interesting thing to note about the time complexity of our stack and queue is that both our push and pop operations from our stack have a time complexity of O(1), while our dequeue operation will have a time complexity of O(n). This is because the shift array method is used in the implementation of dequeue and shares the same time complexity. Nevertheless, both stacks and queues can be extremely useful in their respective use-case scenarios. They can each help us organize data in sequential order while retaining efficiency in our code.

JavaScript Arrays for Beginners

chrisding7 — Tue, 20 Sep 2022 05:28:20 +0000

Picture yourself meeting a new friend or acquaintance for the first time. One of the first things that you probably learn about them is their name, right? In JavaScript, you have probably learned about variables, which are pivotal for your JavaScript foundation when first learning how to program. Variables are extremely important because they help us to store pieces of information, such as a name, so that we can access this information later and don't have to metaphorically ask for someone's name over and over again!

However, remembering a single name is not particularly difficult...but what happens when you have to start remembering tens, hundreds, or even thousands of names? Arrays help us with this problem, as they are one of the most common types of data structures found not only in JavaScript, but in almost every existing programming language. If you are unfamiliar with data structures, they are essentially "data containers" that help us organize and access data when we are programming. Today, we will be learning about and working with arrays, a relatively simple and straightforward type of data structure widely used by programmers everywhere.

You can think about arrays as a "list", where the order of items matter:
[1, 2, 3] is not the same as [1, 3, 2].

Although the two arrays above contain the same elements, these arrays are unique and distinct.

Another special note about JavaScript arrays are that the data types within an array can be mixed together: [1, "1", null]

Here, we see that we have a number (integer), a String, and a null value all contained within a single array. This property of JavaScript arrays is not universally shared across all programming languages, so it is important to know how an array handles properties in your language of choice.

So how do we create a JavaScript array? As shown above, you can create an array using array literal syntax and fill a pair of square brackets with elements of your choosing separated by commas. Logically, you can also assign an array like this to a variable:

const myArray = ["This", "is", "array", "literal", "syntax"];

Checking the length of an array is also as easy as using the built-in length property of JavaScript arrays:

myArray.length;
// => 5

Now that we can create arrays, what can we do with them? We will often find ourselves wanting to access the elements within an array, using bracket notation. Bracket notation utilizes the fact that each element of an array has a designated index, or "place in line" within the array. It is crucial to note that the index of the first element in an array starts at 0! Therefore, the last element in an array will always have an index of Array.length - 1.

myArray[0];
// => "This"
myArray[myArray.length - 1];
// => "syntax"
myArray[4];
// => "syntax"

What if we want to update existing values within an array? We can do that with bracket notation too!

myArray[0] = "Now THIS";
myArray;
// => ["Now THIS", "is", "array", "literal", "syntax"]

As you may have noticed, we can freely reassign the individual elements within an array using the = operator despite the fact that myArray was declared using const.

Now that you have the basics of arrays down, we can move onto the more complex intricacies of arrays! In my next blog post, I will be going over adding and removing array elements, iterating and looping through arrays, as well as how built-in array methods can help solve many common tasks we face when using arrays.