Programming Tutorials and Interview Questions

- Implement Selection Sort Algorithm in Java
- Java Program Code for Selection Sort
- Pros and Cons of Selection Sort
- Analysis of Selection Sort
- References

Before implementing Java program for selection sort let's first see how selection sort functions to sort array elements in either ascending or descending order. *Selection sort* improves a little on the bubble sort by reducing the number of swaps necessary from *O(N ^{2})* to

Developing Java code for selection sort is quite easy. The idea upon *selection sort* works is simple; a *selection sort* selects the element with the lowest value and exchanges it with the first element. Then, from the remaining `N-1`

elements, the element with the smallest key is found and exchanged with the second element, and so forth. The exchanges continue till the last two elements. Following program develops a class `SelectionSort`

containing a static generic method `selectionSort`

. Note that Java provides the `java.util.Comparable`

interface that contains a single method, `compareTo`

. Any class that correctly implements this interface guarantees a total ordering of its instances.

class SelectionSort { public static <T extends Comparable<T>> void selectionSort (T[] list, int size) { int outCounter, inCounter, minIndex; T temp; // swapOccurred helps to stop iterating if the array gets sorted before // outCounter reaches to size for (outCounter = 0; outCounter < size - 1; outCounter++) { minIndex = outCounter; for (inCounter = outCounter + 1; inCounter < size; inCounter++) { if (list[minIndex].compareTo(list[inCounter]) > 0) minIndex = inCounter; } //swap items if (minIndex != outCounter) { temp = list[minIndex]; list[minIndex] = list[outCounter]; list[outCounter] = temp; } } } } public class SelectionSortDemo { public static void main (String[] args) { Integer arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; SelectionSort.selectionSort(arr, arr.length); System.out.println("Sorted Array: "); for(Integer i : arr) System.out.println(i); } } OUTPUT ====== Sorted Array: 1 2 3 4 5 6 7 8 9 10

In above implementation we test a condition `minIndex != outCounter`

before swapping elements just to save unessential swaps. If `minIndex`

remains equal to `outCounter`

, then the element pointed by `minIndex`

is the smallest and no swap is required.

Simplicity is the main benefit of using *selection sort*. It is an algorithm that is easy to understand and implement. On the downside, *selection sort* is very inefficient at sorting lists containing large quantities of data. It has an algorithmic complexity of *O(N ^{2})*.

For large values of `N`

, the comparison times dominate, so we would have to say that the *selection sort* runs in *O(N ^{2})* time, just as the bubble sort does. However,

`N`

(input size) the
In this tutorial we discussed *selection sort*. We implemented selection sort algorithm in Java. *Selection sort* is among the basic and the slowest sorting techniques. Hope you have enjoyed reading this tutorial. Please do write us if you have any suggestion/comment or come across any error on this page. Thanks for reading!

Developers launch a new app to help pregnant women get a seat on public transport while commuting.

The firm says neither software nor hardware, other than the batteries, were at fault in Note 7.

China is cracking down on the hi-tech ways citizens avoid official scrutiny of what they do online.