Selection Sort In Java

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 on Different Data Structures – Sorting Arrays

Selection Sort in Java works efficiently with arrays by repeatedly finding the minimum element and placing it at the beginning. This method is particularly useful when sorting arrays in Java without using additional memory.

Below is a Java selection sort example that sorts an array:

public class SelectionSortExample {
    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};  // Unsorted array

        // Selection Sort in Java
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;

            // Find the index of the minimum element
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

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

        // Print sorted array
        System.out.print("Sorted Array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

Output:

Sorted Array: 11 12 22 25 64

This Java selection sort example highlights how easily the selection sort algorithm can be applied to arrays in Java, especially when no extra memory is needed.

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.

Advantages and Disadvantages of Selection Sort

Advantages of Selection Sort

• Simple to understand and implement, making it a great choice for beginners.
   
• No additional memory is required as it’s an in-place sorting algorithm.
   
• Works well on small datasets where performance is not critical.
   
• Deterministic behavior with a predictable number of swaps.

Disadvantages of Selection Sort in Java

• Poor performance on large datasets due to its O(n²) time complexity.
   
• Not stable, which means the relative order of equal elements is not preserved.
   
• More comparisons than other simple sorts, reducing efficiency.
   
• Not suitable for real-time applications or performance-critical tasks.

Selection Sort vs Other Sorting Algorithms

Selection Sort vs Bubble Sort

Selection Sort vs Insertion Sort

Use Cases of Selection Sort

When to Use Selection Sort

• When memory is limited, as it does not require extra space.
   
• In educational applications where simple logic is needed for teaching sorting.

When Not to Use Selection Sort

• On large datasets, due to its quadratic time complexity.
   
• In performance-critical systems where faster algorithms like QuickSort or MergeSort are preferred.

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.