Implementation of Selection Sort Using C in Data Structure

Selection Sort is a fundamental sorting algorithm widely taught in computer science courses due to its simplicity and ease of implementation. This article will focus on the implementation of Selection Sort using C, along with its use cases and step-by-step explanation.

Selection Sort is an in-place sorting algorithm that divides the input array into two parts: a sorted section and an unsorted section. At each step, the smallest (or largest, depending on the order) element is selected from the unsorted section and swapped with the first element of the unsorted section. This process is repeated until the array is completely sorted.

Key Features of Selection Sort

• Time Complexity:

  • Best, Average, and Worst Case: O(n²)
  • Not suitable for large datasets due to its quadratic time complexity.

• Space Complexity:

  • O(1) (In-place sorting)

• Stability:

  • Selection Sort is not stable by default but can be made stable with slight modifications.

How Selection Sort Works

Steps in the Algorithm:

1. Divide the Array: Divide the array into two sections: sorted and unsorted. Initially, the sorted section is empty.
2. Find Minimum: Iterate through the unsorted section to find the minimum element.
3. Swap: Swap the minimum element with the first element of the unsorted section.
4. Expand Sorted Section: Move the boundary between the sorted and unsorted sections to include the newly sorted element.
5. Repeat: Repeat steps 2-4 until the entire array is sorted.

Example Walkthrough

Given an array: [64, 25, 12, 22, 11]

1. Find the smallest element (11) and swap it with the first element.
   • Array after step 1: [11, 25, 12, 22, 64]
2. Find the smallest element in the unsorted section (12) and swap it with the first element of the unsorted section.
   • Array after step 2: [11, 12, 25, 22, 64]
3. Repeat the process for all elements.
   • Final sorted array: [11, 12, 22, 25, 64]

Selection Sort Code in C

Below is the implementation of Selection Sort in C:

#include <stdio.h>

void selectionSort(int arr[], int n) {
    int i, j, min_idx, temp;

    for (i = 0; i < n - 1; i++) {
        min_idx = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // Swap the found minimum element with the first element
        temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int arr[10], n = 10, i;

    printf("Enter 10 numbers: ");
    for (i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    printf("\nArray before sorting: ");
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    selectionSort(arr, n);

    printf("\nArray after sorting: ");
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

Output Example:

Input:

Enter 10 numbers: 29 10 14 37 13 3 81 17 52 21

Output:

Array before sorting: 29 10 14 37 13 3 81 17 52 21
Array after sorting: 3 10 13 14 17 21 29 37 52 81

Use Cases of Selection Sort

1. Learning Algorithm: Due to its simplicity, Selection Sort is ideal for teaching basic sorting concepts.
2. Small Datasets: Suitable for small datasets where simplicity is preferred over efficiency.
3. Memory Constraints: Since it is an in-place sorting algorithm, it is ideal when memory usage needs to be minimized.

Advantages and Disadvantages

Advantages:

• Simple and easy to implement.
• Performs well on small datasets.
• Minimal memory usage.

Disadvantages:

• Inefficient for large datasets due to O(n²) time complexity.
• Not stable by default.

Conclusion

In this article, we discussed the Selection Sort algorithm and its implementation in C. Selection Sort is an excellent choice for small datasets where simplicity and minimal memory usage are required. While its O(n²) time complexity makes it unsuitable for large datasets, it remains a fundamental algorithm to understand the basics of sorting.

By mastering Selection Sort, developers gain a deeper understanding of sorting techniques, which can be applied to more advanced algorithms like Merge Sort and Quick Sort.

Frequently Asked Questions

Q1: Is Selection Sort stable? No, Selection Sort is not stable by default. However, it can be made stable with modifications.

Q2: What is the time complexity of Selection Sort? The time complexity of Selection Sort is O(n²) in the best, average, and worst cases.

Q3: What is the primary advantage of Selection Sort? Its simplicity and minimal memory usage make it a good choice for small datasets.

This concludes our article on implementing Selection Sort using C. For more insights on data structures and algorithms, stay tuned to developerIndian.com.