Selection sort algorithm Java
Selection sort algorithms are used to reorder the elements of an array or list in ascending or descending numerical or lexicographic order. Sorting is very important for the optimal performance of other algorithms that require sorted input data.
V článku sa dozvieš:
There are a number of different sorting algorithms. The selection of an appropriate algorithm depends on factors such as the size and characteristics of the input data, available memory, and time and space requirements.
To make your choice easier, in our series we will introduce the most well-known data sorting algorithms, explain their principles, advantages and disadvantages, and program them in Java.
So far, we have discussed the following sorting algorithms:
- Sorting algorithms: Introduction to data sorting
- Bubble sort
- Comb sort
- Big O notation: analysis of algorithms’ time and space complexity
Today we are going to look at selection sort.
Selection sort algorithm
Selection sort is a simple data sorting algorithm that divides the input field into two parts: sorted and unsorted. It then repeatedly selects the smallest (largest) element from the unsorted part and moves it to the sorted part. The algorithm is very inefficient for large numbers of elements in the input, but it is often used in situations where there are relatively few elements in the input, usually in combination with other sorting algorithms.
How selection sort works
Suppose we want to sort the input vector from smallest to largest element. For reverse sorting, the whole logic of the algorithm is inverted. The sorted part of the array is always empty at the start of the algorithm.
- At the beginning of the algorithm, we assume that the first element (of the unsorted part) is the minimum (i.e., the smallest).
- We compare this element with the remaining elements in the unsorted part of the array and look for the true minimum.
- If we find a minor element in the unsorted part, we replace the elements.
- The replaced element becomes part of the sorted dataset, its index is increased by 1 and the unsorted part is decreased.
- Repeat steps 1 to 4 until the entire field is sorted.
We will later show a practical selection sort example in Java code.
Selection sort advantages
- Easy to understand and implement
- Works well for small lists of data
Selection sort disadvantages
- The time complexity is O(n²), making it a slow algorithm for a large dataset
- Not stable
Selection sort time complexity
| Algorithm | Method | Time Complexity | Memory | Stable | ||
| worst | average | best | ||||
| Selection sort | Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
Selection sort animation, visualization, gif
The visualization of the Selection sort algorithm looks like this:
Source: commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms
To see how the algorithm is animated, go to Toptal. There are 8 types of algorithms. You can also play the animation backwards.
On this page you can go through the steps of the algorithm to check the time taken by the algorithm.
Selection sort Java implementation
learned the principles of the algorithm, we can now program it in Java.
SelectionSort.java
package sorting;
public class SelectionSort {
private boolean change;
private int temp;
public void sort(int data[])
{
for (int i = 0; i < data.length - 1; i++) {
System.out.println(i + 1 + ". iteration");
// Find the index of the minimum in unsorted part of array
int minIndex = i;
for (int j = i + 1; j < data.length; j++) {
if (data[j] < data[minIndex])
minIndex = j;
}
// Swap the minimum element with first element from unsorted part, unless they are the same
if(i != minIndex) {
System.out.print("Found minimum: " + data[minIndex] + ", swapping with " + data[i] + " => ");
temp = data[minIndex];
data[minIndex] = data[i];
data[i] = temp;
}
else
System.out.print("Minimum: " + data[minIndex] + " is on the right spot, no swapping => ");
printArray(data);
}
}
// Function to print an array
public void printArray(int data[])
{
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + " ");
System.out.println();
}
}
Main.java
import sorting.SelectionSort;
public class Main {
public static void main(String[] args) {
int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };
SelectionSort selectionSort = new SelectionSort();
System.out.print("Input: ");
selectionSort.printArray(dataToSort);
selectionSort.sort(dataToSort);
System.out.print("Sorted: ");
selectionSort.printArray(dataToSort);
}
}The output of this example is:
We have prepared the files with the above example as code that you can run directly in Java. Download SelectionSort Java code.
If you’re a Java developer looking for a job, check out our employee benefits and respond to our job offers!
