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

About these ads

1 Comment »

  1. javamylove said

    Nice read. . . and its so simple and straight forward to read and understand. I preach simplicity myself. . .It’s very easy for newbies to get discouraged when they hear about frameworks. . .log4j…SLF4J..etc….. the com.sun or javax.swing packages in most cases, have all you need. .

RSS feed for comments on this post · TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 203 other followers

%d bloggers like this: