## 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

Advertisements

## 2 Comments »

1. ### javamylovesaid

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. .

2. ### andriansaid

Hi, thank you for the post. It was very interesting to read.