After writing yesterday about the insertion sort algorithm with Python here, today I have decided to continue with the algorithms. Thus, I have decided to take a look at two other simple sorting algorithms – Count Sort and Selection Sort. As far as Python is not the best language, when we talk about productivity and speed, I have decided to switch a little to C# for this subject.
So, working with MonoDevelop was challenging, compared to Visual Studio, but man got used to it, when you are on Ubuntu and Mint as in my case. Anyway, I had an IDE (although a free one) and this was the first time since months, when I was using it 🙂
So, let’s start with the two algorithms. The first one, count sort was really challenging in its simplicity. It is not a greedy algorithm nor a divide and conquer one, but it is the algorithm that is developed by any 5-year-old kid, which is given to sort playing cards (at least this was my way) – you simply put the Aces in the pile of Aces and the Jacks in the pile of Jacks. At the end you pick them in order. Pretty simple, and yet working quite well 🙂
In my code, I have a string for the input, converted to a list and in the first for loop I add values to a dictionary. 700 is a magic number, due to the ASCII table, which goes to 255 (the extended one), but I have decided to enlarge it a little. Later, I assign values to the dictionary from myList and I print every value in the dictionary. And voila, the code works 🙂
Here comes the code for count sort:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
using System; using System.Collections.Generic; using System.Linq; class MainClass { public static void Main () { Console.WriteLine ("Welcome to Count Sort :)"); string sInput = Console.ReadLine (); List<string> myList = sInput.Select (c => c.ToString ()).ToList (); Dictionary<int, int> myDictionary = new Dictionary<int, int> (); for (int i = 0; i < 700; i++) { myDictionary.Add (i, 0); } foreach (string sValue in myList) { myDictionary [(int)Char.Parse (sValue)] ++; } foreach(KeyValuePair<int, int> pair in myDictionary) { if (pair.Value>0) { for (int i = 0; i < pair.Value; i++) { Console.Write("{0}",(char)pair.Key); } } } } } |
Selection sort is considered a simple algorithm any man should be able to write in 5 minutes. If this man is coming from a Math School or similar. 🙂 Anyhow, with a major in Modern Greek language like me, the code takes about 20 minutes to come up, write and test. It could be actually more, if you have to google how to pass string to list in C# (check line 11, it is quite a good decision with linq). Anyway, two embedded loops do the job and give us the complexity of O(n^2). Here comes the code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
using System; using System.Collections.Generic; using System.Linq; class SelectionSort { public static void Main () { Console.WriteLine ("Welcome to Selection Sort"); string sInput = Console.ReadLine (); List myList = sInput.Select (c => c.ToString ()).ToList (); for (int i = 0; i < myList.Count; i++) { int iPosition = i; int iValue = ((int)Char.Parse(myList [i])); for (int z = i; z < myList.Count; z++) { if (iValue > ((int)Char.Parse (myList [z]))) { iValue = ((int)Char.Parse (myList [z])); iPosition = z; } } myList.Insert(i, myList[iPosition]); myList.RemoveAt (iPosition+1); } for (int i = 0; i < myList.Count; i++) { Console.Write(myList[i]); } } } |
Pretty much that is all from today! Enjoy the code! 🙂