Register to reply 
Number of comparisons in an insertion sort 
Share this thread: 
#1
Dec1012, 06:55 PM

P: 136

1. The problem statement, all variables and given/known data
How many comparisons does the insertion sort use to sort the list n, n1, ......2, 1? 2. Relevant equations 3. The attempt at a solution Insertion sort compares every element with every other element in the list, but I'm unsure what this question is asking. Why does it jump from n, n1 to 2, 1? Thanks for any suggestions. 


#2
Dec1012, 08:05 PM

PF Gold
P: 6,486




#3
Dec1012, 08:10 PM

P: 136

Yes, but usually there is an order like 1, 2, . . . , n. I guess I just don't see the order here.



#4
Dec1012, 08:27 PM

PF Gold
P: 6,486

Number of comparisons in an insertion sort
SO you feel that 1, 2, ... n is ordered but the reverse is not?



#5
Dec1012, 08:28 PM

Mentor
P: 21,397

n, n1, ......2, 1 means the list in reversed order. After the sort routine is finished, the order will be 1, 2, 3, ..., n  1, n



#6
Dec1012, 08:32 PM

P: 136

Oh, okay. I see now. Thanks.



#7
Dec1012, 08:38 PM

P: 136

So would the answer be n  1?



#8
Dec1012, 08:39 PM

P: 136

Never mind it would be n  1 passes, not comparisons.



#9
Dec1012, 08:45 PM

P: 136

Actually, after thinking about a bit more, wouldn't the insertion sort also make n  1 comparisons since the list is already in descending order.
Sorry for all the posts. 


#10
Dec1012, 08:49 PM

Mentor
P: 21,397




#11
Dec1012, 08:55 PM

P: 136

Right. So, if you had a list 3, 2, 1 the comparisons would go like this:
Comparison 1. compare 2 and 3, we have 2, 3, 1 Comparison 2. compare 1 and 2 , we have 1, 2, 3 Done, with 2 comparisons, or n  1. Please, correct me if I'm wrong. 


#12
Dec1112, 12:09 AM

P: 136

I'm still not entirely sure of my answer and I was hoping someone would offer some advice.
Thanks for any suggestions. 


#13
Dec1112, 12:21 AM

Mentor
P: 21,397




#14
Dec1112, 12:25 AM

P: 136

That was the exact list I tried it with first. I only used a smaller list here for simplification. Anyway, with the longer list I got the same results: n1.



#15
Dec1112, 10:09 AM

Mentor
P: 21,397

Take a look at this wiki page: http://en.wikipedia.org/wiki/Insertion_sort



Register to reply 
Related Discussions  
Java Insertion sort problem  Engineering, Comp Sci, & Technology Homework  3  
Analysis of the Binary Insertion Sort algorithm  Engineering, Comp Sci, & Technology Homework  0  
Using the Insertion Sort algorithm on a linked list  Engineering, Comp Sci, & Technology Homework  1  
Number Base Comparisons  Linear & Abstract Algebra  34  
Quicksort/Insertion sort combo  Engineering, Comp Sci, & Technology Homework  0 