Array114. Дан массив $$A$$ размера $$N$$ ($$\leq 6$$). Упорядочить его по возрастанию методом сортировки простыми вставками: сравнить элементы $$A_1$$ и $$A_2$$ и, при необходимости меняя их местами, добиться того, чтобы они оказались упорядоченными по возрастанию; затем обратиться к элементу $$A_3$$ и переместить его в левую (уже упорядоченную) часть массива, сохранив ее упорядоченность; повторить этот процесс для остальных элементов, выводя содержимое массива после обработки каждого элемента (от $$2$$-го до $$N$$-го). При выполнении описанных действий удобно использовать прием «барьера», записывая очередной элемент перед его обработкой в дополнительный элемент массива $$A_0$$.
Решение:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <stdio.h> int main(void) { int a[20]; int temp; int n; printf("N: "); scanf("%i",&n); int i; for (i=0; i<n; ++i){ printf("a[%i] : ",i+1); scanf("%i",&a[i]); } if (a[0]>a[1]){ temp=a[0]; a[0] =a[1]; a[1] =temp; } int i2,i3; for (i=2; i<=n-1; ++i){ temp=a[i]; for (i2=i-1;i2>=0;--i2) if (temp<a[i2]) a[i2+1]=a[i2]; else { break; } a[i2+1]=temp; for (i3=0; i3<n;++i3) printf(" %i: %i\n",i3+1,a[i3]); printf("\n"); } return 0; } |
Решение с использованием a[0], как барьерный элемент.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include <stdio.h> int main(void) { int a[20]; int n; printf("N: "); scanf("%i",&n); int i; for (i=1; i<=n; ++i){ printf("a[%i] : ",i); scanf("%i",&a[i]); } if (a[1]>a[2]){ a[1]+=a[2]; a[2]=a[1]-a[2]; a[1]-=a[2]; } int i2,i3; for (i=3; i<=n; ++i){ a[0]=a[i]; for (i2=i-1;i2>=0;--i2) if (a[0]<a[i2]) a[i2+1]=a[i2]; else { a[i2+1]=a[0]; break; } for (i3=0; i3<=n;++i3) printf(" %i: %i\n",i3,a[i3]); } return 0; } |
Другие задачи из раздела Array можно посмотреть здесь.
Комментарии: