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.

Introduction#

The Fibonacci sequence is probably one of the best know number sequences, with each number in the sequence being the sum of the two numbers that precede it, with 0 and 1 normally being the first two numbers of the sequence. The mathematical equation describing it is Xn+2= Xn+1 + Xn.

Solution Using a For Loop#

We can use the basic structure of the fizzbizz program as a template for writing this program. There are various ways to program the fibonacci sequence. The simplest way is to use a for loop. The more elegant solution is to use recursion. For this program we will assume that the only user input is to be able to specify the number of terms the user wants to calculate for the sequence.

Introduction#

Go is a language I have only recently learnt, and so I decided, for practice, to write some of the standard algorithms and data structures in Go. None of these are particular new, all of them can be found on the web already, but the exercise for me was partly to remind myself of them, and partly to see what I learned along the way. The first one I decided to start off with was FizzBuzz.