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 at the beginning.

This method divides the array into two parts:

• Sorted part (initially empty)
• Unsorted part (initially the full array)

How Selection Sort Works?

• Start from the first element and assume it's the minimum.
• Compare it with the rest of the array to find the actual minimum.
• Swap the actual minimum with the current index.
• Move to the next index and repeat the process until the array is fully sorted.

Example: Selection Sort

Sorting the array [64, 25, 12, 22, 11] using Selection Sort

Step-by-Step Process:

Pass 1:

• Unsorted portion: [64, 25, 12, 22, 11]
• Minimum element: 11 at index 4
• Swap 64 with 11

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

Pass 2:

• Unsorted portion: [25, 12, 22, 64]
• Minimum element: 12 at index 2
• Swap 25 with 12

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

Pass 3:

• Unsorted portion: [25, 22, 64]
• Minimum element: 22 at index 3
• Swap 25 with 22

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

Pass 4:

• Unsorted portion: [25, 64]
• Minimum element: 25 at index 3 (already in place)
• No swap needed

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

Pass 5:

• Only one element left: [64]
• No comparison or swap needed

Final Sorted Array: [11, 12, 22, 25, 64]

Summary of Each Pass

Algorithm for Selection Sort

Step-by-Step Algorithm:

Start
Repeat steps 3 to 6 for i = 0 to n-2
	Set min = i
	Repeat steps 5 for j = i+1 to n-1
		If A[j] < A[min], then set min = j
	If min ≠ i, then swap A[i] and A[min]
End

• The outer loop selects the current position to fill with the smallest element from the unsorted part.
• The inner loop finds the index of the minimum element.
• A swap is made only if a smaller element is found.

Advantages of Selection Sort

Simple to Understand and Implement: The logic is straightforward and easy for beginners to grasp.

In-Place Sorting: It requires only constant O(1) extra memory—no additional data structures.

Performs Well on Small Data Sets: For very small arrays (e.g., fewer than 10 elements), the performance is acceptable.

Consistent Number of Comparisons: Always performs n(n-1)/2 comparisons, regardless of input order.

Disadvantages of Selection Sort

Inefficient for Large Lists: Time complexity is always O(n²), making it slow for large datasets.

Unstable Sort: It may change the relative order of equal elements (e.g., [4a, 4b, 3] may become [3, 4b, 4a]).

Not Adaptive: Unlike insertion sort, it does not take advantage of partially sorted arrays.

High Number of Comparisons: Even if the array is already sorted, it still performs the same number of comparisons.

When to Use Selection Sort?

• When memory space is extremely limited (only O(1) extra space).
• When the list size is very small, like fewer than 10–20 elements.
• When you want a simple sorting technique for teaching or learning basic algorithms.
• When data movement is costly, and you want to minimize the number of swaps (Selection Sort does fewer swaps than Bubble Sort).

Selection Sort in C Programming

#include <stdio.h>

// Function to perform selection sort
void selectionSort(int arr[], int n) {
    int i, j, min_idx, temp;

    // Outer loop for each position in the array
    for (i = 0; i < n - 1; i++) {
        // Assume the current index is the minimum
        min_idx = i;

        // Find the index of the smallest element in the remaining array
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }

        // Swap the found minimum element with the current element
        if (min_idx != i) {
            temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
}

// Function to print the array
void printArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; 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;
}

Output

Original array: 64 25 12 22 11 
Sorted array:   11 12 22 25 64

Complexity of Selection Sort

Time Complexity

Selection sort does not adapt to input it performs the same number of comparisons in all cases, regardless of whether the array is already sorted or not.

Number of Swaps:

• At most (n - 1) swaps (one for each position).
• Fewer swaps compared to bubble or insertion sort.

Space Complexity

• O(1) auxiliary space (in-place algorithm).
• No additional data structures are required.

Numerical Question for selection Sort

1. Sort the following array using Selection Sort: [29, 10, 14, 37, 14]
   • Show the array after each pass.
2. Perform Selection Sort on the array: [64, 25, 12, 22, 11]
   • Show all intermediate steps and swaps.
3. Use Selection Sort to sort in descending order: [3, 1, 4, 1, 5, 9]
   • Modify selection sort logic to sort from highest to lowest.
   • Show result after each pass.