#include <stdio.h>
int main()
{
int arr[100], n, i, j, Temp;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
// Insertion Sort
for(i = 1; i < n; i++)
{
Temp = arr[i];
j = i - 1;
// Move elements greater than key one position ahead
while(j >= 0 && arr[j] > Temp)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = Temp;
}
printf("Sorted array: ");
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CgppbnQgbWFpbigpCnsKICAgIGludCBhcnJbMTAwXSwgbiwgaSwgaiwgVGVtcDsKCiAgICBwcmludGYoIkVudGVyIG51bWJlciBvZiBlbGVtZW50czogIik7CiAgICBzY2FuZigiJWQiLCAmbik7CgogICAgcHJpbnRmKCJFbnRlciAlZCBlbGVtZW50czpcbiIsIG4pOwogICAgZm9yKGkgPSAwOyBpIDwgbjsgaSsrKQogICAgewogICAgICAgIHNjYW5mKCIlZCIsICZhcnJbaV0pOwogICAgfQoKICAgIC8vIEluc2VydGlvbiBTb3J0CiAgICBmb3IoaSA9IDE7IGkgPCBuOyBpKyspCiAgICB7CiAgICAgICAgVGVtcCA9IGFycltpXTsKICAgICAgICBqID0gaSAtIDE7CgogICAgICAgIC8vIE1vdmUgZWxlbWVudHMgZ3JlYXRlciB0aGFuIGtleSBvbmUgcG9zaXRpb24gYWhlYWQKICAgICAgICB3aGlsZShqID49IDAgJiYgYXJyW2pdID4gVGVtcCkKICAgICAgICB7CiAgICAgICAgICAgIGFycltqICsgMV0gPSBhcnJbal07CiAgICAgICAgICAgIGotLTsKICAgICAgICB9CiAgICAgICAgYXJyW2ogKyAxXSA9IFRlbXA7CiAgICB9CgogICAgcHJpbnRmKCJTb3J0ZWQgYXJyYXk6ICIpOwogICAgZm9yKGkgPSAwOyBpIDwgbjsgaSsrKQogICAgewogICAgICAgIHByaW50ZigiJWQgIiwgYXJyW2ldKTsKICAgIH0KCiAgICByZXR1cm4gMDsKfQo=