New Zealand Space Program by 2015

"The world is going to change".

United States, Russia, India, China are some of the countries who have one thing in common right now, they all have a space program. There are even more countries with space programs even Australia but New Zealand does not. Why not New Zealand? That is about to change by 2015 and it is an exciting time, for me at least!
I present to you my latest news finding on the internet, the New Zealand Space Program which you can read at:
http://www.nzherald.co.nz/business/news/article.cfm?c_id=3&objectid=11300831

I present to you a video also found on the above link:





The company behind this is Rocket Lab and I like the name of their rocket "Electron".

"The world is going to change"

Insertion Sort

Insertion sort algorithm is interesting because it feels more natural. If you had a randomly sorted deck of cards and picked up one card, it is already sorted. If you picked up another card you would "insert" it into a sorted order which will either be before or after the card you already have. You now have two cards and pick up the third card. At this point you will "traverse" the cards you have and inserted it at the appropriate point, repeating the process until you have the desired number of cards in your hands in some sorted order. This process is an iterative search and should not be confused with a priori, a trait human beings are likely to apply or in short a human being will likely "just know where to place the card" upon looking at what is already in hand.

Insertion sort starts by indexing the first element which it deems is in correct order since the current index is the same as the first index. The index is moved up one and the element at the new index is compared or iterated backwards until a suitable position is found to insert the current element into. A good way to solve this is to store the current element into a temporary buffer. Then as you traverse backwards you swap each previous index with current index until you find where to place the stored element and copy that into the new location. The diagram below illustrates the process which I feel describes it more clearly than words:

To build this into code we need two methods. First method is the InsertionSort method that traverses the array of n elements. At each incremental traversal a second method, Insert, is called which inserts the current element being traversed into the appropriate slot.

InsertionSort code:

public int InsertionSort(ref int[] array)
{
  int swapcount = 0;
  for (int i = 1; i < array.Length; i++)
  {
    swapcount += Insert(ref array, i);
  }
  return swapcount;
}

In the above code inside the for loop Insert method is called which is passed the index of the current element being looked at and the array.

Insert code:

private int Insert(ref int[] array, int i)
{
  int swapcount = 0;
  for(int j = i - 1; j >= 0; j--)
  {
    if (array[j] >= array[i])
    {
      Swap(ref array, i, j);
      i = j;
      swapcount++;
    }
   }
  return swapcount;
}

In the above Insert code the array is traversed backwards from an index previous to current index 'i' and each item is compared with the 'current' index 'i'. If current indexed element is smaller than the index previous to it a swap is made and the current index 'i' becomes the previous index 'j'. The loop stops when no more elements can be traversed backwards. One thing I did not include is storing the current index into a temp variable because the solution is so trivial we do not need a temp storage and it was only mentioned above to simplify the explanation. In the code above, optionally, a swap count is kept and returned. Also it is important to notice that unlike bubble sort where you could detect that no swap has taken place and rest assured array is sorted, you cannot do the same here. If the current element is larger than the element before it, we cannot stop the entire insertion sort since we cannot tell if elements after the current element are sorted.

This brings us to the running time which is also quadratic at O(n^2) if none of the data is sorted. However there is one exception and that is Insertion sort can achieve O(n) time if all the data is already sorted. This is because the InsertionSort method will traverse n data and Insert will return with O(1) time because the loop will terminate if the first comparison reveals that no swap should take place in the already sorted portion of the array. We can detect this with a simple modification to our Insert algorithm:

private int Insert(ref int[] array, int i)
{
  int swapcount = 0;
  for(int j = i - 1; j >= 0; j--)
  {
    if (array[j] >= array[i])
    {
      Swap(ref array, i, j);
      i = j;
      swapcount++;
    }
    else break;
  }
  return swapcount;
}

The extra code is in green which detects, much like bubble sort, if no swap has taken place and breaks the for-loop. It does not abort the entire insertion sort algorithm which happens in bubble sort but only the current passes insert algorithm. Like bubble sort and selection sort, insertion sort is also an in-place algorithm because it requires little or no additional memory to perform its operation.

