Archive for March, 2012

Simple Sorting Algorithms Implementations – Part 1

In the below, I will be presenting java source code of popular sorting algorithms. The problem with so many books I have read is that they don’t provide the simplest of solutions. I always consider myself an Hello World programmer. If I pick a new language, the first thing I look for is hello world, if I pick a concept, the first thing I look for is the simplest implementation, not the most optimized solution. NO. So when I look for implementations of algorithms, even if you are going to present me the most optimized algorithm, let me see the simplest, non-optimized implementation first.

When someone asked me why am I using for example, java.util.logging instead of log4j, I tell them, so far java.util.logging is working and I am yet to see a case I can not easily handle with it. So it is with these algorithms, let the reader/student see the simple solution and then present him with the problems with the simple solution, and then the optimized, more difficult to implement solution. If he likes, he can go with the simple implementation, when he finally discovered the problems with the simple implementation himself, it will be easier to understand the complex ones.

The programs below are very simple. Non of them have been optimized, they are meant to introduce to you these algorithms. You can take the code and optimize all you want. I also take care to use only simple data structures, no Lists, or Sets or any class in the collections package.

The below code are just segments of the full code. The important segments. The full source code is publicly hosted on Github

Finally if you want to read-up on these algorithms, please head to wikipedia
BUBBLE SORT

The algorithm below is based on the assumption that after every run through the array, the last element is already sorted.

So
for run1, the nth element is sorted,
for run2, the n-1th element is sorted,
for run3, the n-2th element is sorted, etc

	public void sortList(int n) {
		boolean swapped = true;
		while(swapped) {
			swapped = false;
			for(int i = 1; i < n; i++) {
				if (toSort[i] < toSort[i - 1]) {
					swap(i, i - 1);
					swapped = true;
				}
			}
			printArray();
			n = n -1;
		}
	}

INSERTION

	public void algorithm() {
		for(int i = 1; i < toSort.length; i++) {
			int key = toSort[i];
			int k = i - 1;
			while(k >= 0 && toSort[k] > key) {
				toSort[k + 1] = toSort[k];
				k--;
			}
			toSort[k + 1] = key;
		}
	}

SELECTION

	private void sortList(int startIndex) {
		int minIndex = findMinimum(startIndex);
		if(minIndex != startIndex) {
			//swap
			int temp = toSort[minIndex];
			toSort[minIndex] = toSort[startIndex];
			toSort[startIndex] = temp;
		}
		startIndex++;
		if(startIndex < toSort.length) {
			//recursively call sortList
			sortList(startIndex);
		}
	}

	public int findMinimum(int startIndex) {
		int min = toSort[startIndex];
		int minIndex = startIndex;

		for(int i = (startIndex + 1); i < toSort.length; i++) {
			if(min > toSort[i]) {
				min = toSort[i];
				minIndex = i;
			}
		}
		return minIndex;
	}

In the Part 2 of this post, I will show codes for MergeSort, QuickSort and HeapSort.

Source Code: Github

Comments (1)

Codename One Dynamic Ads Component

Codename One (CN1) really took off with a blast. Although still in beta, but loads of people are already using it for various apps, from banking to a mobile front for this. What is commendable is the ease with with you can build mobile apps that are truly cross platform without having to install tools for each platform.

If you are still wondering what CN1 is, please head to CN1 Website and read up about it for yourself.

I am going to be doing a series of tutorials or useful code snippets for CN1. Today we are looking at the ads component.

To use codename one ads, you need to register and have an account on inner active

Here are the steps to getting your ads on your CN1 app

  1. Create an account on inner active
  2. After login in, click the Add App tab and provide details for your app. The trick is to create different apps for different platforms so that inner active don’t go displaying a download app link on the appstore to blackberry users. You can also profile by age group and/or location.
  3. For every App you added like this, inner active will generate a unique key for you. Key this key.
  4. Now in your code, create an hash table that holds all the keys mapped to the specific platform and populate it. Then write a method as in below to add the ads component to the form.
    public static final Hashtable adKeys = new Hashtable();
    .............
    adKeys.put("rim", "[inner_active_rim_ad_key]);
    adKeys.put("and", "[inner_active_android_ad_key]");
    adKeys.put("me", "[inner_active_others_ad_key]]");
    ......................
    public static void showAds(Form f) {
        Ads ads = new Ads(adKeys.get(Display.getInstance().getPlatformName()).toString());
        if (!f.contains(ads)) {
            f.addComponent(BorderLayout.NORTH, ads);
        }
    }

Now for every page where I want to show the ad, I just call the above method and pass the form instance. Notice however that all my forms are BorderLayout and the North part is reserved for ads.

If you want to however use any type of layout other than border layout, you can use this code to add the ads component to the top of the page

Ads ads = new Ads(Helpers.adKeys.get(Display.getInstance().getPlatformName()).toString());
if (!f.contains(ads)) {
f.addComponent(0, ads);
}

That’s it, you now have Ads. You can visit your inneractive dashboard to see how your App is doing.

Comments (6)