Haversine Formula in C# and in SQL

The Haversine Formula class listed below is used to calculate the distance between two latitude/longitude points in either Kilometers or Miles.  I’ve seen the formula written in a few other languages but didn’t see any in C#.  So, here is the Haversine Formula in C#.  Before I show the class, let me give an example of how the class is called and used.

To start we will need 2 latitude/longitude points.  I created a struct to hold the  latitude/longitude points.  Once we have the points, we create the Haversine class and call the Distance method, passing in the points and an enum specifying whether to return the results in Kilometers or Miles.  We end up with the following:

Position pos1 = new Position();

pos1.Latitude = 40.7486;

pos1.Longitude = -73.9864;

 

Position pos2 = new Position();

pos2.Latitude = 24.7486;

pos2.Longitude = -72.9864;

 

Haversine hv = new Haversine();

double result = hv.Distance(pos1, pos2, DistanceType.Kilometers);

Here is the code for the class:

using System;

 

namespace HaversineFormula

{

    /// <summary>

    /// The distance type to return the results in.

    /// </summary>

    public enum DistanceType { Miles, Kilometers };

 

    /// <summary>

    /// Specifies a Latitude / Longitude point.

    /// </summary>

    public struct Position

    {

        public double Latitude;

        public double Longitude;

    }

 

    class Haversine

    {

        /// <summary>

        /// Returns the distance in miles or kilometers of any two

        /// latitude / longitude points.

        /// </summary>

        /// <param name=”pos1″></param>

        /// <param name=”pos2″></param>

        /// <param name=”type”></param>

        /// <returns></returns>

        public double Distance(Position pos1, Position pos2,DistanceType type)

        {

            double R = (type == DistanceType.Miles) ? 3960 : 6371;

 

            double dLat = this.toRadian(pos2.Latitude – pos1.Latitude);

            double dLon = this.toRadian(pos2.Longitude – pos1.Longitude);

 

            double a = Math.Sin(dLat / 2) * Math.Sin(dLat / 2) +

                Math.Cos(this.toRadian(pos1.Latitude)) *Math.Cos(this.toRadian(pos2.Latitude)) *

                Math.Sin(dLon / 2) * Math.Sin(dLon / 2);

            double c = 2 * Math.Asin(Math.Min(1, Math.Sqrt(a)));

            double d = R * c;

 

            return d;

        }

 

        /// <summary>

        /// Convert to Radians.

        /// </summary>

        /// <param name=”val”></param>

        /// <returns></returns>

        private double toRadian(double val)

        {

            return (Math.PI / 180) * val;

        }

    }

}

 Here is the same formula as a SQL function. I used Microsoft SQL server for this example.

CREATE FUNCTION [dbo].[GetDistance]

(

      @lat1 Float(8),

      @long1 Float(8),

      @lat2 Float(8),

      @long2 Float(8)

)

RETURNS Float(8)

AS

BEGIN

 

      DECLARE @R Float(8);

      DECLARE @dLat Float(8);

      DECLARE @dLon Float(8);

      DECLARE @a Float(8);

      DECLARE @c Float(8);

      DECLARE @d Float(8);

 

      SET @R = 3960;

      SET @dLat = RADIANS(@lat2 – @lat1);

      SET @dLon = RADIANS(@long2 – @long1);

 

      SET @a = SIN(@dLat / 2) * SIN(@dLat / 2) + COS(RADIANS(@lat1))

                        * COS(RADIANS(@lat2)) * SIN(@dLon / 2) *SIN(@dLon / 2);

      SET @c = 2 * ASIN(MIN(SQRT(@a)));

      SET @d = @R * @c;

 

      RETURN @d;

 

END

GO

 

– Seth Long

Quicksort / Insertion Sort Combo

My blog is now located at http://www.WhoIsSethLong.com

The Quicksort is one of the fastest sorting algorithms for sorting large lists of data.  The Insertion sort is a fast sorting algorithms for sorting very small lists that are already somewhat sorted.  We combine these two algorithms to come up with a very simple and effective method for sorting large lists.

We start our sort by using a Quicksort.  The Quicksort on average runs in O(n log(n)) time but can be as slow as O(n²) if we try to sort a list that is already sorted and use the left most element as our pivot.  If you are unfamiliar with the quicksort here is a Wikipedia article describing the algorithm: http://en.wikipedia.org/wiki/Quicksort

As the Quicksort works, it breaks down our list into smaller and smaller lists.  Once the lists become small enough that an Insertion sort becomes more efficient then the Quicksort we will switch to the Insertion sort to finish off the job.  Think of it as grinding away with the Quicksort then polishing it off with the Insertion sort once most of the work has been done.

Here is a code sample of a combined Quicksort and Insertion sort algorithm in C#.

class Quicksort

{

    public void Sort(int[] list, int start, int end)

    {

        if (start < end)

        {

            // This is where we switch to Insertion Sort!

            if ((end – start) < 9)

            {

                this.InsertionSort(list, start, end + 1);

            }

            else

            {

                int part = this.partition(list, start, end);

                this.Sort(list, start, part – 1);

                this.Sort(list, part + 1, end);

            }

        }

    }

    public void InsertionSort(int[] list, int start, int end)

    {

        for (int x = start + 1; x < end; x++)

        {

            int val = list[x];

            int j = x – 1;

            while (j >= 0 && val < list[j])

            {

                list[j + 1] = list[j];

                j–;

            }

            list[j + 1] = val;

        }

    }

    private int partition(int[] list, int leftIndex, int rightIndex)

    {

        int left = leftIndex;

        int right = rightIndex;

        int pivot = list[leftIndex];

        while (left < right)

        {

            if (list[left] < pivot)

            {

                left++;

                continue;

            }

            if (list[right] > pivot)

            {

                right–;

                continue;

            }

            int tmp = list[left];

            list[left] = list[right];

            list[right] = tmp;

            left++;

        }

        return left;

    }

}

Binary Search

My blog is now located at http://www.WhoIsSethLong.com

A binary search is used to find if a value exists or what it’s position is in a sorted list.  You may have noticed that I put “sorted” in italics.  That’s because in order for the binary search to work, it must have a sorted list.

To better explain how the binary search works, lets walk through a simple example.  We will start off with a sorted list of numbers.

3, 5, 6, 9, 11, 12, 14

Next, we’ll need a number to search for.  For this example we’ll choose the number 12.

The binary search starts by selecting the middle position of the array and getting it’s value.  In our example we selected 9.

3, 5, 6, 9, 11, 12, 14

The algorithm then must decide if the number we are searching for is higher or lower then 9.  Since we are searching for 12, the number is higher then 9.  We must search to the right of 9 since we know that if there is a 12 in the list it must be to the right of 9.  We have now reduced the number of items to compare to in half with just 1 comparison! Pretty cool!  This leaves us with the follow numbers to search through.

11, 12, 14

We again select the middle position and compare it to the number we are searching for.  In this case the middle position returns a 12 which happens to be the number we are searching for.  Using the binary search we found our number in an array of 7 items using only 2 comparisons!

The key things to remember about a binary search are that it must have a sort list and it reduces the number of items it has to search through every time it does a comparison.

Coding a Binary Search

Coding a binary search is fairly straight forward.  We take the middle position of the array and compare it to our number.  If our number is higher then the middle position we then use the top half of the list.  If our number is lower we use the lower half of the list.  We then repeat the process till we find the number or run out of numbers to compare.

Here’s an example of a binary search using C#.

public int binarySearch(int[] array, int lower, int upper, int target)
{

    // set -1 to the location in case we don't find it
    int location = -1;    // keep looping till we run out of positions or we find it

    while (lower  array[mid])  // the mid position is less then our target
        {
            lower = mid + 1;
        }
        else  // the mid position is greater then our target
        {
            upper = mid - 1;
        }
    }

return location;

}

One thing you may have noticed is that you could have written the algorithm using recursion instead of using an iterative approach. So, here is another example of the same algorithm using a recursive method rather then an iterative one.

public int binarySearch(int[] array, int lower, int upper, int target)
{
    // get the mid position
    int mid = (lower + upper) / 2;    // does not exist

    if (lower >= upper)
    {
        return -1;
    }

    if (array[mid] == target) // mid position equals the target
    {
        return mid;
    }
    else if (target < array[mid]) // target is less then mid
    {
        return binarySearch(array, lower, mid - 1, target);
    }
    else // target is greater then mid
    {
        return binarySearch(array, mid + 1, upper, target);
    }
}

Performance

One of the greatest things about a binary search is the speed at which it can search through large lists.  For example, if we had a list with 1,000,000 items in it, a binary search could find the item we are searching for in under 20 comparisons!  Of course there is one drawback to the binary search, the list must be sorted.

Since every comparison the binary search performs cuts the number of items we have to search through in half, the binary search runs in logarithmic time or O(logN).

Well, that’s all for now.

– Seth Long

Fisher-Yates Shuffle Algorithm

My blog is now located at http://www.WhoIsSethLong.com

I went to an interview recently and was asked to arrange an array of integers from 1 to 52 in random order.  As soon as they said 52 I thought about a deck of cards, then instantly thought about the Fisher-Yates Shuffle Algorithm.

