selection sort

Selection Sort is a simple comparison-based sorting algorithm. It works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the array and placing it in its correct position in the sorted portion.

---

Key Concepts of Selection Sort:

1. Selection:
   1. Find the smallest (or largest) element in the unsorted portion of the array.
2. Swapping:
   1. Swap the smallest (or largest) element with the first element of the unsorted portion.
3. Iteration:
   1. Repeat the process for the remaining unsorted portion until the entire array is sorted.

---

Characteristics of Selection Sort:

• Time Complexity:
  • Best Case: O(n2)O(n^2)O(n2)
  • Average Case: O(n2)O(n^2)O(n2)
  • Worst Case: O(n2)O(n^2)O(n2)
  • The number of comparisons is always n(n−1)/2n(n-1)/2n(n−1)/2, regardless of input.
• Space Complexity:
  • O(1)O(1)O(1) (in-place sorting).
• Stability:
  • Selection Sort is not stable by default because swapping may change the relative order of equal elements.

---

Implementation of Selection Sort in C:

C Code Example:

#include <stdio.h>

// Function to perform Selection Sort

void selectionSort(int arr[], int n) {

    for (int i = 0; i < n – 1; i++) {

        int minIdx = i;  // Index of the smallest element

        // Find the smallest element in the remaining array

        for (int j = i + 1; j < n; j++) {

            if (arr[j] < arr[minIdx]) {

                minIdx = j;

            }

        }

        // Swap the smallest element with the first element of the unsorted part

        if (minIdx != i) {

            int temp = arr[minIdx];

            arr[minIdx] = arr[i];

            arr[i] = temp;

        }

    }

}

// Utility function to print an array

void printArray(int arr[], int size) {

    for (int i = 0; i < size; i++) {

        printf(“%d “, arr[i]);

    }

    printf(“\n”);

}

// Main function

int main() {

    int arr[] = {64, 25, 12, 22, 11};

    int n = sizeof(arr) / sizeof(arr[0]);

    printf(“Original array: “);

    printArray(arr, n);

    selectionSort(arr, n);

    printf(“Sorted array: “);

    printArray(arr, n);

    return 0;

}

---

How It Works:

Example Walkthrough:

For the array {64, 25, 12, 22, 11}:

1. First Pass:
   1. Find the smallest element in the array: 11.
   1. Swap 11 with the first element: {11, 25, 12, 22, 64}.
2. Second Pass:
   1. Find the smallest element in the remaining array: 12.
   1. Swap 12 with the second element: {11, 12, 25, 22, 64}.
3. Third Pass:
   1. Find the smallest element in the remaining array: 22.
   1. Swap 22 with the third element: {11, 12, 22, 25, 64}.
4. Fourth Pass:
   1. Find the smallest element in the remaining array: 25.
   1. Swap 25 with the fourth element: {11, 12, 22, 25, 64}.
5. Final Array:
   1. {11, 12, 22, 25, 64}

---

Advantages and Disadvantages:

Advantages:

1. Simple:
   1. Easy to understand and implement.
2. In-Place Sorting:
   1. Requires minimal extra memory.
3. Predictable Performance:
   1. The number of comparisons is consistent.

Disadvantages:

1. Inefficient:
   1. Poor performance on large datasets due to O(n2)O(n^2)O(n2) complexity.
2. Not Stable:
   1. May not preserve the relative order of equal elements.
3. Always Performs n(n−1)/2n(n-1)/2n(n−1)/2 Comparisons:
   1. Even if the array is already sorted.

---

Example Output:

For the input array {64, 25, 12, 22, 11}:

Original array: 64 25 12 22 11

Sorted array: 11 12 22 25 64

---

When to Use Selection Sort:

1. Small Datasets:
   1. Suitable for small arrays due to simplicity.
2. Learning:
   1. Useful for educational purposes to understand the concept of sorting.
3. Memory Constraints:
   1. Requires minimal additional memory.

---

Selection Sort is a straightforward algorithm but is inefficient for large datasets. For better performance, consider using more advanced algorithms like Merge Sort or Quick Sort for larger arrays.