what is selection sort in c

Selection sort is a simple and efficient sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list. The algorithm repeatedly selects the smallest (or largest) element from the unsorted portion of the list and swaps it with the first element of the unsorted part. This process is repeated for the remaining unsorted portion until the entire list is sorted.

Here are the key features of selection sort in C:

• The algorithm repeatedly selects the smallest (or largest) element from the unsorted portion of the list and swaps it with the first element of the unsorted part.
• The algorithm works by dividing the array into two parts - one that will be sorted and the other that will be unsorted.
• It is an in-place algorithm as it swaps the elements in the list itself. It does not require an extra list or array to sort the elements.
• The time complexity of the selection sort is the same in all cases. At every step, you have to find the minimum element and put it in the right place. The minimum element is not known until the end of the array is not reached. The time complexity of selection sort is O(n^2).
• The space complexity of selection sort is O(1) because an extra variable temp is used.

Here is an example of selection sort in C:

#include <stdio.h>

void selectionSort(int arr[], int n) {
    int i, j, min_idx;
    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;
            }
        }
        if (min_idx != i) {
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
    for (int i=0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

Output:

Sorted array:
11 12 22 25 64

Advantages of selection sort:

• Simple and easy to understand.
• Works well with small datasets.

Disadvantages of selection sort:

• Selection sort has a time complexity of O(n^2), which makes it inefficient for large datasets.
• It is not suitable for real-time applications where data is continuously changing.