The Fisher-Yates Shuffle Algorithm is a simple algorithm that runs in linear time and is used to shuffle an array in random order.  The algorithm loops through each item in the array, generates a random number between 0 and the array length, then assigns the array item to the randomly generated array position.  This is a simple algorithm and is probably easiest understood with an example. For this example I’ll use C#.

public void FisherYates(int[] ary)
{
    Random rnd = new Random();

    for (int i = ary.Length - 1; i > 0; i--)
    {
        int r = rnd.Next(0, i);

        int tmp = ary[i];
        ary[i] = ary[r];
        ary[r] = tmp;
    }
}

There are other ways to sort the array besides the Fisher- Yates method.  If this had been a deck of cards, another method would be to assign a randomly generated 64-bit number to each card then sort by their randomly assigned number.

– Seth Long

A Simple Bubble Sort

My blog is now located at http://www.WhoIsSethLong.com

Well, this is my first time writing online so I thought I’d start off with something simple and a bubble sort was the first thing that came to mind.  If you’re not familiar with what a bubble sort is, let me give you a quick rundown.

A bubble sort algorithm is a very simple way to sort a collection but also not a very efficient one.  The algorithm works by comparing 2 items in the collection and swapping them if they are not in the right position.  For example, we are going to sort the following array of numbers from smallest to largest.

6, 3, 8, 2, 5

The algorithm would start by comparing the first two numbers and moving the larger number to the right.

6, 3, 8, 2, 5   ->  3, 6, 8, 2, 5

The algorithm would then move over 1 place and compare the numbers there.

3, 6, 8, 2, 5

Since the larger number is already on the right, the algorithm doesn’t need to make any changes and again moves over to the right 1 position.

3, 6, 8, 2, 5

Now we have the larger number on the left so it will need to be swapped with the smaller number of the right.

3, 6, 8, 2, 5  ->  3, 6, 2, 8, 5

The larger number has been swapped to the right so the algorithm will now move over again and check the last two numbers.

3, 6, 2, 8, 5

Again, the larger number is on the left so it will need to be swapped.  This gives us:

3, 6, 2, 8, 5  ->  3, 6, 2, 5, 8

After the first pass through, we now have the largest number (8) in its proper position.  So now we will start at the beginning of the array again, work our way towards the end and swap numbers as needed.

3, 6, 2, 5, 8
3, 6, 2, 5, 8  ->  3, 2, 6, 5, 8
3, 2, 6, 5, 8  ->  3, 2, 5, 6, 8

Now, you can see that we don’t compare the last number this time.  That’s because we know the last number is already in it’s proper place.  Each run through the array we compare one less number on the right.  The algorithm gets its name because the largest number will bubble up to the last position after each pass.  Our third run through the array would look like this:

3, 2, 5, 6, 8  ->  2, 3, 5, 6, 8
2, 3, 5, 6, 8

Fourth run:

2, 3, 5, 6, 8

That’s definitely a lot of work just to sort 5 numbers.  There are other algorithms out there that are much more efficient then the bubble sort.

Coding the Bubble Sort Algorithm

Now that we hopefully understand how the bubble sort algorithm works, lets look at the code needed to implement it.  All we really need is 2 loops and an if statement to create a bubble sort algorithm.  The first and outer loop will start from the end of the array and work its way to the beginning.  The second and inner loop will start from the beginning of the array and work its way to the value of the outer loop.  Inside the inner loop is an if statement that compares the 2 numbers and swaps them if necessary.   Here is the code using C# syntax:

// the array to sort
int[] ary = new int[] { 6, 3, 8, 2, 5 };

// outer loop
for (int outer = ary.Length - 1; outer > 0; outer--)
{
    // inner loop
    for (int inner = 0; inner  ary[inner + 1])
    {
        // swap them
        int tmp = ary[inner];
        ary[inner] = ary[inner + 1];
        ary[inner + 1] = tmp;
    }
}

There are other variations of this algorithm but this is probably the most common way of coding it.

Efficiency

As I’ve mentioned before, the bubble sort algorithm is one of the worst ways to sort a collection.  To understand why, we need to look at the worst-case complexity of the algorithm.  Since the algorithm uses 2 loops to sort the array, there are a LOT of comparisons and swaps being made.  With an array of n items, the algorithm will make n – 1 comparisons on the first pass.  The next pass will require n – 2 comparisons, etc…  This gives us n(n – 1) / 2 or O(n²).

Well, that’s all for now.  I’ll be posting some more sorting algorithms soon so keep checking back!

– Seth Long