Sort n numbers into increasing order with insertion sort. After inserting each item a[i] (for i from 1 to n - 1), print the whole array. This is a common exam question.
What to build
An insertion sort that shows the array after every insertion.
Requirements
- Lift out each item from index 1 onwards.
- Move larger items one place right, and put the item in the gap.
- Print the whole array after each insertion.
Input
The first line has n (2 ≤ n ≤ 20). The second line has the n numbers.
Output
n - 1 lines: the array after each insertion, numbers separated by spaces.
Constraints
2 ≤ n ≤ 20.
Example
Input:
5
12 11 13 5 6
Output:
11 12 13 5 6
11 12 13 5 6
5 11 12 13 6
5 6 11 12 13
Why it works
After inserting index i, the first i + 1 items are sorted. Each printed line shows the sorted part growing by one.
Examples
Example 1 · Input
5 12 11 13 5 6
Expected output
11 12 13 5 6 11 12 13 5 6 5 11 12 13 6 5 6 11 12 13
Example 2 · Input
2 2 1
Expected output
1 2
Hints
Hint 1
For i from 1 to n - 1: save key = a[i], move bigger items of a[0 .. i-1] one place right, and put key in the gap.
Hint 2
Print the whole array after each i, not only at the end.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
void print(int a[], int n) {
for (int i = 0; i < n; i++) {
if (i > 0) printf(" ");
printf("%d", a[i]);
}
printf("\n");
}
int main(void) {
int n;
int a[20];
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;
print(a, n);
}
return 0;
}