Selection Sort: Algorithm & Implementation

1️⃣ What is Selection Sort?

🔹 Selection Sort is a simple comparison-based sorting algorithm.
🔹 It selects the smallest (or largest) element from the unsorted part and swaps it with the first element of the unsorted part.
🔹 It continues this process until the entire array is sorted.

✅ Time Complexity

Case	Complexity
Best Case (Already Sorted)	O(n²)
Average Case	O(n²)
Worst Case (Reversed Order)	O(n²)

✅ Space Complexity

• O(1) (In-place sorting)

✅ Is it Stable?

❌ No (It may change the relative order of equal elements)

---

2️⃣ How Selection Sort Works

🔹 The algorithm divides the array into sorted and unsorted parts.
🔹 It finds the minimum element in the unsorted part and swaps it with the first element of the unsorted part.
🔹 This process is repeated for all elements.

Step-by-Step Example

📝 Input: [29, 10, 14, 37, 13]

Step	Array State	Minimum Found	Swap Performed
1	[29, 10, 14, 37, 13]	10	Swap 29 ↔ 10
2	[10, 29, 14, 37, 13]	13	Swap 29 ↔ 13
3	[10, 13, 14, 37, 29]	14	No swap needed
4	[10, 13, 14, 37, 29]	29	Swap 37 ↔ 29
5	[10, 13, 14, 29, 37]	37	No swap needed

🔹 Final Sorted Array: [10, 13, 14, 29, 37]

---

3️⃣ Selection Sort Algorithm

🔹 Pseudocode

for i = 0 to n-2:
    minIndex = i
    for j = i+1 to n-1:
        if arr[j] < arr[minIndex]:
            minIndex = j
    Swap arr[i] and arr[minIndex]

---

4️⃣ Selection Sort Implementation in C

#include <stdio.h>

// Function to perform Selection Sort
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        
        // Find the minimum element in the remaining unsorted array
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

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

// Function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Main function
int main() {
    int arr[] = {29, 10, 14, 37, 13};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    selectionSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

🔹 Output

Original array: 29 10 14 37 13
Sorted array: 10 13 14 29 37

---

5️⃣ Advantages & Disadvantages

✅ Advantages

✔ Simple & easy to implement
✔ Works well for small datasets
✔ Performs well when memory writes are costly (e.g., flash memory)
✔ Does not require extra memory (O(1) space complexity)

❌ Disadvantages

❌ Inefficient for large datasets (O(n²))
❌ Slower than Quick Sort & Merge Sort
❌ Not a stable sorting algorithm

---

6️⃣ When to Use Selection Sort?

🔹 Best for small datasets (e.g., <100 elements).
🔹 Good when memory writes are expensive (fewer swaps).
🔹 Not ideal for large datasets; use Merge Sort or Quick Sort instead.