Visually Explained Algorithms The Merge Sort algorithm sorts an array of items in ascending order. Merge Sort is a divide-and-conquer type of algorithm. The algorithm takes n elements and recursively keeps dividing them until it reaches a state where there is only one element that it needs to focus on. Once that state is reached, it starts to combine the elements and each time it combines them, it sorts them along the way. Let’s dive into an example. We’ll start off with an array containing 8 elements. The Merge Sort algorithm starts recursively dividing the array into n/2 sub-arrays. After the first division,
Category: Algorithms
Visually Explained Algorithms The insertion sort starts with the value at index 1 and compares it to the value at index 0. If the value at index 1 is less than the value at index 0, the values are swapped. The index is incremented, and the procedure is repeated. The best way to see this is with an example. We’ll start off with the following array. The algorithm starts at index position 1. The first comparison is executed. The insertion sort algorithm starts at index 1 and compares it to the index before, which in this case is index 0.
Visually Explained Algorithms Like most sorting algorithms, the Quick Sort algorithm sorts an array of items in ascending order. There are numerous approaches to Quick Sort. This article will focus on one method. T his approach selects the left-most element of the array as the pivot. It then compares it against the last element in the array. If the pivot is less than the element it’s being compared to, that element becomes the pivot and the left side is incremented. If the pivot is greater than the element it’s being compared to, the index value of that element is incremented. This occurs until
The heap denotes an ordered binary tree. A heap can be built from a one-dimensional array. In this one-dimensional array: n represents the index of the parent node (n = 1, 2, 3, …) 2n represents the index of the left child 2n + 1 represents the index of the right child If we have the following array, we can construct a heap from it following the rules outlined above. Since there are 6 elements, the heap will have 6 nodes. Although the indices of the array start at 0, when numbering the elements in the heap, the first element starts
We’ll look at two types of heaps: max-heap and min-heap. The root node (top-most node) of a min-heap contains the smallest value. Each child is larger than the parent. Once the heap was built in the previous example, a min-heap can be constructed from it. To build a min-heap, we’ll start from the floor(n/2) node. The reason for the floor is due to uneven number of nodes. If the number of nodes was 7, the starting position would be at floor(7/2) = floor(3.5) = 3. For our example, there are 6 nodes: floor(6/2) = floor(3) = 3 The starting position will be at the third
We looked at the construction of the min-heap tree from an already constructed tree. Min-heap can also be constructed directly from an array. If we look at the array that we used in the Creating a Heap from an Array article, we’ll see how easy it is to construct a min-heap from the array. We start by adding the first node, 7. Heaps are built from left to right. The next element that’s added is 2. Since we’re constructing a min-heap, all the children nodes must be smaller than the parent node. Number 2 is smaller than 7, so the two nodes are swapped. Next, element 9 is
The root node of a max-heap contains the largest value. Each child is smaller than the parent. We’ll start with the same array that we had in the previous few articles. We’ll first construct the heap. Next, we’ll start constructing the max-heap. Just like when we were constructing the min-heap, we’ll start with the 3rd node: floor(6/2) = floor(3) = 3 Since 9 has only one child node, 9 will be compared to 3. If the parent is less than the child, the nodes will be swapped. Since 9 is larger than 3, the nodes are not swapped. We move to the
Let’s use the same array that we used to construct the min-heap to create the max-heap from an array. We start by adding the first node, 7. We move top-to-bottom, left-to-right and we add the 2nd node, 2. Since 7 is larger than 2, the nodes remain in their current position. Next, 9 is added to the heap. Since 9 is larger than 7, the two nodes are swapped. Next, 4 is added as a child of 2. Since 4 is larger than 2, the two nodes are swapped. We observe that 4 moved up, so 4 is also compared to 9.
Visually Explained Algorithms I’ll begin by stating that inserting a node into the min-heap has been outlined in my other articles: Constructing Min-Heap from a Tree and Constructing Min-Heap from an Array. As a quick recap, you add it as the last element in the tree. You compare it with its parent, and if its larger, you swap the parent and the child. You keep comparing it with each parent going up the tree until you reach a point where either the parent is smaller than the node you’re inserting, or the node has reached the root. We’ll start by deleting the root
Visually Explained Algorithms Now that we know how to create a max-heap, we’ll move into sorting an array of values using heap sort. To sort the array using heap sort, we’ll keep creating max-heaps. Each time a max-heap is created, the root is removed and is considered sorted. Let’s start with the following example. The first step is to construct a tree from the array. We’ll follow the same procedure as outlined in my other article, Constructing Max-Heap from a Tree. To begin, 5 is swapped with 9 and then 5 is swapped with 7 to generate a max-heap. Considering that the