# insertion sort

Page 1 of 1

## 4 Replies - 1004 Views - Last Post: 15 November 2009 - 06:41 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=139290&amp;s=f13cac96c8bdf94f0e2d9bf57cb4fdc4&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 MajorCS

Reputation: 0
• Posts: 5
• Joined: 15-November 09

# insertion sort

Posted 15 November 2009 - 06:18 PM

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;
}
}

Is This A Good Question/Topic? 0

## Replies To: insertion sort

### #2 KYA

• su wtf -am -i /doing/with/my/life

Reputation: 2979
• Posts: 19,033
• Joined: 14-September 07

## Re: insertion sort

Posted 15 November 2009 - 06:28 PM

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);
}

### #3 Dogstopper

Reputation: 2695
• Posts: 10,556
• Joined: 15-July 08

## Re: insertion sort

Posted 15 November 2009 - 06:28 PM

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

### #4 MajorCS

Reputation: 0
• Posts: 5
• Joined: 15-November 09

## Re: insertion sort

Posted 15 November 2009 - 06:34 PM

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.

### #5 KYA

• su wtf -am -i /doing/with/my/life

Reputation: 2979
• Posts: 19,033
• Joined: 14-September 07

## Re: insertion sort

Posted 15 November 2009 - 06:41 PM

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.