The best use for insertion sort algorithm is on data that is already mostly sorted in order to reduce the quadratic time. For data that is completely unsorted a better option, from the algorithms covered so far, would be selection sort because although it has a cost of O(n^2) it will have considerably less cost in swapping data.

Next: QuickSort.
Previous: Selection Sort.
Landing page: Part One.

Selection Sort

Previously we looked at bubble sort algorithm which has O(n^2) quadratic time regardless of order of original collection. The problem with bubble sort is compounded by the number of swaps it has to do within each pass. Everytime the algorithm encounters a unordered comparison, it does a swap which is costly. To avoid that we have selection sort which produces considerably less swaps.

Selection sort works by performing a number of passes identical to bubble sort however the difference is how the inner loop works. Unlike bubble sort, selection sort does not perform a swap every time it encounters two unordered comparisons. Index of largest element is sought. Once obtained and at the conclusion of the inner loop, the last element of the array is swapped with this largest element. The problem domain is then reduced by one since after the first pass the largest value is now in its sorted position. The cycle repeats up to the final pass. Obvious advantage is less data swapping compared to Bubble sort but worst case running time is still O(n^2). Best case is also O(n^2) since every element is scanned per pass.

Here is the sequence of events for selection sort.
Initial: 6 1 3 2 7 5 4
6 1 3 2 4 5 7 //Largest element: 7 at index 4. Swap with end element, 4.
5 1 3 2 4 6 7 //Largest element: 6 at index 0. Swap with end element, 5.
4 1 3 2 5 6 7 //Largest element: 5 at index 0. Swap with end element, 4.
2 1 3 4 5 6 7 //Largest element: 4 at index 0. Swap with end element, 2. 
2 1 3 4 5 6 7 //Largest element: 3 at index 2. No change last element == end element.
1 2 3 4 5 6 7 //Largest element: 2 at index 0. Swap with end element, 1.  
Done.

Like bubble sort, selection sort algorithm is also an in-place algorithm. What this means is that it uses little extra memory to complete its sorting operation. The source code for selection sort:

public int SelectionSort(ref int[] array)
{
  int swapcount = 0;
  for (int i = array.Length-1; i >= 0; i-- )
  {
    int index = 0;
    for (int j = 0; j <= i; j++)
    {
      if (array[j] >= array[index]) index = j;
    }
    if (index != i)
    {
      Swap(ref array, i, index);
      swapcount++;
    }
  }
  return swapcount;
}

How does the above code work:
The first loop is the number of passes and runs from 0 - n as index 'i'. The innerloop also runs from 0-n however in this instant n = i. The inner loop compares the item at stored index with item currently being looked at. If item of stored index is smaller then index is updated. Once the inner loop terminates for current pass, a swap is made if index of largest items is not the same as index of final element. Every time a swap is made a count is kept and this is returned at the conclusion of the algorithm.

Next: Insertion Sort.
Previous: Bubble Sort.
Landing page: Part One.

Bubble sort algorithm

First section of part one, this covers bubble sort algorithm.
Largest values are "Bubbled up" on each pass by swapping them between current element and next element. Each comparison is run n-1 times over n-1 passes. This leads to a time complexity of O((n-1)^2) or O(n^2). 
We can detect if data was sorted by checking if any swaps took place. If no swap, we stop the algorithm and this leads to O(n) time on data that is already sorted.

Let's look at how this works by using an unsorted array 6 1 3 2 7 5 4.
In the first pass we scan the entire array "bubbling up" the largest value to the end whose index starts from zero and goes up to six.
In the first pass we compare the entire array starting at index zero by comparing element at index with element at index + one. In our example we see if 6 > 1 and it is so we swap and have a new array 1 6 3 2 7 5 4.
We increment the counter still within first pass and now check if 6 > 3. Yes it is so we swap and get 1 3 6 2 7 5 4. Carrying on we get:
1 3 2 6 7 5 4
1 3 2 6 7 5 4
1 3 2 6 5 7 4
1 3 2 6 5 4 7
First pass done and the largest value, seven, in this pass is now at the end.

The second pass will start from zero again but only up to five because in the previous pass the 6th element has the largest value of the array and thus is in its final location.

