Selection sort is another simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the array and swapping it with the element at the beginning of the unsorted part. It continuously reduces the unsorted portion until the entire array is sorted.

Here's an explanation of the selection sort algorithm:

1. Start with an unsorted list of elements.

2. Find the minimum element in the unsorted part of the list.

3. Swap the minimum element with the first element in the unsorted part.

4. Move the boundary of the sorted part by one position to the right.

5. Repeat steps 2-4 until the entire array is sorted.

Here's an example implementation of the selection sort algorithm in C:

#include <stdio.h>

// Function to perform selection sort
void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;
    for (i = 0; i < n - 1; i++) {
        minIndex = i;

        for (j = i + 1; j < n; j++) {
            // Find the index of the minimum element in the unsorted part
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // Swap the minimum element with the first element in the unsorted part
        temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

// Function to print an array
void printArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Test the algorithm

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    selectionSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

In this example, the `selectionSort` function performs the selection sort algorithm on the given array. The `printArray` function is used to display the array before and after sorting. In the `main` function, we create an array, print it, call `selectionSort` to sort the array, and then print the sorted array.

The output will be:

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

As you can see, the selection sort algorithm repeatedly finds the minimum element and swaps it with the element at the beginning of the unsorted part, resulting in a sorted array.

Time Complexity

The time complexity of the Selection Sort algorithm is O(n^2) in all cases, including the worst, best, and average cases.

In the worst case, the Selection Sort algorithm needs to make comparisons and swaps for each element in the array. For each pass, it finds the minimum element from the remaining unsorted part of the array and performs a swap. This requires (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = O(n^2) comparisons and swaps.

In the best case, the input array is already sorted. However, even in the best case, the Selection Sort algorithm still needs to make comparisons for each element to verify that it is the minimum and perform swaps with the first element of the unsorted part. Thus, the time complexity remains O(n^2).

The average case time complexity of Selection Sort is also O(n^2) because, on average, it requires the same number of comparisons and swaps as in the worst case.

It's worth noting that Selection Sort is generally considered inefficient for large datasets. Other sorting algorithms, such as Quicksort or Mergesort, provide better average and worst-case time complexities. However, Selection Sort can be useful for small datasets or in scenarios where minimizing the number of swaps is important due to expensive swapping operations.

Space Complexity-

The space complexity of the Selection Sort algorithm is O(1) because it uses a constant amount of extra space.

Selection Sort operates directly on the input array without requiring additional data structures or dynamic memory allocation. It only uses a few variables to keep track of the indices and temporary values during the swapping process. Regardless of the size of the input array, the amount of extra space used by Selection Sort remains constant.

This makes Selection Sort advantageous in terms of space complexity when compared to sorting algorithms that require additional arrays or data structures for auxiliary operations. The space required by Selection Sort is minimal and does not depend on the input size.

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc