What is a selection sort in C and how is it implemented?

Table of Contents

• Introduction
• How Selection Sort Works in C
  • Algorithm Steps
  • Time Complexity:
  • Space Complexity:
• Implementation of Selection Sort in C
  • Explanation of the Code:
  • Output:
• Practical Examples
  • Example 1: Sorting a List of Student Scores
  • Example 2: Sorting Characters by ASCII Values
• Conclusion

Introduction

Selection sort is one of the simplest comparison-based sorting algorithms. It divides the array into two parts: a sorted section and an unsorted section. The algorithm works by repeatedly selecting the smallest element from the unsorted section and swapping it with the first unsorted element, thereby growing the sorted portion of the array.

Although selection sort has a time complexity of O(n²), which makes it inefficient for large datasets, it is easy to understand and implement, making it a good choice for small arrays or teaching purposes.

How Selection Sort Works in C

Algorithm Steps

1. Initialize the unsorted array: Assume the entire array is unsorted at first.
2. Find the minimum element: Starting from the unsorted portion, locate the smallest element.
3. Swap elements: Swap this smallest element with the first element of the unsorted portion.
4. Move boundary: Move the boundary between the sorted and unsorted sections to the right by one.
5. Repeat: Continue the process until all elements are sorted.

Time Complexity:

• Worst-case: O(n²)
• Best-case: O(n²)
• Average-case: O(n²)

Space Complexity:

• Space Complexity: O(1) (in-place sorting)

Implementation of Selection Sort in C

Here’s how to implement selection sort in C:

Explanation of the Code:

1. selectionSort Function:
   • The outer loop runs through each element of the array, treating the first unsorted element as the minimum.
   • The inner loop finds the minimum value in the unsorted section of the array.
   • Once the minimum is found, it swaps that value with the first unsorted element.
2. printArray Function:
   • This function iterates through the array and prints each element.

Output:

Practical Examples

Example 1: Sorting a List of Student Scores

You can use selection sort to organize student scores in ascending order.

Output:

Example 2: Sorting Characters by ASCII Values

Selection sort can also be applied to character arrays to sort elements by their ASCII values.

Output:

Conclusion

Selection sort is a simple and easy-to-implement sorting algorithm. It works by repeatedly finding the smallest element in the unsorted portion of the array and swapping it with the first unsorted element. While selection sort is inefficient for large datasets due to its O(n²) time complexity, it is a valuable tool for small arrays and educational purposes. Implementing selection sort in C is straightforward and involves basic loop constructs.