Question

Write a C program to sort an array of size n using insertion sort. Show the

intermediate steps for each iteration by displaying currently which

element is picked from unsorted sublist and placed in which position in

the sorted sublist.

Answer 1

#include <stdio.h>
#include <stdlib.h>
#define N 10

void print_arr(int a[], int n) {
    int i;
    for (i=0; i<n; i++) {
        printf("%2d ", a[i]);
    }
    printf("\n");
}

void print_step(int a[], int n, int i, int j) {
    int k;


    for (k=0; k<i; k++) {
        printf("   ");
    }
    printf(" ^\n");

    for (k=0; k<j; k++) {
        printf("   ");
    }
    if (i==j) {
        printf(" |\n");
    }
    else {
        printf(" +");
        for (k=j; k<i-1; k++) {
            printf("---");
        }
        printf("--+\n");
    }
    for (k=0; k<j; k++) {
        printf("   ");
    }
    printf(" v\n");


    print_arr(a, n);
}


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


        print_step(a, n, i, j);
        
    }
}


void gen_arr(int a[], int n) {
    int i;


    for (i=0; i<n; i++) {
        a[i] = rand() % 100;
    }
}


int main() {
    int A[N];


    gen_arr(A, N);
    printf("Unsorted array:\n");
    print_arr(A, N);


    sort(A, N);


    printf(":Sorted array\n");


    return 0;
}