Introduction#

A binary tree is a tree where each node has up to two leaves, and each of those leaves has up to two leaves. So you start with a root node and then fan out, like a genealogical tree.

The way the insertion works is that you look at the root node and decided whether the value you are trying to insert is less than or greater than the root node node value. If less than then you go down the left hand, if more than then the right. You repeat this process for each node in turn. The result is that the tree is automatically sorted, just by insertion. Because you are essentially halving the number of items you need to investigate each time, this is very efficient.

Introduction#

The Quick Sort algorithm uses what is known as a divide and conquor technique. It revolves around the idea of choosing a particular element in the array and then doing what is called pivoting around that. Essentially, all the elements less than the pivot go into the left hand array, all the elements greater than the pivot go into the right had array. The pivot itself can be choosen in different ways. It can be:

Introduction#

The merge sort is a bit more complicated than the bubble sort and insertion sort as you can see by the code below. In principle the merge sort works by splitting the array in half, and then splitting each of those two parts in half, and then splitting each of those four parts in half, etc, until we have elements of a maximum of two elements. We then sort and merge those elements in a specific order to ensure that the end result is the sorted array we were wanting.

Introduction#

Another way of sorting an array is by using the insertion sort method. In this case we start at position 1 in the array¹. We then set j = i, or in this case, 1. We then compare array[j - 1] with array[j], i.e. array[0] and array[1]. If array[0] is greater than array[1], we swap them. Then we subtract 1 from j and if j is greater than zero, we do the next j, other we break and do the next i. In one sense this is very similar to the bubble sort, but we do not have to loop through the entire array each time, just part of it, which makes this faster and more efficient than the bubble sort. Let’s look at the code.

Introduction#

There are many different ways of sorting an array. One the simplest ways is the bubble sort. Essentially you start at the beginning of the array and compare element i with element i + 1. If i > i + 1, swap them, and increment i. This way the larger value bubbles up the array, hence the name bubble sort. You repeat this until there you can run through the entire array without swapping anything. At this point the array is sorted. As you can image, this works, but is certainly not very efficient.