Insertion Sort

Lab C Intermediate 20 points

Sort n integers with insertion sort and print the array after each insertion.

Input

Line 1: n. Line 2: n integers.

Output

n − 1 lines.

Example

Input

5
4 3 5 1 2

Output

Sample input available Sample output available

Editor

Hints

Shift larger elements right, then drop the key into the gap.

Solution explanation

Insertion sort is fast for small or nearly sorted arrays.

Show solution

#include <stdio.h>

int main() {
    int n, a[100];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
        for (int k = 0; k < n; k++) printf("%d%s", a[k], k < n - 1 ? " " : "\n");
    }
    return 0;
}

Output

Answer