NUHMAN.com

Sorting is one of the most fundamental problems in computer science. Among the various sorting algorithms, Selection Sort is a simple and intuitive algorithm that works by repeatedly selecting the minimum (or maximum) element from the unsorted portion of the array and swapping it with the first unsorted element.

In this article, we will go through the implementation of Selection Sort in Java, explaining its steps, time complexity, and providing an example.

📚 How Does Selection Sort Work?

Selection Sort works by repeatedly finding the smallest element from the unsorted portion of the array and swapping it with the first unsorted element. The algorithm iterates through the array, progressively shrinking the unsorted section and growing the sorted section.

Steps:

1. Start from the first element and iterate over the array to find the smallest element.
2. Swap the smallest element found with the first unsorted element.
3. Move the boundary of the unsorted subarray one element forward.
4. Repeat this process until the entire array is sorted.

🖥️ Java Implementation of Selection Sort

Below is the Java code for implementing Selection Sort:

java

public class SelectionSort {
    // Method to perform selection sort
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        
        // Traverse through all array elements
        for (int i = 0; i < n - 1; i++) {
            // Find the minimum element in the unsorted portion of the array
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j; // Update minIndex if a smaller element is found
                }
            }
            
            // Swap the found minimum element with the first element
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    // Main method to test the selection sort
    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        
        System.out.println("Unsorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        
        // Call selection sort to sort the array
        selectionSort(arr);
        
        System.out.println("\nSorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

💡 Explanation

selectionSort Method:

• This method loops through each element of the array and finds the minimum element in the unsorted portion.
• The minIndex variable stores the index of the smallest element.
• Once the minimum element is found, it swaps that element with the first unsorted element to expand the sorted portion of the array.

main Method:

• This method initializes an array of unsorted integers and prints the array.
• It then calls the selectionSort method to sort the array.
• Finally, it prints the sorted array.

⏱️ Time Complexity

• Worst Case: O(n²)
• Best Case: O(n²) (no improvement in the best case)
• Average Case: O(n²)

The algorithm always performs the same number of comparisons regardless of whether the array is already sorted or not. Therefore, it has a time complexity of O(n²) in all cases.

🏅 When to Use Selection Sort?

Selection Sort is simple to understand and implement, but it is not the most efficient algorithm for large datasets because of its O(n²) time complexity. It is best suited for:

• Small datasets where the simplicity of the algorithm is more beneficial than optimization.
• Educational purposes to demonstrate the basic principles of sorting.

🚀 How to Run

1. Save the code in a file named SelectionSort.java.
2. Compile the Java program using the command:

nginx

javac SelectionSort.java

1. Run the compiled class:

nginx

java SelectionSort

1. You will see the unsorted and sorted arrays printed to the console.

📈 Conclusion

Selection Sort is a straightforward sorting algorithm that is often used in introductory computer science courses. While it’s not the most efficient for large datasets due to its O(n²) time complexity, it is an excellent way to understand the fundamentals of sorting algorithms. By following this example, you now have the knowledge to implement Selection Sort in your Java projects!