The Insertion sort algorithm
Sort by repeatedly taking the next item and inserting it into the final data structure in its proper order with respect to items already inserted. It inserts each element of the array into its proper position.
Run time is O(n^2) because of moves. Insertion sort is an example of an incremental algorithm; it builds the sorted sequence one number at a time. Insertion sort is stable, i.e. the relative order of equal keys is not changed, provided that you are careful about scanning the sorted region from right to left.
using namespace std;
int main()
{
int array[9]={4,3,5,1,2,0,7,9,4};
for(int i=1; i<9; i++)
{
int index = array[i];
int dec = i;
while(dec>0 && array[dec-1]>=index)
{
array[dec]=array[dec-1];
–dec;
}
array[dec]=index;
}
for(int i=0; i<9;i++)
cout << array[i] << endl;
}
Hey thanks!
I just copied your program. Tweaked it a little, made it possible to enter 10 numbers to be sorted. It worked!!!!
However I’m still confused and puzzled why the software prompts that it encountered an error and needs to shut down after it has executed the program.
Anyone who can help me?
Could someone explain.
I’m studying Information Technology, first year, it would be so much help if you could unravel this “sort of a mystery”.
Thanks a LOT!!!
Did you try it in Dev C , Restart your computer and recompile your program again, try to add before the last } return 0;
I guess it is something related to your computer, not to the code above because it works just fine!
you either need to add a “return 0;” to the end of the code, or change the “int main()”
to “void main()” the reason it is erroring out is because the runtime is expecting to get a return value of type int. do either of those items and it should work fine.
note: some compilers throw a fit if you don’t return an expected data type.
It has linear complexity in the best-case.
Good post!