For completeness here is what the second pass will look like:
initial: 1 3 2 6 5 4 7
1 3 2 6 5 4 7 //no change as 1 > 3 is not true.
1 2 3 6 5 4 7 //swapped 3 and 2 as 3 > 2.
1 2 3 6 5 4 7 //no change as 3 > 6 is not true.
1 2 3 5 6 4 7 //swapped 6 and 5 as 6 > 5.
1 2 3 5 4 6 7 //swapped 6 and 4 as 6 > 4.
Done second pass.

If we look at this carefully we can see that in any given pass, if no swap takes place then the data must already be in their correct sorted order. If we detect that no swap takes place we can reduce the time complexity on sorted data to a single pass of O(n).  In the above example at the completion of pass two we can see that the algorithm only needs to run pass three before all the data is sorted and no more passes is required. Without this check bubble sort is always an O(n^2) algorithm regardless of the condition of the collection.

The bubble sort algorithm code is shown below complete with a check for swaps. It returns the number of passes that was done.

public int BubbleSort(ref int[] array)
{
  int swapped = 0;
  int i;
  for (i = array.Length-1; i >= 0; i--)
  {
    swapped = 0;
    for (int j = 0; j < i; j++)
    {
      if (array[j] > array[j + 1])
      {
        Swap(ref array, j, j + 1);
        swapped++;
      }
    }
    //No swap, data is already sorted, no need to continue.
    if (swapped == 0) break; 
  }
  return array.Length - i; //Returns the pass count.
}

How does the above code work:
There are two for-loops where the first for loop determines the number of passes and runs through n passes referred to as index 'i'. The second loop using index 'j' will run from zero up to 'i' and since at each pass 'i' reduces by one then 'j' will always start at zero and run through to the length of the current pass 'i' each time the second loop executes. The second loop counts how many swaps have occurred and if zero swaps has occurred then this detects that the data must already be sorted and terminates the algorithm. In this second loop each item at index j and j+1 is compared and swapped as necessary. As an option the method returns the number of passes that has occurred during this run.

This concludes the bubble sort algorithm.
Next: Selection Sort.
Previous: Landing page Part One.

Sort and search algorithms using C# Part one

Welcome to the introduction of searching and sorting algorithms in C# part one. This will be a two part series. The first part will introduce and talk about six sorting algorithms and one searching algorithm. These algorithms will be built using a single data type, an int. In part two, I will modify the algorithms from part one to allow more data types. The contents in each part will not attempt to teach C# as that information is left for the reader to investigate. Each algorithm will be posted once every week.

Most of what what a computer is expected to do is searching and sorting. Information found on search engines use searching algorithms, looking for a word in a text editor uses searching. Sorting is performed quite extensively and sometimes they are performed but not noticed. A list of music you have may be sorted in various ways such as alphabetical order of album name, or artist name, or even song name. Looking for a file in a directory you might be tempted to use one of its ordering functions. There are many things we do and some we don't even notice where powerful algorithms are working hard to provide you with a great user experience and of course to do it in the fastest way possible.

So why have I written this blog post when there are so many books and websites that already feature all of the algorithms I will present. The answer is that I will write it in a way that would make every attempt to produce understandable instructions and also provide complete example codes. Many of the algorithms follow a paradigm that will be immediately obvious if you have already done searches for how to write these algorithms. Furthermore this is a technology blog so it really wouldn't be complete without some sort of searching and sorting algorithm present.

The index below will provide what is to be expected in the coming weeks as well as serve as a landing page to jump straight to the appropriate algorithm. These links will be  updated as new algorithms are added to part one.

Algorithms covered:

1. Bubble Sort.
2. Selection Sort.
3. Insertion Sort.
4. Quick Sort.
5. Merge Sort.
6. Heap Sort.
7. Binary Search.

 I will begin right now with a method that we will use for all the sorting algorithms. It is a trivial method and ordinarily does not need to be mentioned, however for completeness, with care for any learner programmers, and to get things started, I will show the code for the "Swap" method.

The swap method takes a reference to an array of ints, and two indices 'i' and 'j' of the elements to swap. Inside the method element at index i is stored in a temporary storage variable and this element in the array is overwritten by the element at index j. Finally the element at index j is overwritten by the int we stored in the temporary variable.

Next: Bubble Sort.