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!

The BBCâ€™s technology correspondent Rory Cellan-Jones gets a beer poured for him by a robotic barman - but how long does it take?

US politicians have voted to let ISPs gather and sell data about what Americans do online.

Customers who suffer poor service could get automatic payouts under Ofcom's plan.