Inheritance
My blog is now located at http://www.WhoIsSethLong.com
A good friend of mine called me up the other day and said he was getting back into programming after being away from it for many years. He was having a hard time understand the concept of inheritance and asked me for a really easy to understand example. So here it is…
The easiest way to understand inheritance is to think about your parents. Ok, I know you’re wondering what thinking about your parents has to do with programming but let me explain. You are a unique individual yet you share many of the same features as your parents. You inherited those features from you parents and combined them with your own features, creating a new and unique individual. Well, inheritance in programming isn’t much different. You create a new class that inherits the properties and methods of another class.
For this example, we will have a class named AlcoholicBeverage. In case you didn’t know, all alcoholic beverages contain alcohol and have a “proof”. So, we’ll add the properties “Proof” and “AlcoholPercent” to the AlcoholicBeverage class. This class will act as the “parent” for our future beer and wine classes.
class AlcoholicBeverage
{
protected double _PercentAlcohol;
public double Proof
{
get { return (_PercentAlcohol * 2); }
set { _PercentAlcohol = (value / 2); }
}
public double PercentAlcohol
{
get { return _PercentAlcohol; }
set { _PercentAlcohol = value; }
}
}
Next, we will create our beer and wine class which will inherit from the AlcoholicBeverage class. A beer and a glass of wine both have a percentage of alcohol and a proof but we will not need to add them to our beer and wine classes since they are already defined in the base AlcoholicBeverage class.
class Beer : AlcoholicBeverage
{
public Beer()
{
PercentAlcohol = 2.5;
}
}
class Wine : AlcoholicBeverage
{
public Wine()
{
PercentAlcohol = 12;
} }
Now we can create our new beer and wine classes and check their Proof.
Beer bottleOfBeer = new Beer();
Console.WriteLine(bottleOfBeer.Proof.ToString());
Wine glassOfWine = new Wine();
Console.WriteLine(glassOfWine.Proof.ToString());
When run, it gives the following output:
5
24
This is a really simple example of inheritance. Hopefully it’s simple enough for everyone to understand. Well, that’s all for now!
– Seth Long
Coupling and Cohesion
My blog is now located at http://www.WhoIsSethLong.com
One of my biggest pet peeves as a programmer are other programmers who create giant “do all” general classes rather then creating a few smaller specialized classes. So, I thought it would be a good idea to write a little bit about the Object Oriented principles of Coupling and Cohesion that deal specifically with this issue.
Coupling refers to how tightly different classes are connected to one another. Tightly coupled classes contain a high number of interactions and dependencies. Loosely coupled classes are the opposite in that their dependencies on one another are kept to a minimum and instead rely on the well defined public interfaces of each other
Ok, I know it’s hard to understand coupling if you’ve never heard about it before, so I think the best way to explain it is with an example. I read a great description of coupling a while back that I’m going to share here. I think it will really help people better understand the concept of coupling. It was in a reply post on the Sun Developer’s Network forums and just does a great job of describing coupling in easy to understand terms.
Legos, the toys that SNAP together would be considered loosely coupled because you can just snap the pieces together and build whatever system you want to. However, a jigsaw puzzle has pieces that are TIGHTLY coupled. You can’t take a piece from one jigsaw puzzle (system) and snap it into a different puzzle, because the system (puzzle) is very dependent on the very specific pieces that were built specific to that particular “design”. The legos are built in a more generic fashion so that they can be used in your Lego House, or in my Lego Alien Man.
The code example below shows two very simple classes that are tightly coupled to one another. It was inspired by actual code from the Ektron CMS my previous employer so dearly loved. It is not the actual code but is in the exact same format.
class TightCoupling { public void ShowWelcomeMsg(string type) { switch (type) { case “GM”: Console.WriteLine(“Good Morning”); break; case “GE”: Console.WriteLine(“Good Evening”); break; case “GN”: Console.WriteLine(“Good Night”); break; } } } class TightCoupling2 { public TightCoupling2() { TightCoupling example = new TightCoupling(); example.ShowWelcomeMsg(“GE”); } }In the above example, the ShowWelcomeMsg function can not be called without knowing the inner-workings of that function making it nearly useless for other systems. Secondly, if another developer in the future decides to change the switch statement in the ShowWelcomeMsg function, it could inadvertently effect other classes that call that function.
It shouldn’t be too hard to see that loosely coupled classes offer much greater code reuse and flexibility then tightly coupled classes. Any changes to tightly coupled classes run the high risk of inadvertently effecting other classes and their dependence on other specific classes making them worthless outside the system they are in. With loosely coupled classes we use well defined public interfaces. This give us the flexibility to modify the internals of the class in the future without effecting other classes and allow us to reuse the code in other systems. So, next time you are writing a class, think to yourself: Am I writing a Lego or am I writing a puzzle piece?
Cohesion is often mentioned with Coupling since they usually go hand-in-hand. Cohesion refers to how closely related methods and class level variables are in a class. A class with high cohesion would be one where all the methods and class level variables are used together to accomplish a specific task. On the other end, a class with low cohesion is one where functions are randomly inserted into a class and used to accomplish a variety of different tasks. Generally tight coupling gives low cohesion and loose coupling gives high cohesion.
The code below is of an EmailMessage class that has high cohesion. All of the methods and class level variables are very closely related and work together to accomplish a single task.
class EmailMessage { private string sendTo; private string subject; private string message; public EmailMessage(string to, string subject, string message) { this.sendTo = to; this.subject = subject; this.message = message; } public void SendMessage() { // send message using sendTo, subject and message } }Now here is an example of the same class but this time as a low cohesive class. This class was originally designed to send an email message but sometime in the future the user needed to be logged in to send an email so the Login method was added to the EmailMessage class.
class EmailMessage { private string sendTo; private string subject; private string message; private string username; public EmailMessage(string to, string subject, string message) { this.sendTo = to; this.subject = subject; this.message = message; } public void SendMessage() { // send message using sendTo, subject and message } public void Login(string username, string password) { this.username = username; // code to login } }The Login method and username class variable really have nothing to do with the EmailMessage class and its main purpose. This class now has low cohesion and is probably not a good example to follow.
So that’s a brief overview of Coupling and Cohesion. Remember, if you want easy to maintain and reusable code, stick to loose coupling and high cohesion in your objects. I should also mention that there are times where tight coupling is desirable but it’s rare that I’ll leave that up to you to read more about on your own. Also, I really recommend reading up on Cohesion and Coupling on Wikipedia. They have a lot more detail and information there then what I’ve written here.
– Seth Long
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
Ternary Search Tree in C#
My blog is now located at http://www.WhoIsSethLong.com
I recently had the urge to create a Ternary Search Tree in C# (doesn’t everyone get these urges?). My first stop was at http://www.ddj.com/windows/184410528 for a GREAT article on how Ternary Search Trees work and how to create them. If you’re really unfamiliar with Ternary Search Trees, I’d recommend starting with the wikipedia article on them before reading this.
For this project, I began by creating a class called TSTree and another called TSNode. The TSNode class is a very simple class that simply contains properties for the split char, low node, equal node and hi node (later we will add a value). Here is an example of the TSNode class:
class TSNode { private char splitChar; private TSNode lowNode; private TSNode eqNode; private TSNode hiNode; private object value; public char SplitChar { get { return this.splitChar; } set { this.splitChar = value; } } public TSNode LowNode { get { return this.lowNode; } set { this.lowNode = value; } } public TSNode EqNode { get { return this.eqNode; } set { this.eqNode = value; } } public TSNode HiNode { get { return this.hiNode; } set { this.hiNode = value; } } public object Value { get { return this.value; } set { this.value = value; } } }Later on we can add more to the class but for now that is a good start. So lets briefly go over what it all does. The first property SplitChar holds the char that this node represents. The LowNode holds a reference to a node that holds a SplitChar that is less then the value of this Node, HiNode holds a reference to a node that holds a SplitChar that is greater then the value of this Node and of course EqNode holds a reference to a node that has a SplitChar that is equal. Pretty much like a binary tree node but with a reference to an equal node added (Binary = 2, Ternary = 3).
The next step is to add an Add method to the TSTree class. What the Add method is going to do is add a node for each char in a string to the tree. For example, if we have an empty tree and add the key “cat” to it, it will add nodes for ‘c’, ‘a’, and ‘t’ to the tree. Since our word is “cat”, the root node will have a SplitChar value of ‘c’. In it’s EqNode property it will contain a reference to another node with a SplitChar value of ‘a’. This node will also contain a EqNode reference to another node with a SplitChar value of ‘t’. So we have three nodes in our tree whos collective SplitChar values spell out “cat”.
Here is the code for the Add method:
public TSNode Add(TSNode p, string s, int pos, object value) { if (p == null) { p = new TSNode(); p.SplitChar = s[pos]; } if (s[pos] < p.SplitChar) { p.LowNode = Add(p.LowNode, s, pos, value); } else if (s[pos] == p.SplitChar) { if (pos < s.Length – 1) { p.EqNode = Add(p.EqNode, s, ++pos, value); } else { p.Value = value; } } else { p.HiNode = Add(p.HiNode, s, pos, value); } return p; }Now, when we want to add another word things get interesting. So, lets add the word “cab” to our tree and see what happens next. We start by looking at the root node in our tree and see that ‘c’ matches the first letter in our word “cab”. Since it matches, we follow the EqNode reference and check the next SplitChar value. In this case it is ‘a’, which again matches the next char in our word “cab”. Again, we follow the EqNode reference and check the next SplitChar value. This time, the value of the SplitChar does not equal the last value of our word. So we have to check if the SplitChar value is greater then or less then the value of ‘b’. ‘b’ is less then the value of ‘t’ so we will follow the path of the LoNode. In this example the LoNode value is null so we create another node and set its SplitChar value to ‘b’. That’s how we add items to the tree.
Searching for a string in our tree is going to work a lot like adding an item to it. If we were searching for the word “cab” in the previous tree we created, we would start by checking the root node’s SplitChar value and compairing it to the value of the first char in our search word. In this case the ‘c’ in our search word matches the SplitChar value of the root node. So we follow the reference in the EqNode property to the next node. The next node contains a SplitChar value of ‘a’ and again matches the second char in our search word of “cab”. Again, we follow the EqNode reference to the next node and check the SplitChar value. This time they are not equal so we then determine if ‘b’ is greater then or less then the ‘t’ that is stored in the SplitChar value. ‘b’ is less then ‘t’ so we take the LoNode to the next node. This node contains a SplitChar value of ‘b’ so we have found our match! Here is the code for the search:
public object Search(string s) { TSNode p = root; int x = 0; while (p != null) { if (s[x] < p.SplitChar) { p = p.LowNode; } else if (s[x] == p.SplitChar) { x++; if (x == s.Length && p.Value != null) { return p.Value; } p = p.EqNode; } else { p = p.HiNode; } } return null; }So those are the major methods of a Ternary Search Tree. I will post the complete code up here shortly. It’s also important to remember that even though a Ternary Search Tree is similar in use to other key-value type data structures it does have some major differences. First, the key MUST be a string. Second, the Ternary Search Tree has the ability to return partial matches and even similar matches. Very Cool!
– 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(n2) 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; } }Understanding a SQL Junction Table
My blog is now located at http://www.WhoIsSethLong.com
I was recently asked about a sql junction table and thought I’d share my thoughts about them with the few people who read this. First off, I am NOT a DBA. So, if something is not correct or accurate please feel free to correct me.
Junction tables are used when dealing with many-to-many relationships in a SQL database. If you’re wondering what exactly a many-to-many relationship is, let me try to briefly explain. Suppose we are working at a school and have a table full of student names and another table full of classrooms. Each of the students can belong to multiple classrooms or none at all. Likewise, each classroom can have multiple students or none at all. This is an example of a many-to-many relationship.
A junction table will allow us to create the many-to-many relationship and most importantly, let us keep from adding duplicate entries as you’ll soon see.
To start, lets create a student table and a classroom table.
CREATE TABLE Students
(
StudentID int IDENTITY(1,1) PRIMARY KEY,
StudentName nchar(50) NOT NULL
)
CREATE TABLE Classrooms
(
ClassroomID int IDENTITY(1,1) PRIMARY KEY,
RoomNumber int NOT NULL
)
Now that we have our two tables created we need to create the junction table that will link them together. The junction table is created by using the primary key from the Classrooms and Students tables.
CREATE TABLE StudentClassroom
(
StudentID int NOT NULL,
ClassroomID int NOT NULL,
CONSTRAINT PK_StudentClassroom PRIMARY KEY
(
StudentID,
ClassroomID
),
FOREIGN KEY (StudentID) REFERENCES Students (StudentID),
FOREIGN KEY (ClassroomID) REFERENCES Classrooms (ClassroomID)
)
We have now created a table with columns for the StudentID and the ClassroomID. This table also uses a combination of these two columns as the primary key. This means that each student-classroom pair is unique. Each student can belong to many classrooms, each classroom can belong to many students but each pair can only occur once.
You should also note that the columns in the junction table are setup as foreign keys to the Students and Classrooms tables. This is important as it keeps us from adding students to a classroom that doesn’t exist or deleting a classroom from the database if there are still students belonging to it.
To see what students belong to what classrooms we can use the junction table and the following query:
SELECT StudentName, RoomNumber FROM StudentClassroom JOIN Students ON Students.StudentID = StudentClassroom.StudentID JOIN Classrooms ON Classrooms.ClassroomID = StudentClassroom.ClassroomID
So, that’s a junction table in a nut shell.
– Seth Long
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
Nonrepeated Character Search
My blog is now located at http://www.WhoIsSethLong.com
This code challenge was inspired by a book I recently read. The book is called Programming Interviews Exposed: Secrets To Landing Your Next Job. It’s a great book full of those fun technical questions you get asked during programming job interviews.
For this challenge, you will need to create a function/class/algorithm that takes a string and finds the first non-repeated character. For example, in the word reaper the first non-repeated character is ‘a’. The character ‘p’ is also not repeated but we are looking for the first one.
There are multiple ways to accomplish this but I’m going to only post 1 here. To start, I first created a hash table with all the chars in the string and incremented each char as additional matches are found. So for example, in the string reaper I will start with the char ‘r’ and add that to the hashtable and give it a value of 1. Next I will add ‘e’ to the hash table and give it a value of 1. The char ‘p’ will get a value of 1 but the next char, ‘e’, already exists in the hashtable so we will increment it by 1 and it’s value becomes 2. This is done for all the chars in the string.
Once this is done, we then read back over the string, comparing each char in the string to the hashtable till we find the first char that has a value of 1. I know, it sounds a little confusing but if you read of the code sample it will make a lot more sense.
Here is a code sample in C#:
public char NonRepeatedChar(string s) { Hashtable ht = new Hashtable(); // loop through each char in string // and add to hashtable for (int x = 0; x < s.Length; x++) { char c = s[x]; if (ht.ContainsKey(c)) { // already exists in hashtable so // give it a value of 2. ht[c] = 2; } else { // does not already exist so give // an initial value of 1 ht.Add(c, 1); } } // loop through the string again and // find the FIRST match in the hashtable // that has a value of 1 and return it. for (int x = 0; x < s.Length; x++) { char c = s[x]; // check if the char’s value is 1 if ((int)ht[c] == 1) { return c; } } // no match found return ”; }Well, that’s all for now!
(I just noticed the return value for the above code isn’t showing up. It’s just a null char.)
– 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(n2).
Well, that’s all for now. I’ll be posting some more sorting algorithms soon so keep checking back!
– Seth Long
About
Hello, my name is Seth Long and I’m a Senior Software Engineer for SpeedDate.com in the San Francisco Bay Area.
I can be reached at sincityseth@gmail.com. For more information about me, visit my website at http://www.WhoIsSethLong.com
-
Archives
- May 2008 (1)
- February 2008 (3)
- January 2008 (6)
-
Categories
-
RSS
Entries RSS
Comments RSS
Coding Notes 