Table of contents
1.
Introduction
2.
How Does Selection Sort Work?
3.
Time Complexity
4.
Space Complexity
5.
Selection Sort Java Example
5.1.
Java
6.
Frequently Asked Questions
6.1.
Why is Selection Sort not suitable for large datasets?
6.2.
Can Selection Sort be used for sorting strings?
6.3.
Is Selection Sort stable?
7.
Conclusion
Last Updated: Mar 31, 2024
Easy

Selection Sort In Java

Author Rinki Deka
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Sorting is a fundamental operation in computer science, crucial for organizing data in a structured manner. Among the various sorting algorithms, Selection Sort stands out for its simplicity & ease of understanding, making it an ideal starting point for beginners in programming. 

Selection Sort In Java

This article will walk you through the basics of Selection Sort, its operational mechanics, & how to implement it in Java. We'll explore its efficiency in terms of time & space complexity & provide a hands-on example to solidify your understanding. 

How Does Selection Sort Work?

Selection Sort is a straightforward sorting technique. Imagine you have a row of books that you want to arrange in order, from the smallest to the largest. What you do is, you look for the smallest book & place it at the beginning. Then, you search for the next smallest book among the remaining ones & place it next to the first. You repeat this process until all books are arranged in order.

In Selection Sort, we do something similar with numbers (or any other items that can be compared). We start with an array, which is just a collection of elements, like our row of books. Here’s the step-by-step process:

  • Find the Minimum: Look through the entire array to find the smallest element.
     
  • Swap: Move this smallest element to the start of the array.
     
  • Repeat: Now, ignore the first position (since it's already sorted) & repeat the process for the remaining part of the array.
     

We keep doing this until we reach the end of the array. By then, all elements are sorted in ascending order.

Here’s a quick example to clarify:

Suppose we have an array [29, 10, 14, 37, 13]. In the first round, we find 10 as the smallest number & swap it with 29. The array becomes [10, 29, 14, 37, 13]. Next, we start from the second position & find 13 as the next smallest number, which we swap with 29. This process continues until the entire array is sorted.

This method might not be the fastest for large arrays, but its simplicity makes it a great tool for learning & understanding how sorting works.

Time Complexity

When we talk about time complexity, we're essentially asking: "How long does it take to sort an array using Selection Sort?" This is important because it gives us an idea of how efficient or inefficient an algorithm is.

For Selection Sort, the time it takes doesn't depend on the arrangement of the elements in the array. Whether they're almost sorted, completely reversed, or in random order, Selection Sort goes through the same steps:

  • It looks at each element in the array (except the last one) and compares it to every other element to find the minimum.
     
  • It makes a swap if needed.
     
  • Because of these steps, for every element, it needs to make a bunch of comparisons with all the other elements. Specifically, for an array with n elements, the first element needs n-1 comparisons, the second needs n-2 comparisons (since the first element is already sorted), and so on, until the last element, which doesn't need any comparison.
     
  • When you add up all these comparisons, it turns out that Selection Sort makes about n*(n-1)/2 comparisons in total, where n is the number of elements in the array. This is why we say Selection Sort has a time complexity of O(n^2) (read as "order n squared"). This means that the time it takes grows with the square of the size of the input. So, if you double the number of elements, the sorting time goes up by four times, making Selection Sort not the best choice for large arrays.
     

In simple terms, Selection Sort is like going through every item on your shopping list to make sure you're getting each item one by one, regardless of how long the list is. It's thorough but can take a lot of time if your list is really long.

Space Complexity

When we talk about space complexity, we're interested in how much extra space or memory an algorithm needs to do its job. With Selection Sort, the good news is it's quite efficient in terms of space.

Selection Sort is an "in-place" sorting algorithm. This means it doesn't need any additional temporary arrays or lists to sort the data. The only extra space it uses is for a few variables to keep track of the minimum value and its index during each pass through the array.

Here's the breakdown:
 

  • Extra Variables: We typically need just one extra variable to store the index of the current minimum element as we find it. Sometimes, we might also use a temporary variable for swapping elements, but that's about it.
     
  • In-Place Swapping: Since all the swapping of elements happens within the original array, we're not using extra space for another data structure.
     
  • Because of this, the space complexity of Selection Sort is O(1). This "constant space" usage means that no matter how big the array is, the amount of extra memory we need doesn't change. It's like having a small notebook where you only need to jot down a couple of numbers, regardless of whether you're sorting a list of 10 items or 10,000 items.
     

This makes Selection Sort a space-efficient option, especially when you're working with limited memory resources. However, remember that while it's great in terms of space, its time efficiency is another story, especially with large datasets.

Selection Sort Java Example

The following example implement whatever we have learnt above.

First, you need to set up your Java environment. If you haven’t already, download and install the Java Development Kit (JDK) from the official Oracle website. Then, you can write your code in any text editor and run it using the Java compiler (javac) and Java interpreter (java) from the command line.

Here’s a simple Java program that implements the Selection Sort algorithm:

  • Java

Java

public class SelectionSortExample {
// Method to perform selection sort
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
// Find the index of the minimum element
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // Update the index of the minimum element
}
}

// Swap the minimum element with the first unsorted element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}

// Main method to test the selectionSort method
public static void main(String[] args) {
int[] myArray = {64, 25, 12, 22, 11}; // Example array
selectionSort(myArray); // Calling the selection sort method
System.out.println("Sorted array: ");
for (int value : myArray) {
System.out.print(value + " "); // Printing the sorted array
}
}
}
You can also try this code with Online Java Compiler
Run Code

 

Output

Sorted array: 
11 12 22 25 64 


This code defines a SelectionSortExample class with two methods: selectionSort, which performs the sorting, and main, which tests the selectionSort method.

In the selectionSort method, we loop over the array, each time finding the smallest element in the unsorted portion of the array and swapping it with the element at the current position.

The main method creates an array, calls selectionSort to sort it, and then prints the sorted array.

To run this program, save it to a file named SelectionSortExample.java, open your command line or terminal, navigate to the directory containing your file, and execute the following commands:

javac SelectionSortExample.java
java SelectionSortExample


You should see the sorted array printed out, demonstrating the Selection Sort algorithm in action.

Frequently Asked Questions

Why is Selection Sort not suitable for large datasets?

Selection Sort has a time complexity of O(n^2), meaning the time it takes to sort grows quadratically with the size of the dataset. For large arrays, this can lead to significant inefficiencies, making Selection Sort less ideal compared to faster algorithms like Quick Sort or Merge Sort.

Can Selection Sort be used for sorting strings?

Yes, Selection Sort can be adapted to sort arrays of strings or any other objects, as long as a comparison can be made between the elements. The logic remains the same; you just need to compare strings based on alphabetical order or any other criteria you define.

Is Selection Sort stable?

By default, Selection Sort is not stable, meaning it might change the order of equal elements. However, it can be made stable with some modifications to the algorithm, ensuring that equal elements retain their original order.

Conclusion

In this article, we've learned everything about Selection Sort, a fundamental sorting algorithm that is famous for its simplicity. We started by understanding how Selection Sort operates, methodically selecting the smallest unsorted element and placing it in its correct position. We then examined its time and space complexity, highlighting its efficiency in terms of memory usage but cautioning against its use for larger datasets due to its quadratic time complexity.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.

Live masterclass