Register to reply

Number of comparisons in an insertion sort

by nicnicman
Tags: comparisons, insertion, number, sort
Share this thread:
nicnicman
#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
FIXD tells car drivers via smartphone what is wrong
Team pioneers strategy for creating new materials
Team defines new biodiversity metric
phinds
#2
Dec10-12, 08:05 PM
PF Gold
phinds's Avatar
P: 6,333
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
#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
#4
Dec10-12, 08:27 PM
PF Gold
phinds's Avatar
P: 6,333
Number of comparisons in an insertion sort

SO you feel that 1, 2, ... n is ordered but the reverse is not?
Mark44
#5
Dec10-12, 08:28 PM
Mentor
P: 21,286
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
#6
Dec10-12, 08:32 PM
P: 136
Oh, okay. I see now. Thanks.
nicnicman
#7
Dec10-12, 08:38 PM
P: 136
So would the answer be n - 1?
nicnicman
#8
Dec10-12, 08:39 PM
P: 136
Never mind it would be n - 1 passes, not comparisons.
nicnicman
#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
#10
Dec10-12, 08:49 PM
Mentor
P: 21,286
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
#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
#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
#13
Dec11-12, 12:21 AM
Mentor
P: 21,286
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
#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
#15
Dec11-12, 10:09 AM
Mentor
P: 21,286
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