The Java selection sort finds the smallest item in a list and moves that value to the start of the list. This happens repeatedly until every element in the first list has been sorted. The selection sort returns the sorted list.
How do you sort a list in Java? You’ve got a few options. One common option is the selection sort.
In this guide, we’re going to talk about what selection sorts are and how they work. We’ll also walk through how to build a selection sort in Java so that you’ll know how to build your own. Let’s get started!
What is a Java Selection Sort?
A selection sort repeatedly finds the minimum item in a list and moves it to the beginning of the unsorted items in the list. This process repeats for every item in a list until the list is ordered.
The first item in the list is considered to be the smallest item. This item is compared with the next element. If the next element is smaller, the elements swap. This algorithm finds the minimum element until the last element is reached. Then, our program moves the smallest item to the start of the list.
In a selection sort, a list contains two parts: the sorted list and the unsorted list. As elements are sorted, they move from the unsorted subarray to the sorted subarray.
You can order a list in either ascending or descending order.
When Should You Use a Selection Sort?
Selection sorts are optimal when you need to sort a small list. This is because there are more efficient ways of sorting large lists. Algorithms, such as a merge sort, an insertion sort, and a quick sort, are more efficient than a selection sort in Java programming.
A selection sort performs best when checking all the elements of the array is mandatory. This would be the case if few or none of the items in a list are sorted. Selection sorts usually outperform a bubble sort, which is easier to understand.
How do Selection Sorts Work?
There’s no use trying to implement an algorithm in Java without first knowing what it is that we want our algorithm to do. Let’s start by walking through the steps a selection sort takes to sort a list in order.
Consider the following unsorted array:
17 | 14 | 9 | 12 |
Selection sorts set the first item as the smallest in the list. This is a temporary value which changes every time our program makes a comparison. This value is stored in its own variable.
minimum = 17 | |||
17 | 14 | 9 | 12 |
The “minimum” item is compared with the second element. This element is in the unsorted part of the array; every element after the sorted elements is unsorted.
Say the second element is smaller than the “minimum” item. In this case, the value of the “minimum” item is set to the value of the second item. 14 is smaller than 17, so our new minimum value becomes 14.
minimum = 14 | |||
17 | 14 | 9 | 12 |
This process repeats for each item in our list. 9 is less than 14. So, the value of “minimum” becomes 9. 9 is not less than 12, so the value of minimum stays the same.
After one iteration, our list has found that 9 is the smallest number. This item is moved to the start of the list:
9 | 17 | 14 | 12 |
This process starts over again from the first unsorted element. So, our next set of comparisons would begin with 17:
- 17 is equal to the minimum.
- Our program compares 17 with 14. The value of “minimum” becomes 14.
- Our program compares 14 is with 12. The value of “minimum” becomes 12.
- Our program moves 12 to end of the sorted items in the list.
Our list looks like this:
9 | 12 | 17 | 14 |
This process repeats until our list is ordered. When our algorithm has finished executing, the following list is returned:
9 | 12 | 14 | 17 |
Our list is sorted in ascending order.
How to Build a Selection Sort in Java
It’s one thing to know how a selection sort works; it’s another to build one. Let’s code a selection sort in Java that uses the logic we discussed in the walk through.
Set Up the Program
Create a file called selection_sort.java. We’ll start by importing the Java Arrays library into our code:
import java.util.Arrays;
We use this library later in our code. We use it to convert our sorted array to a string so that we can print it to the console.
Create a Sort Function
Next, we’re going to declare a class and create a method which performs our selection sort. Add the following to your selection_sort.java file:
class SelectionSort { void sortNumbers(int array[]) { int size = array.length; for (int item = 0; item < size - 1; item++) { int minimum = item; for (int number = minimum + 1; number < size; number++) { if (array[number] < array[minimum]) { minimum = number; } } int temporary = array[item]; array[item] = array[minimum]; array[minimum] = temporary; } } }
In our class, we have defined a method called sortNumbers which performs our sort. We start by calculating the length of our array. We store the length of our array in a Java variable.
Then, we create a Java for loop. This loop iterates through every item in our list. Inside this for loop, we find the minimum item, which is the first item in the list.
We then start another for loop to compare the minimum item with every item in the list.
"Career Karma entered my life when I needed it most and quickly helped me match with a bootcamp. Two months after graduating, I found my dream job that aligned with my values and goals in life!"
Venus, Software Engineer at Rockbot
If the number the for loop is reading is smaller than the minimum number, the value of “minimum” becomes that number. In our loop, “number” represents the index value of the number to which we are comparing to the minimum value.
Once the minimum number has been compared to every number in the list, our inner for loop stops. The minimum number is then moved after all the sorted numbers in the list.
Call the Sort Function
Our code doesn’t do anything just yet. We haven’t yet called our class and given it a list to sort.
Below the sortNumbers method in the list, add the following code:
public static void main(String args[]) { int[] toSort = { 17, 14, 9, 12 }; SelectionSort newSort = new SelectionSort(); newSort.sortNumbers(toSort); System.out.println(Arrays.toString(toSort)); }
Inside our main method we have declared a list of items to sort called toSort. We then initialize an instance of our SelectionSort class called newSort. We use this to call our sortNumbers method, which sorts the values in the toSort array.
After the sortNumbers method has executed, we print out the sorted array to the console. We do this using the Arrays.toString() method, which converts our array to a list of strings.
Let’s run our code:
[9, 12, 14, 17]
Our list has been sorted!
Selection Sort Java: Sort Values in Descending Order
It’s worth noting that you can sort values in descending order. To do so, replace the following line of code in your sortNumbers method:
if (array[number] < array[minimum]) {
With this code:
if (array[number] > array[minimum]) {
This code checks whether the “minimum” value is greater than the one being accessed by the for loop. This means that the value of “minimum” will reflect the highest value in a list instead of the lowest value.
To prevent confusion, you should rename “minimum” to “maximum”, if you are sorting a list in descending order.
You’ve done it. You have sorted a list in Java using the selection sorting algorithm.
What is the Complexity of a Java Selection Sort?
There are three time complexities that we need to consider when evaluating an algorithm: the best case, the worst case, and average case.
The selection sort has the best, average, and worst case complexity of O(n^2). This means that the algorithm will take exponentially longer as the numbers of the items in a list grow.
Are you confused by the complexity of algorithms? Check out our two-part series on Big O Notation. This is the notation we use to describe the complexity of algorithms.
Conclusion
Selection sorts are an efficient method of sorting lists of data. They work by selecting the smallest item from an unsorted list and moving that item to the beginning of the unsorted list. This process repeats until the list is sorted.
Do you want to become a Java developer? Check out our How to Learn Java guide. You’ll find top learning tips and advice on the best online courses and learning resources in this guide.
About us: Career Karma is a platform designed to help job seekers find, research, and connect with job training programs to advance their careers. Learn about the CK publication.