Thread: Insertion sort!

Uhm.. well first of all I would prefer NO spaces in the scanf, and your code does what you want, but it organize the array from left(biggest) to right(smallest).
you may also use some of the algorithms for insertion sort, such as MAX_SORT / BUBBLE_SORT / BUCKET_SORT...
NOTE: you should consider that the n value should not be more than 100, cuz of the array, or use malloc

Originally Posted by ConanCoder

Uhm.. well first of all I would prefer NO spaces in the scanf, and your code does what you want, but it organize the array from left(biggest) to right(smallest).
you may also use some of the algorithms for insertion sort, such as MAX_SORT / BUBBLE_SORT / BUCKET_SORT...
NOTE: you should consider that the n value should not be more than 100, cuz of the array, or use malloc

Thanks a lot!!!! But could you elaborate about not using spaces in scanf..

Originally Posted by shan2014

Thanks a lot!!!! But could you elaborate about not using spaces in scanf..

it's NO BIG DEAL, I mean the program runs very normal, but with spaces in scanf in the code you did (for example), u should enter the values like this " 3" without space u can enter it like this "3" without any spaces. and sometimes it's good to use spaces, for example when you enter a char scanf(" %c", &str), to avoid the space that pops once the program runs... both ways work eventually, but I dunnu why I prefer no spaces xD

Originally Posted by ConanCoder

it's NO BIG DEAL, I mean the program runs very normal, but with spaces in scanf in the code you did (for example), u should enter the values like this " 3" without space u can enter it like this "3" without any spaces.

That's actually not correct. A space (any whitespace character) in a scanf string does not read a literal space character. It tells scanf to skip any and all sequential white space (space, newline, tab, etc) characters from that point in the stream. Also, the %d format specifier (and all the number format specifiers and %s) tell scanf to skip sequential whitespace before scanning in the actual number/string. Thus, the space in the format string is redundant, but does not in any way affect how the program runs or how the input must be entered.

Originally Posted by ConanCoder

and sometimes it's good to use spaces, for example when you enter a char scanf(" %c", &str), to avoid the space that pops once the program runs... both ways work eventually, but I dunnu why I prefer no spaces xD

You're correct that putting a space before %c is often the right thing to do, but I have no idea what you mean by avoiding "the space that pops once the program runs". That is not very clear/accurate, and I'm not sure anyone but you really knows what it means. What you are referring to is the newline that often gets left in the input buffer when the user presses enter after inputting a character, which the space helps get rid of.

Originally Posted by shan2014

Can anyone validate if my code implements the concept of insertion sort. The program is executing successfully. Just need a verification!

It does not implement insertion sort.

You should have a good idea of this yourself if you have any understanding of how insertion sort is supposed to work, and if you actually wrote the code yourself. I strongly suggest you read up on insertion sort (link), then revisit your code.

Originally Posted by anduril462

It does not implement insertion sort.

You should have a good idea of this yourself if you have any understanding of how insertion sort is supposed to work, and if you actually wrote the code yourself. I strongly suggest you read up on insertion sort (link), then revisit your code.

I have rectified my code and this is the new one

Code:

for(i=1;i<n;i++)
	{
		for(j=i-1;j>=0;j--)
             { 
				if(a[i]<a[j] )
				{temp=a[j];
				a[j]=a[i];
				a[i]=temp;i--;}
			 }
	}printf("\nInsertion Sort:");
	for(i=0;i<n;i++)
	printf(" %d",a[i]);
getch();
return 0;
}

Originally Posted by iMalc

You have implemented what most people here call "Substitution Sort".
It's correct too, although j could start at i+1 rather than just i.

Ah! okay..

What you have basically implements insertion sort, but it's inefficient, mostly because you keep doing i--; whenever you swap, causing you to reprocess the array without actually swapping/inserting any new elements into the right order/position. Re-read the Wikipedia article I linked you to, and study carefully the first bit of pseudo code.

One other thing: a function should do one thing and do it well. A sort function should sort data, but should not print it. Create a separate print function for that. This is called "separation of concerns". Also, strive to keep your functions modular and reusable. This way you can print the list before and after you sort, and you can reuse it inside your sort function for debugging if you need to.