Selection Sort in C: Program to Sort Array Using Selection Sort Algorithm

📚 In this tutorial, you will learn:

What is selection sort and how it works
How to implement selection sort in C
How selection sort finds the minimum element in each pass
Step-by-step explanation of the program
Time and space complexity of selection sort
Practice exercises to test your understanding

Introduction

In this tutorial, we will learn how to write a C program to sort an array using the selection sort algorithm.

Selection sort is a simple and intuitive sorting algorithm. It works by dividing the array into two parts: the sorted part at the beginning and the unsorted part at the end. In each pass, the algorithm finds the minimum element from the unsorted part and swaps it with the first element of the unsorted part, gradually building the sorted list.

💡 Key Point: Selection sort is known for its simplicity and is often used when memory is limited. It performs the same number of comparisons regardless of the initial order of the array.

Selection sort is used in various scenarios, such as:

Education: Teaching fundamental sorting concepts
Small Datasets: Sorting small arrays where simplicity is key
Embedded Systems: When memory is constrained and simple logic is preferred
Visualizations: Creating sorting algorithm animations

Visual Example

Let's see how selection sort sorts the array [64, 25, 12, 22, 11]:

Pass 1 (i=0): Find minimum in [64, 25, 12, 22, 11] → 11

[64, 25, 12, 22, 11] → Swap 64 and 11 → [11, 25, 12, 22, 64]

Pass 2 (i=1): Find minimum in [25, 12, 22, 64] → 12

[11, 25, 12, 22, 64] → Swap 25 and 12 → [11, 12, 25, 22, 64]

Pass 3 (i=2): Find minimum in [25, 22, 64] → 22

[11, 12, 25, 22, 64] → Swap 25 and 22 → [11, 12, 22, 25, 64]

Pass 4 (i=3): Find minimum in [25, 64] → 25 (no swap needed)

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

C Program for Selection Sort

#include <stdio.h>

int main() {
    int n, i, j, min_idx, temp;
    
    // Ask user for number of elements
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    
    // Declare array
    int arr[n];
    
    // Read elements into the array
    printf("Enter %d elements:\n", n);
    for(i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    // Selection Sort Algorithm
    for(i = 0; i < n-1; i++) {
        // Find the minimum element in the unsorted part
        min_idx = i;
        for(j = i+1; j < n; j++) {
            if(arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // Swap the found minimum with the first element of the unsorted part
        if(min_idx != i) {
            temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
    
    // Display sorted array
    printf("\nSorted array in ascending order: ");
    for(i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

Sample Output

Enter the number of elements: 5
Enter 5 elements:
64 25 12 22 11

Sorted array in ascending order: 11 12 22 25 64

Another Example:

Enter the number of elements: 6
Enter 6 elements:
29 10 14 37 13 33

Sorted array in ascending order: 10 13 14 29 33 37

Example with Negative Numbers:

Enter the number of elements: 6
Enter 6 elements:
-5 10 -2 8 0 -10

Sorted array in ascending order: -10 -5 -2 0 8 10

Program Explanation

Let's break down the code step by step:

Include Header File: #include <stdio.h> includes the standard input/output library.
Declare Variables:
- int n; — number of elements
- int i, j; — loop counters
- int min_idx; — index of the minimum element in the unsorted part
- int temp; — temporary variable for swapping
Get User Input: Reads the array elements from the user.
Selection Sort:
- Outer Loop: for(i = 0; i < n-1; i++) — runs n-1 times
- Inner Loop: for(j = i+1; j < n; j++) — finds the minimum element
- Find Minimum: If arr[j] < arr[min_idx], update min_idx
- Swap: Swap the minimum element with arr[i]
Display Result: Prints the sorted array.
Return: return 0; indicates successful program execution.

📝 Note: Selection sort has a time complexity of O(n²) in all cases. It is not efficient for large arrays but is great for learning sorting concepts.

Selection Sort Algorithm

Step-by-step algorithm:

Start
Read the array elements
For i = 0 to n-2:
- Set min_idx = i
- For j = i+1 to n-1:
  - If arr[j] < arr[min_idx]:
    - Set min_idx = j
- Swap arr[i] and arr[min_idx]
Print the sorted array
End

Time and Space Complexity

Scenario	Time Complexity	Space Complexity
Best Case (Already Sorted)	O(n²)	O(1)
Worst Case (Reverse Sorted)	O(n²)	O(1)
Average Case	O(n²)	O(1)

💡 Note: Selection sort performs n(n-1)/2 comparisons regardless of the input, which makes it O(n²) in all cases. However, it performs at most n-1 swaps, which is efficient for memory writes.

💻 Practice Exercise

Challenge 1: Modify the selection sort program to sort the array in descending order.

Challenge 2: Modify the program to find the maximum element in each pass instead of the minimum.

🔍 Click to Show Solution for Challenge 1

#include <stdio.h>

int main() {
    int n, i, j, max_idx, temp;
    
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    
    int arr[n];
    
    printf("Enter %d elements:\n", n);
    for(i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    // Selection Sort for Descending Order
    for(i = 0; i < n-1; i++) {
        max_idx = i;
        for(j = i+1; j < n; j++) {
            if(arr[j] > arr[max_idx]) {  // Change < to > for descending
                max_idx = j;
            }
        }
        if(max_idx != i) {
            temp = arr[i];
            arr[i] = arr[max_idx];
            arr[max_idx] = temp;
        }
    }
    
    printf("\nSorted array in descending order: ");
    for(i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

Frequently Asked Questions

1. What is selection sort in C?

Selection sort is a simple sorting algorithm that repeatedly selects the minimum element from the unsorted part and places it at the beginning. It divides the array into sorted and unsorted parts.

2. What is the time complexity of selection sort?

Selection sort has a time complexity of O(n²) in all cases (best, average, worst). It performs n(n-1)/2 comparisons and at most n-1 swaps.

3. Is selection sort stable?

Selection sort is not stable because it can change the relative order of equal elements when swapping.

4. How many swaps does selection sort perform?

Selection sort performs at most n-1 swaps, which is better than bubble sort in terms of swaps.

5. When should I use selection sort?

Selection sort is useful when memory is limited (in-place sorting) or when you need a simple algorithm for educational purposes. It's not recommended for large datasets.

💡 Tip: Selection sort is a great starting point for learning sorting algorithms. Once you understand it, you can move on to more efficient algorithms like Quick Sort or Merge Sort.

Previous Topic: -->> Bubble Sort in C || Next topic: -->> Insertion Sort in C

📚 Explore More Topics