1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number of comparisons in an insertion sort

  1. Dec 10, 2012 #1
    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.
     
  2. jcsd
  3. Dec 10, 2012 #2

    phinds

    User Avatar
    Gold Member
    2016 Award

    What jump? Do you not understand what the ellipsis stands for ?
     
  4. Dec 10, 2012 #3
    Yes, but usually there is an order like 1, 2, . . . , n. I guess I just don't see the order here.
     
  5. Dec 10, 2012 #4

    phinds

    User Avatar
    Gold Member
    2016 Award

    SO you feel that 1, 2, ... n is ordered but the reverse is not?
     
  6. Dec 10, 2012 #5

    Mark44

    Staff: Mentor

    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
     
  7. Dec 10, 2012 #6
    Oh, okay. I see now. Thanks.
     
  8. Dec 10, 2012 #7
    So would the answer be n - 1?
     
  9. Dec 10, 2012 #8
    Never mind it would be n - 1 passes, not comparisons.
     
  10. Dec 10, 2012 #9
    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.
     
  11. Dec 10, 2012 #10

    Mark44

    Staff: Mentor

    But you want the list to be in ascending order, right?
     
  12. Dec 10, 2012 #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: Dec 10, 2012
  13. Dec 11, 2012 #12
    I'm still not entirely sure of my answer and I was hoping someone would offer some advice.

    Thanks for any suggestions.
     
  14. Dec 11, 2012 #13

    Mark44

    Staff: Mentor

    Your list is too short to really give you any insight. How about if the list is 5, 4, 3, 2, 1?
     
  15. Dec 11, 2012 #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.
     
  16. Dec 11, 2012 #15

    Mark44

    Staff: Mentor

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Number of comparisons in an insertion sort
Loading...