Sort an array using Selection Sort in DSA

🔹 Introduction to Selection Sort

Selection Sort is one of the simplest sorting algorithms in data structures. It is an in-place comparison-based algorithm. The main idea is to divide the array into a sorted and an unsorted part, then repeatedly select the smallest (or largest) element from the unsorted part and move it to the sorted part.

Selection Sort is easy to understand and implement, making it ideal for beginners learning DSA.

🔹 How Selection Sort Works

The process of Selection Sort can be summarized as:

Start with the first element of the array as the current minimum.
Scan the rest of the array to find the smallest element.
Swap the smallest element with the first element.
Move to the next position and repeat steps 1–3 until the array is sorted.

Example
Array: [64, 25, 12, 22, 11]

Step	Array Status	Action
1	`[64, 25, 12, 22, 11]`	Minimum is 11 → Swap with 64
2	`[11, 25, 12, 22, 64]`	Minimum is 12 → Swap with 25
3	`[11, 12, 25, 22, 64]`	Minimum is 22 → Swap with 25
4	`[11, 12, 22, 25, 64]`	Minimum is 25 → Already in place
5	`[11, 12, 22, 25, 64]`	Done

🔹 Selection Sort Algorithm (Step by Step)

Step 1: Loop through the array from index i = 0 to n-2.
Step 2: Set minIndex = i.
Step 3: Loop from j = i+1 to n-1 to find the smallest element.
Step 4: If a smaller element is found, update minIndex.
Step 5: Swap arr[i] with arr[minIndex].
Step 6: Repeat until the array is sorted.

🔹 Time Complexity

Best Case: O(n²) – Even if the array is already sorted, Selection Sort still checks all pairs.
Average Case: O(n²)
Worst Case: O(n²)

Space Complexity: O(1) (In-place sorting)

Selection Sort is not stable by default, meaning equal elements may change order after sorting.

🔹 C/C++ Example

#include <stdio.h>

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

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: ");
    for(int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

🔹 Java Example

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.print("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

🔹 Advantages of Selection Sort

Simple and easy to implement. ✅
Requires no extra memory (in-place). ✅
Works well for small arrays. ✅

🔹 Disadvantages of Selection Sort

Inefficient for large arrays due to O(n²) time complexity. ❌
Not stable by default. ❌
Performs unnecessary swaps even if the array is partially sorted. ❌

🔹 Conclusion

Selection Sort is a beginner-friendly algorithm to understand the basic concepts of sorting. While it is not suitable for large datasets due to its O(n²) complexity, it provides a solid foundation for learning more advanced sorting algorithms like Quick Sort, Merge Sort, and Heap Sort.