Selection Sort

Table of Contents 📚

1. Introduction to Selection Sort
2. How Does Selection Sort Work?
3. Java Implementation
4. Time and Space Complexity
5. Conclusion

🌟 Introduction to Selection Sort

Selection sort is another straightforward sorting algorithm that is particularly easy to understand and implement. Although not the most efficient, it’s still important due to its simplicity, ease of use, and the fact that it performs well on small lists or arrays.

🎨 How Does Selection Sort Work?

Let’s take an array [29, 10, 14, 37, 13]. The basic idea of selection sort is:

1. Find the Minimum Element: Find the minimum element in the remaining array.
2. Swap: Swap it with the first unsorted element.

Let’s break it down:

• First Pass:
  • Minimum = 10, Swap 29 with 10
    [10, 29, 14, 37, 13]
• Second Pass:
  • Minimum = 14, Swap 29 with 14
    [10, 14, 29, 37, 13]
• And so on…

💻 Implementation of Selection Sort in Java

Here is how you could implement the selection sort algorithm in Java.

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {29, 10, 14, 37, 13};
        selectionSort(arr);
        
        for(int num : arr) {
            System.out.print(num + " ");
        }
    }

    public static void selectionSort(int[] arr) {
        int n = arr.length;

        for(int i = 0; i < n - 1; i++) {
            int minIndex = i;
            
            for(int j = i + 1; j < n; j++) {
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            
            // Swap arr[minIndex] and arr[i]
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

📈 Time and Space Complexity

• Time Complexity: The time complexity is O(n²) for all cases (worst, average, and best) as there are two nested loops.
• Space Complexity: The algorithm runs in constant space O(1), excluding the input space.

🎓 Conclusion

In this post, we covered the selection sort algorithm, a Java implementation, and its time and space complexities. While not the most efficient, the algorithm is simple and intuitive, making it a good starting point for understanding sorting algorithms.

If you enjoyed this guide, please share with others, and spread the knowledge!