Skip to lab content

UNIT 05 · Sorting and Searching

Insertion sort in ascending order

EXERCISE 05EC173 sample runs

THE SYLLABUS QUESTION

What you need to solve

Write a C program that sorts the given array of integers using insertion sort in ascending order.
Input format & conventions

Array size n (1–100), followed by n integers between -1,000,000 and 1,000,000.

UNDERSTAND THE IDEA

Explanation

Maintain a sorted prefix. Take the next element as key, shift larger prefix elements right, and place the key in the resulting gap.

The key must be saved before shifting so its value is not lost. Testing j >= 0 before reading a[j] prevents access before the array.

PLAN BEFORE CODING

Algorithm

  1. Read the array.
  2. Start with the second element; the first is already a sorted prefix.
  3. Save the current key and shift preceding larger values right.
  4. Insert the key at j + 1.
  5. Repeat and display ascending order.

SEE THE CONTROL FLOW

Flowchart

Follow the arrows from Start. Diamonds ask a question; labeled arrows show the answer. A returning arrow repeats a loop. Function internals are grouped where needed; later input checks follow the rules in the program.

Flowchart for Insertion sort in ascending order: input, decisions, processing, output and loop paths

On a phone, scroll sideways to read the diagram at full size. Open full-size flowchart ↗

C17

Complete C program

Download .c
#include <stdio.h>
#define MAX_SIZE 100

int readArray(int a[], int *n) {
    if (scanf("%d", n) != 1 || *n < 1 || *n > MAX_SIZE) return 0;
    for (int i = 0; i < *n; ++i)
        if (scanf("%d", &a[i]) != 1 || a[i] < -1000000 || a[i] > 1000000) return 0;
    return 1;
}

void printArray(const int a[], int n) {
    for (int i = 0; i < n; ++i) printf("%s%d", i == 0 ? "" : " ", a[i]);
    putchar('\n');
}

void insertionSort(int a[], int n) {
    for (int i = 1; i < n; ++i) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            --j;
        }
        a[j + 1] = key;
    }
}

int main(void) {
    int a[MAX_SIZE], n;
    if (!readArray(a, &n)) { puts("Invalid input."); return 1; }
    insertionSort(a, n);
    printf("Ascending: "); printArray(a, n);
    return 0;
}
Open in compiler ↗

Code loads into the existing compiler. Enter the sample input there; sign-in and execution rules stay the same.

Compile and run locally
gcc -std=c17 insertion-sort-ascending.c -o lab
./lab

On Windows, run .\lab.exe after compiling with GCC. The interest program requires the math library where applicable.

FOLLOW THE VALUES

Dry run

Step / stateOperationResult
Start5 | 1 4 2Prefix [5] is sorted
Insert 11 5 | 4 2Shift 5 right
Insert 41 4 5 | 2Shift 5 right
Insert 21 2 4 5Shift 5 and 4 right

CHECK THE BEHAVIOR

Sample input & output

Each output below was produced by compiling and running this exact program. Input values are entered in the stated order; the examples do not print input prompts.

Sample 1

INPUT 
4
5 1 4 2
OUTPUT
Ascending: 1 2 4 5

Sample 2

INPUT 
5
3 -1 3 0 -2
OUTPUT
Ascending: -2 -1 0 3 3

Sample 3

INPUT 
1
7
OUTPUT
Ascending: 7

Common mistakes

  • Store key before shifting elements.
  • The j >= 0 test must be evaluated before a[j] > key.

WHY THIS GROWTH RATE?

Time and space complexity

Time O(n²) worst case and O(n) best case; O(1) additional space.

In reverse order, inserting the second value shifts one element, the third shifts two, and so on. Total shifts are 1 + 2 + … + (n − 1) = n(n − 1)/2, giving O(n²) worst-case time.

For already sorted input, each key fails the shift condition immediately. Only n − 1 short insertion steps occur, so best-case time is O(n). A saved key and counters are the only extra storage; the sort is in place and uses O(1) auxiliary space.

Big-O describes how work grows as the stated input quantity grows; fixed factors and lower-order terms are omitted. The analysis treats fixed-width arithmetic as constant cost and the published limits as practical safety bounds.