coding
A Generic Implementation of Counting Sort
What is “Counting Sort”?
Counting Sort is a super fast sort algorithm that only works for certain types of data.
- It is only useful if you have a relatively small range of values to sort
- Even if there you have a large number of items to sort
For example, if you have a large list of “Person” objects, and each Person has an age between 1 and 100, then counting sort would be useful. Because what you are sorting on, age, has a relatively small range. The ages are repeated a lot, i.e. you will probably have a lot of Persons with age=18, a lot with age=65, etc.
For a counter example, assume each Person has a social security number; this would not be good use for Counting Sort, because there shouldn’t be any repeated SSNs.
Algorithm Speed
- Counting Sort runs in O(n) (refer to Big O Notation for an explanation)
- Which is superior to most other sorts, which run in O(n ∙ ln(n)) time
Counting Sort is only necessary in a special situations where you have need maximum efficiency, typically big data sets or other situations where you sort a lot.
Concepts Covered in this Post
- Counting Sort
- Generic Methods
- Extension Methods
- C# delegates using ‘Func’ declaration
First, The Code, Then The Explanation
using System;
using System.Collections.Generic;
namespace CountingSortExample {
public static class CountingSortExt {
public static IList<T> CountingSort<T>(this IList<T> sortMe,
Func<T, int> sortProp) {
List<int> buckets = new List<int>();
for (int i = 0; i < sortMe.Count; i++) {
int theVal = sortProp(sortMe[i]);
//Increase the bucket size, if necessary
for (int j = buckets.Count; j <= theVal; j++)
buckets.Add(0);
buckets[theVal]++;
}
int[] startIndex = new int[buckets.Count];
for (int j = 1; j < startIndex.Length; j++) {
startIndex[j] = buckets[j-1] + startIndex[j-1];
}
T[] result = new T[sortMe.Count];
for (int i = 0; i < sortMe.Count; i++) {
int theVal = sortProp(sortMe[i]);
int destIndex = startIndex[theVal]++;
result[destIndex] = sortMe[i];
}
return result;
}
}
}
Usage
List<Person> _PersonList; //List populated elsewhere //Now do the work: IList<Person> sorted = _PersonList.CountingSort(p => p.Age);
Notes on Generic Aspects of My Implementation
- public static class CountingSortExt – This is an extension method, so it must be a static class
- Using an extension method allows the syntax immediately above, i.e. _Personlist.CountingSort…
- public static IList<T> CountingSort – Static again because it is an extension method
- T is a placeholder for the class type being sorted
- Func<T, int> sortProp – an anonymous function that allows the caller to specify the field used to perform the sort with
- When you invoke it, it will look like this: p => p.Age
- Which means “Use the age field for sorting”
Brief Discussion of the Algorithm
Counting sort works by:
- Counting how many there are of each age. There is one person with age 7, seven persons with age 18, two persons with age 21 and five persons with age 65.
- We can use the counts to compute the destination index to move each person to
- For example, since there is only one seven-year-old, we know to move the first eighteen-year-old into slot 2.
Another Example
Because I implemented my method as a generic method, you can sort anything that has an int property, such as sorting a list of strings by length. You simply need to pass a lambda expression indicating the field/property to sort on, such as a string length property, as shown in the sample below:
List<string> stringList = new List {
"adsf",
"adsfl;jkadsf",
"qwerp9oui",
"a",
";ljsdfqweroiusd",
"zcxv,mnzxcvnm,k"
};
IList<string> sortedString = stringList.CountingSort(w => w.Length);
foreach(string s in sortedString)
Console.WriteLine(s);
Potential Modification
Note that my code works well when the field/property being sorted is close to 0. If that is not the case for you, you could replace my list ‘Buckets’ with a dictionary, or other type of hash list. Otherwise, if you have high values for the sorting field/property, you will allocate a large amount of memory for Buckets.
Download the Code
You can download my code from my DropBox account; they will ask you to set-up a free account for the privilege of downloading it.
Earn the Big Bucks By Learning New Job Skills Smartly
You’re smart, you love to code. You frequently learn new skills, because it’s fun and useful. But are you learning skills that employers want? Are you sure that, if your job loses stability, you can find a new one? Your favorite language may be cool – lots of skills are also cool – but wouldn’t you like to have job security as well as write cool code?
Or maybe you’re that guy who picked-up FoxPro years ago and hasn’t learned anything new since. Now your company wants to upgrade its technology; do you have alternatives? Or are you going to live in your car while you try to learn Android? All your peers learned new skills; maybe you should do the same now!
What You Can Learn Reading this Post
You can avoid sleeping in your car by intelligently analyzing the coding skills in demand now. After reading this article, you’ll be prepared to analyze the skills market and be smart about which new skills you learn!
So here are some things you can learn from this post:
- Make sure your skills are strong enough to look for a new job, or negotiate a better salary.
- Update your resume; use the right buzzwords to reflect your hard-earned knowledge. HR departments sometimes use bots to scan resumes – they don’t understand that, if you write code in C#, then you already know .NET!
- And what about learning a new, rare skill that pays high – can you pick that skill?
- You can use my free, easy to use, open source app to analyze what skills are in demand
I Doubled My Salary By Learning Skills in Demand
Quick story… Years ago, I was a mainframe programmer, and I could tell that my mainframe skills were rapidly becoming unmarketable. I was pretty underpaid to boot. My employers didn’t really treat me very well, and I didn’t have a lot of options with my current skill set. I took matters onto my own hands; having read “What Color is Your Parachute”, I took classes in VB, Java and C++. Then I begged to write my next work project in any of those new skills. They let me write my project in VB and tada! Now I had the skill and the experience. Shortly after finishing that project, I was able to switch jobs and double my salary, on the strength of my new skill!
Years later, I’m still doing fine, but I still want to list attractive skills on my resume, so I wrote a program to scrape data from the web and actually measure what the employers are looking for. Then I looked at the results and realized that I haven’t made the best choices about picking new technologies to learn. For fun, I thought I’d share what I learned with you. Maybe you can double your salary, or else avoid getting laid-off with no current skills.
Chances are you’re pretty smart… when it comes to maximizing your employer’s profit. But are you being smart on your own behalf? We programmers like to brag we are logic experts, capable of hard work. If you ever told someone you’re good at logic, and work like a slave, why don’t you prove it by logically analyzing your skills and working just a little to choose your new skills, for your own career!
I Wrote a Screen-Scraper/Analysis Program for Careers 2.0 (StackOverflow)
StackOverflow has a nice jobs board that displays only programming jobs. That made it easier to grab their data; it was also easier because they prominently display the major skills as searchable tags. I was able to get some real-world data and accurately dissect it!
My program grabs data from their site and analyze the approximately 700 jobs they have listed there. I posted my code on CodePlex at https://visualizejobskills.codeplex.com/releases/view/122002; you can download it free and run it yourself. The results could change your life.
When I first ran my program, the first thing I checked were the skills most in demand. Holy cow, Java Script is beating everyone these days! jQquery also surprised me with a #4 ranking, I had no idea they were so popular. I sure am glad I spent the time to learn those two! In fact, I know 6 of the top 10 skills pretty strongly; that’s the good news.
Some of my Skills Aren’t too Popular
But now for the bad news: lately I’ve been writing a lot of WPF with MVVM, using Test-Driven Development (TDD), and learning Rx (Rx == “Reactive Extensions”, a cool multi-threading API from Microsoft). If you download my Tag Analysis app from CodePlex, you’ll see exactly what I’m talking about. I searched for the rankings for these skills and was disappointed: WPF is #62, MVVM is #196; Rx is not even listed. At least TDD came in at #45.
You should do the same thing: get out your resume, look at your major skills, see how they rank with employers. Then check the skills you think are cool and might learn: do employers want them too?
Bottom line: I know some cool stuff, but not all of it is demanded right now. True, Stack Overflow is only a small sample (approx 700 jobs), but that does not disqualify it. I tend to think of Stack Overflow as the avaunt guard programmers. So while the data is not conclusive, but nonetheless highly indicative.
What Skills Should You Learn?
So, what should you be learning for new skills? Based on popularity and compatibility with my current skills, plus an idea of how hard they are to learn, I’d guess I personally should start looking at CSS3, node.js or AngularJs. The upside is that they are easy to learn and piggy-back on skills I already have. You should consider the same idea, i.e. build on what you know. Also, when picking a new skill, take a peak at what related skills employers seek.
But, maybe we should try to pick a rare skill that is hard to fill, in hopes of commanding a higher rate!
Identify Rare Skills that Pay Better
According to the law of Supply and Demand, rare skills command a higher rate than common skills. Based on the data available on Stack Overflow, I picked 3 measures of rareness:
- Posting Age. The longer the job has been listed, the more desperate the employer is to fill it. Some skills may, on average, be posted longer than others, implying scarcity.
- Percent remote work allowed per skill. Employers prefer to have you on site. But if they can’t find someone local, they’ll reluctantly relax their standards and hire remote workers. The more they need it, the more likely to allow remote, thus the more pressure to pay top dollar to whomever they can find.
- Average # other skills listed. Imagine the bosses having this conversation: “Hey Bob, this project will die if we don’t get an Erlang coder, we can’t find anyone. I don’t care if they don’t know TCP/IP or Linux, Rajiv can teach them
that. Just find me an Erlang guy! Write-up the ad without any other requirements than Erlang.” As it turned-out, there doesn’t seem to be much variation in the counts, so perhaps this measure is less powerful than I anticipated, it is definitely useful, but less than I wished.
Looking at my screen shot, if I knew Ruby-On-Rails, I’d be feeling pretty good right now. It scores well for both % remote allowed and Avg. job age. The following other skills looked good to me, based on my measures of scarcity:
- GWT (presumably not the Global War on Terror, but Google Web Toolkit) – I already have some experience with the Google Maps API, and GWT scores well for % remote and average age.
- NoSql, Cassandra – I’m already pretty darn good at SQL, that means there should be less new material for me
- Amazon web services (probably not a good match for my skill set)
Are you Listing the Correct Buzzwords in Your Resume?
As I mentioned above, the HR departments (and their bots) don’t understand the skills their internal customers seek. For example, they don’t understand that, if you practice TDD, you also practice automated testing! Here are some tags I didn’t realize were in demand, but which I am adding to my own resume because I already know them:
- Performance analysis (I’ve worked with the .NET profiler)
- jQuery-UI
- Design patterns
- Automated testing, unit-testing, e-commerce, Web applications
- Model-View-Controller (Since I practice MVVM, I also practice MVC)
- OOP
- Active Directory – I thought it was too simple to list!
- http – I can’t believe this is a tag, but I’d hate to miss a job for lacking it
- Scripting – who writes these ads? It’s ranked #205
You should download my app and scrutinize the list of job tags. Make sure you list all common synonyms on your resume so HR won’t reject your resume before the IT folks see it.
What’s Your Plan for Success?
Don’t go randomly buying computer books based on hunches. Use your professional logic skills to strategically pick new skills to bolster your resume; see if you can learn something new that is not only cool, but also in demand. Why don’t you download my project and analyze the data yourself?
Randy's Rants, Ravings and Reflections 