Given a set of n numbers in an array, we would like to arrange them in a non-descending order (increasing sorted sequence). For this, you are asked to implement the following algorithm.
At some intermediate stage, assume that we have arranged A[0], A[1].. A[i] in a sorted sequence. Next we consider x = A[i+1] (if i n). Our goal is to identify an index j, such that A[j] x A[j+1]. This can be done by scanning A[i], A[i-1] etc till we find the appropriate j. All elements to the right of A[j] must be shifted by one position to accommodate A[i+1]. Alternately you can move one element at a time when you are searching for A[j] (If A[i] is larger than A[i+1] then exchange their positions etc)
Sorting is complete when A[0] ...A[n] is sorted - in every phase we are increasing the length of the sorted sequence by one starting with one element A[0] which is sorted trivially.
For generating input use the following method for producing random numbers
#include < stdlib.h >
srand(seed); /*seed is any positive integer */
You can generate now random numbers in the range 0 .. 999 by calling rand() % 1000. Every time you make a call rand() % 1000, it returns a number in the range 0 .. 999
Both srand() and rand() are library functions available in stdlib.h