Read n numbers in increasing order and a number x. Insert x into the array so that it stays in increasing order, by moving the larger numbers one place right. Then print all n + 1 numbers.
What to build
An insertion that keeps a sorted array sorted.
Requirements
- Move every number larger than
xone place to the right, starting from the end. - Write
xinto the gap. - Print all
n + 1numbers.
Input
The first line has n (0 ≤ n ≤ 100). The second line has the n numbers in increasing order. The third line has x.
Output
The n + 1 numbers on one line, separated by spaces.
Constraints
0 ≤ n ≤ 100.
Example
Input:
5
10 20 30 40 50
25
Output:
10 20 25 30 40 50
Why it works
Shifting from the end copies each value before it is overwritten, and the gap that is left is exactly where x belongs.
Examples
Example 1 · Input
5 10 20 30 40 50 25
Expected output
10 20 25 30 40 50
Example 2 · Input
3 1 2 3 0
Expected output
0 1 2 3
Hints
Hint 1
Start at the last item and move left while the item is bigger than x.
Hint 2
Move each bigger item one place right: a[i + 1] = a[i].
Hint 3
Write x into the gap at a[i + 1], and remember that n grows by one.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n, x;
int a[101];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
scanf("%d", &x);
int i = n - 1;
while (i >= 0 && a[i] > x) {
a[i + 1] = a[i];
i--;
}
a[i + 1] = x;
n++;
for (int k = 0; k < n; k++) {
if (k > 0) printf(" ");
printf("%d", a[k]);
}
printf("\n");
return 0;
}