Programming Problems - Sorting Algorithms

In early 2000 I used to consult for several software companies. I noticed that though the young software engineers were smart, their grip on the Computer Science fundamentals was not thorough and strong. I decided to train them by making them solve one programming problem after another. "Data Structures & Algorithms" has remained a favorite subject of mine and has caught my fascination. All the problems I used for the training are related to that subject.

I have decided to share those problems in this blog site for the benefit of those interested in excelling in Computer Science. These exercises are not be all and end all but for any sincere seeker of knowledge, they should generate enough interest and should definitely help strengthen the design and programming skills. After these exercises, one should continue pursuing the subject by looking for problems and articles from various other sources.

For most of the exercises, I had also coded the solution in Java and I have posted my sources in a public repository hosted on GitHub. For every exercise, I shall provide a link to my implementation. Please feel free to post your comments on my implementation if you notice any mistake or inefficiency or any possible improvements.

As a warm-up for this training, our first exercise is to understand the various Sorting Algorithms which are nicely illustrated by these Sorting Algorithm Animations.

Here is the first exercise.

Sorter

Implement a class called Sorter which has the following four public methods.

public void doBubbleSort(int a[]);
public void doSelectionSort(int a[])’
public void doInsertionSort(int a[]);
public void doQuickSort(int a[]);

Though the normal running time of Bubble Sort is O(n*n), some of the important points that are overlooked while implementing it are

1. If the array is already sorted, then the algorithm should exit after just one iteration.
2. During any of the iterations if no swap happens then the algorithm should exit.
3. During an iteration, the point at which the last swap happens should be noted and the next iteration need not examine the array elements beyond the last swap index.

I strongly urge the readers to make a sincere attempt in implementing the solution. I am providing my implementation so that you can compare it with yours. Looking straightaway at my solution may not be as helpful as making a physical attempt to solve the problem even if your solution is incomplete or not perfect.

You could also carry your source code in a public repository hosted on GitHub and if you prefer you could share the link to your source code in the comment section so that other readers could take a look at it and provide their comments.

Please provide your support and express your encouragement by using the social buttons provided below and share this effort with others.

Here is my implementation.