I’m currently doing some work to prepare for my next exam in programming. The exam involves explaining and implementing algorithms, in particular sorting- and search algorithms. In this post I will present my two attempts of implementing one of each kind.
First we have a sorting algorithm. It is the traditional Bubble Sort. Well, I won’t present any advantages or disadvantages but most of the sorting algorithms are fairly inefficient on large amount of data. The best way, I guess, is to combine different methods to make a good algorithm.
In bubble sort you simply step through each index and for each index you step backwards from the end to the current. Each time you then compare the items in the indices and swap if so.
This is my implementation in C#:
public static void BubbleSort(int[] array) { int temp; /* Step through all indices. */ for (int i = 0; i < array.Length; i++) { /* Step through the indices backwards to index i. */ for (int y = array.Length - 1; y > i; y--) { /* Swap items if item y is less than item i. */ if (array[y] < array[i]) { temp = array[y]; array[y] = array[i]; array[i] = temp; } } } }
With some modifications you could make it usable on other kinds of data too. This could be done by passing an IEnumerable<T> instead of an array. An array is an IEnumerable which is inherited by IEnumerable<T>, a generic interface.
However, although this is C#, implementing this algorithm in other languages is easy. There are no language or platform specific stuff in my implementation.
Moving on to the search algorithm. I have implemented a recursive version of Binary Search.
Basically, it cleaves the the list of sorted numbers in half and checks in which part it has a chance of finding the number to be searched for. This is done repeatedly until it has found the value.
Here’s the implementation:
public static int BinarySearch(this int[] array, int value, int from, int to) { if(from < to) { int mid = (to + from) / 2; if (array[mid] == value) {
return mid; }
if (array[mid] > value) { return BinarySearch(array, value, mid, to); } else if (array[mid] < value) { return BinarySearch(array, value, from, mid); } }
return -1; }
This implementation of the algorithm has some flaws, it will return the last occurence of a number if it finds any other than just one.
But per definition this should be enough because ‘2’ is ‘2’ and nothing else. Doesn’t matter if it is sorted.
Updated: October 29th, 2009.
Recent Comments