[MajorCS]

I am implementing an insertion sort and it works fine yet i want to find the number of comparisons made during sorting here is my method.

	public void insertionSort(int theArray[],int n)
	{
		
		   for (int i = 1; i < n; i++)
		   {
			   int j = i;
			   int key = theArray[i];
			   
			   while ((j>0 && theArray[j-1] > key))
			   {
					theArray[j] = theArray[j-1];
					j--;
				   // comparison++ not sure if this is correct?
			   }
			   theArray[j] = key;
			}
	 }

[KYA]

Yeah, that's how you would do it.

	public void insertionSort(int theArray[],int n)
	{
	   int comparisons = 0;
		   for (int i = 1; i < n; i++)
		   {
			   int j = i;
			   int key = theArray[i];
			   
			   while ((j>0 && theArray[j-1] > key)) //each iteration of this loop is a comparison
			   {
					theArray[j] = theArray[j-1];
					j--;
				   comparisons++;
			   }
			   theArray[j] = key;
			}
		 System.out.println("# of comparisons made: " + comparisons);
	 }

[Dogstopper]

I would say that you are correct because the while loop is actually testing to see where it goes. The first for loop merely dictates where the number goes. Nice job.

Dang KYA! I posted this way quickly, but you still beat me! At least we agree, otherwise I would still look stupid!

This post has been edited by Dogstopper: 15 November 2009 - 06:36 PM

[MajorCS]

Thanks guys , i did not want to try out a 200 numbers array with pen and paper just to find out if i have the right comparison number lol

appreciate it.

[KYA]

The only thing I could think of is this: the last condition the while loop examines that turns out to be false is still a comparison, depending on your frame of reference.