/*
 * Author  : Amit Dutta <amitdutta4255@gmail.com>
 * Date    : 08 Feb 2026
 * Repo    : https://github.com/notamitgamer/bsc
 * License : MIT License (See the LICENSE file for details)
 */

/* Implement the Insertion Sort algorithm shown in Figure 13.3 on a set of 25 numbers.
*/

/* Let Us C, Chap- 13 (Arrays), Qn No.: B(d) */

/* This file is auto-generated by a bot. */
/* This code is not compiled; it is for reference only. */


#include <stdio.h>
#include <math.h>
#include <stdlib.h>

void insertion_sort(int *, int);

int main()
{
    int arr[25], i;

    printf("Enter 25 integers for Insertion Sort:\n");
    for (i = 0; i < 25; i++)
    {
        scanf("%d", &arr[i]);
    }

    insertion_sort(arr, 25);

    printf("\nSorted Array:\n");
    for (i = 0; i < 25; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

void insertion_sort(int *arr, int n)
{
    int i, j, key;
    for (i = 1; i < n; i++)
    {
        key = arr[i];
        j = i - 1;

        /* Move elements of arr[0..i-1], that are greater than key,
           to one position ahead of their current position */
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}