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
Final pieces to the circadian clock puzzle found
A spray-on light show on four wheels: Darkside Scientific
How an ancient vertebrate uses familiar tools to build a strange-looking head
phinds
#2
Dec10-12, 08:05 PM
PF Gold
phinds's Avatar
P: 6,486
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,486
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,397
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,397
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,397
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,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