Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one element at a time. It iterates through the input array, moving each element to its correct position relative to the already sorted elements.

A[0] ≤ . . . ≤ A[j] < A[j + 1] ≤ . . . ≤ A[i – 1]    |   A[i] . . . A[n – 1] 
smaller than or equal to A[i]        greater than A[i]

Algorithm

Algorithm InsertionSort(A[0..n − 1])
// Sorts a given array by insertion sort
// Input: An array A[0..n − 1] of n orderable elements
// Output: Array A[0..n − 1] sorted in nondecreasing order

for i ← 1 to n - 1 do
    v ← A[i]
    j ← i - 1
    while j ≥ 0 and A[j] > v do
        A[j + 1] ← A[j]
        j ← j - 1
    A[j + 1] ← v

Write a C++ program to implement insertion sort

#include <iostream>

void insertionSort(int A[], int n) {
    for (int i = 1; i < n; i++) {
        int v = A[i];
        int j = i - 1;
        
        // Move elements of A[0..i-1], that are greater than v,
        // to one position ahead of their current position
        while (j >= 0 && A[j] > v) {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = v;
    }
}

// Function to print the array
void printArray(int A[], int n) {
    for (int i = 0; i < n; i++) {
        std::cout << A[i] << " ";
    }
    std::cout << std::endl;
}

int main() {
    int A[] = {12, 11, 13, 5, 6};
    int n = sizeof(A) / sizeof(A[0]);

    std::cout << "Original array: ";
    printArray(A, n);

    insertionSort(A, n);

    std::cout << "Sorted array: ";
    printArray(A, n);

    return 0;
}

Output

Original array: 12 11 13 5 6 
Sorted array: 5 6 11 12 13 

Sort the given list of numbers using insertion sort: 45,2,20,6,3

Selection sort

Selection sort is a straightforward sorting algorithm that works by repeatedly selecting the minimum (or maximum) element from the unsorted portion of the array and swapping it with the element at the beginning of the unsorted portion. This process gradually builds up the sorted portion of the array from left to right.

Algorithm

ALGORITHM SelectionSort(A[0..n − 1])
// Sorts a given array by selection sort
// Input: An array A[0..n − 1] of orderable elements
// Output: Array A[0..n − 1] sorted in nondecreasing order

for i ← 0 to n − 2 do
    min ← i
    for j ← i + 1 to n − 1 do
        if A[j] < A[min]
            min ← j
    swap A[i] and A[min]

Write a C++ program to implement selection sort.

#include <iostream>

void selectionSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_index = i;

        // Find the index of the minimum element in the unsorted portion
        for (int j = i + 1; j < n; j++) {
            if (A[j] < A[min_index]) {
                min_index = j;
            }
        }

        // Swap the minimum element with the first element of the unsorted portion
        if (min_index != i) {
            std::swap(A[i], A[min_index]);
        }
    }
}

// Function to print the array
void printArray(int A[], int n) {
    for (int i = 0; i < n; i++) {
        std::cout << A[i] << " ";
    }
    std::cout << std::endl;
}

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

    std::cout << "Original array: ";
    printArray(A, n);

    selectionSort(A, n);

    std::cout << "Sorted array: ";
    printArray(A, n);

    return 0;
}

Output

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

Sort the given list of numbers using selection sort: 45,2,20,6,3