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
Lemurs match scent of a friend to sound of her voice
Repeated self-healing now possible in composite materials
'Heartbleed' fix may slow Web performance
phinds
phinds is online now
#2
Dec10-12, 08:05 PM
PF Gold
phinds's Avatar
P: 5,674
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 online now
#4
Dec10-12, 08:27 PM
PF Gold
phinds's Avatar
P: 5,674

Number of comparisons in an insertion sort


SO you feel that 1, 2, ... n is ordered but the reverse is not?
Mark44
Mark44 is offline
#5
Dec10-12, 08:28 PM
Mentor
P: 20,937
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 offline
#10
Dec10-12, 08:49 PM
Mentor
P: 20,937
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 offline
#13
Dec11-12, 12:21 AM
Mentor
P: 20,937
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 offline
#15
Dec11-12, 10:09 AM
Mentor
P: 20,937
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