Number of comparisons in an insertion sort


by nicnicman
Tags: comparisons, insertion, number, sort
nicnicman
nicnicman is offline
#1
Dec10-12, 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, n-1, ......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, n-1 to 2, 1?

Thanks for any suggestions.
Phys.Org News Partner Science news on Phys.org
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes
phinds
phinds is offline
#2
Dec10-12, 08:05 PM
PF Gold
phinds's Avatar
P: 5,705
Quote Quote by nicnicman View Post
1. The problem statement, all variables and given/known data
How many comparisons does the insertion sort use to sort the list n, n-1, ......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, n-1 to 2, 1?

Thanks for any suggestions.
What jump? Do you not understand what the ellipsis stands for ?
nicnicman
nicnicman is offline
#3
Dec10-12, 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.

phinds
phinds is offline
#4
Dec10-12, 08:27 PM
PF Gold
phinds's Avatar
P: 5,705

Number of comparisons in an insertion sort


SO you feel that 1, 2, ... n is ordered but the reverse is not?
Mark44
Mark44 is online now
#5
Dec10-12, 08:28 PM
Mentor
P: 21,063
n, n-1, ......2, 1 means the list in reversed order. After the sort routine is finished, the order will be 1, 2, 3, ..., n - 1, n
nicnicman
nicnicman is offline
#6
Dec10-12, 08:32 PM
P: 136
Oh, okay. I see now. Thanks.
nicnicman
nicnicman is offline
#7
Dec10-12, 08:38 PM
P: 136
So would the answer be n - 1?
nicnicman
nicnicman is offline
#8
Dec10-12, 08:39 PM
P: 136
Never mind it would be n - 1 passes, not comparisons.
nicnicman
nicnicman is offline
#9
Dec10-12, 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.
Mark44
Mark44 is online now
#10
Dec10-12, 08:49 PM
Mentor
P: 21,063
Quote Quote by nicnicman View Post
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.
But you want the list to be in ascending order, right?
nicnicman
nicnicman is offline
#11
Dec10-12, 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.
nicnicman
nicnicman is offline
#12
Dec11-12, 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.
Mark44
Mark44 is online now
#13
Dec11-12, 12:21 AM
Mentor
P: 21,063
Quote Quote by nicnicman View Post
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.
Your list is too short to really give you any insight. How about if the list is 5, 4, 3, 2, 1?
nicnicman
nicnicman is offline
#14
Dec11-12, 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: n-1.
Mark44
Mark44 is online now
#15
Dec11-12, 10:09 AM
Mentor
P: 21,063
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