Number of comparisons in an insertion sort

  • Thread starter Thread starter nicnicman
  • Start date Start date
  • Tags Tags
    Sort
Click For Summary

Discussion Overview

The discussion revolves around the number of comparisons made by the insertion sort algorithm when sorting a list in reverse order, specifically the list n, n-1, ...2, 1. Participants explore the implications of this ordering on the sorting process and the resulting comparisons.

Discussion Character

  • Homework-related
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • Some participants express confusion about the notation used to describe the list, questioning the transition from n, n-1 to 2, 1.
  • Others clarify that the list is in reverse order and will be sorted into ascending order.
  • A participant suggests that the number of comparisons could be n - 1, but later retracts this, indicating it refers to passes rather than comparisons.
  • Another participant proposes that since the list is in descending order, insertion sort would make n - 1 comparisons to sort it into ascending order.
  • One participant provides a specific example with a smaller list (3, 2, 1) to illustrate their reasoning about the number of comparisons.
  • Another participant suggests that the example is too short to draw definitive conclusions and encourages testing with a longer list.
  • Some participants express uncertainty about their answers and seek further clarification or confirmation from others.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the exact number of comparisons made by insertion sort for the given list. There are competing views on whether the number of comparisons is n - 1 or if it varies based on the specific implementation or understanding of the sorting process.

Contextual Notes

Participants express uncertainty regarding the implications of the list's ordering and the definitions of comparisons versus passes in the context of insertion sort.

nicnicman
Messages
132
Reaction score
0

Homework Statement


How many comparisons does the insertion sort use to sort the list n, n-1, ...2, 1?


Homework Equations





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.
 
Physics news on Phys.org
nicnicman said:

Homework Statement


How many comparisons does the insertion sort use to sort the list n, n-1, ...2, 1?


Homework Equations





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 ?
 
Yes, but usually there is an order like 1, 2, . . . , n. I guess I just don't see the order here.
 
SO you feel that 1, 2, ... n is ordered but the reverse is not?
 
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
 
Oh, okay. I see now. Thanks.
 
So would the answer be n - 1?
 
Never mind it would be n - 1 passes, not comparisons.
 
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
nicnicman said:
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?
 
  • #11
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.
 
Last edited:
  • #12
I'm still not entirely sure of my answer and I was hoping someone would offer some advice.

Thanks for any suggestions.
 
  • #13
nicnicman said:
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?
 
  • #14
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.
 

Similar threads

Maximum number of comparisons required to merge two sorted files
  • · Replies 7 ·
Replies
7
Views
6K
Max Comparisons in Binary Search: Understanding Efficiency and Implementation
  • · Replies 2 ·
Replies
2
Views
3K
Comp Sci Expected number of collisions for hashing with chaining
  • · Replies 1 ·
Replies
1
Views
2K
What is the running time of this algorithm?
  • · Replies 12 ·
Replies
12
Views
5K
Algorithm Complexity: Sorted Arrays into Sorted Array
  • · Replies 12 ·
Replies
12
Views
4K
Doubt about quicksort algorithm
  • · Replies 2 ·
Replies
2
Views
2K
Problem on Probability -- Hash Table & Collisions
  • · Replies 6 ·
Replies
6
Views
3K
Looping Program Problem -- create and fill in two vector arrays....
  • · Replies 22 ·
Replies
22
Views
2K
How Do You Calculate Insertion Loss in a T-Network?
  • · Replies 5 ·
Replies
5
Views
3K
C: Sorting and searching data from separated files
  • · Replies 4 ·
Replies
4
Views
2K