Detailed Explanation of Selection and Insertion Sort Algorithms in C

Selection Sort Algorithm Selection Sort is a simple and intuitive sorting algorithm. Its core idea is to find the minimum (or maximum) element from the unsorted elements in each round and swap it with the first element of the unsorted part until all elements are sorted.

Basic Principle of Selection Sort

Start from the first element of the array, treating it as the current minimum value
Traverse the remaining unsorted elements to find the true minimum value
Swap the found minimum value with the element at the current position
Move to the next position and repeat the above process until all elements are sorted

Implementation Code

Header File

#include <stdio.h>

Function to swap two integers

void swap(int* a, int* b) {    int temp = *a;    *a = *b;    *b = temp;}

Selection Sort Function

// arr: array to be sorted// n: number of elements in the arrayvoid selectionSort(int arr[], int n) {    int i, j, min_index;    // Outer loop: controls the boundary of sorted elements    // 0-i is the range of sorted elements    for (i = 0; i < n - 1; i++) {        // Assume the current position is the position of the minimum value        min_index = i;        // Inner loop: find the minimum value in the unsorted part        // i-n is the range of unsorted elements        for (j = i + 1; j < n; j++) {            // If a smaller element is found, update the minimum index            if (arr[j] < arr[min_index]) {                min_index = j;            }        }        // Swap the found minimum value with the element at the current position        swap(&arr[min_index], &arr[i]);    }}

Function to print array elements

void printArray(int arr[], int size) {    for (int i = 0; i < size; i++) {        printf("%d ", arr[i]);    }    printf("\n");}

Main Function

int main() {    int arr[] = { 66, 55, 12, 22, 11 };    int n = sizeof(arr) / sizeof(arr[0]);    printf("Original array: ");    printArray(arr, n);    selectionSort(arr, n);    printf("Sorted array: ");    printArray(arr, n);    return 0;}

Code Analysis

swap Function: This function swaps two integers using pointers and serves as an auxiliary function in sorting.
selectionSort Function:

Outer Loopi runs from 0 ton-1, indicating the current position to be determined (the end of the sorted part).
Finding the Minimum Value The inner loopj starts fromi+1 to find the index of the minimum value in the unsorted part (elements afteri).
Swapping Elements The found minimum value (arr[min_index]) is swapped with the element at the current position (arr[i]), makingarr[i] the last element of the sorted part.

Time Complexity: Regardless of the initial state of the array, selection sort requires n(n-1)/2 comparisons, thus the time complexity is alwaysO(n²).

Characteristics of Selection Sort

Advantages

Simple implementation, clear logic, and easy to understand.
Fewer swaps (at mostn-1 times), which is advantageous in scenarios where the cost of swapping is high (e.g., sorting large structures).

Disadvantages

Fixed time complexity of O(n²), which is inefficient for handling large datasets.
It is an unstable sorting algorithm (for example, in the case of[2, 2, 1]<code>, the relative positions of the two 2s will change after sorting) (the first 2 is swapped to the third position).

Applicable Scenarios

Selection sort is suitable for teaching demonstrations, sorting small datasets, or scenarios sensitive to the cost of swapping operations. For large datasets, more efficient algorithms (such as quicksort, mergesort, etc.) are usually preferred.

Insertion Sort Algorithm

Core Principle

Sorted Interval Initially contains only the first element of the array (a single element is considered sorted by default).
Unsorted Interval Contains all remaining elements in the array.

Note: The indices of the unsorted interval are all greater than those of the sorted interval. That is, the sorted part is in front, and the unsorted part is behind.

The core steps of the algorithm are:

Take the first element from the unsorted interval (called the “element to be inserted”).
Find the appropriate position for this element in the sorted interval (so that it remains sorted after insertion).
Move all elements in the sorted interval that are greater than the element to be inserted one position back to make room for the element to be inserted.
Place the element to be inserted in the found appropriate position.
Repeat the above steps until the unsorted interval is empty, and the entire array is sorted.

Detailed explanation of the second step, assuming the sorted interval is 0-i, and the unsorted interval is i-n.

At this point, the element taken out is [i+1].

Elements from 0 to i are all sorted, so we only need to compare from i with the value of i+1. If it is greater, we move it back until we find a position p that is less than i+1.

At this point, [0,p] are all less than i+1; elements from p to i have all moved back one position, i.e., from p+1 to i.

The position becomes from p+2 to i+1; and i+1 is inserted at position p+1.

Code Implementation

// arr: array to be sorted// n: number of elements in the arrayvoid insertionSort(int arr[], int n) {    int i, key, j;    // Outer loop: starts from the second element (the first element is considered sorted)    for (i = 1; i < n; i++) {        // Take out the current element to be inserted        key = arr[i];        // The position i is now free        // Start comparing from the last element of the sorted part        j = i - 1;        // Inner loop: move elements greater than key back        while (j >= 0 && arr[j] > key) {            // Move the element back            arr[j + 1] = arr[j];            // Continue comparing forward            j--;        }        // Insert key into the correct position        arr[j + 1] = key;    }}

Time Complexity

Worst case (array completely reversed): O (n²)
Best case (array already sorted): O (n) (only needs to traverse once, no need to move elements)
Average case: O (n²)