Lets define a function to insert an integer into a non-decreasing sorted array. See the function void insert(int x[], int& length, int& number_to_be_inserted). What it does, is that it starts scanning the array from the end - the maximum number (as it is a non-decreasing array). Whenever it finds that the number_to_be_inserted is less than than the number in the array, it shifts the position of that number in the array towards right. Otherwise it inserts the new number in that position. This principle can be applied to Sort an array. We will start with an one element array. It is obviously sorted. We will pick up the next element and put it in the right place of the sorted array. Thus we get a two element sorted array. Similarly we can get a sorted array of size n.
In the following code snippet, the Method I is the Algorithm with a separate Insert Function. The method II is the sorting algorithm with the Insert function inbuilt into it.
The source code of Method I can be found here.
The output of this program is as given below
The source code of Method II can be found here.
The output of this program is given below
Hope you enjoy this study.
No comments:
Post a Comment