Insertion Sort Question
This problem is really confusing me.
Consider the following list:
12, 38, 45, 50, 55, 5, 30
The first five keys are in order. To move 5 to its proper position using the insertion sort as described in this chapter, exactly how many key comparisons are executed?
The chapter does not do a very good job of explaining what key comparisons are in this case. My guess is there will be 1 key comparison, because it will compare 5 to 12, and realize that 5 < 12. Am I wrong? Can someone help explain this to me?
Consider the following list:
12, 38, 45, 50, 55, 5, 30
The first five keys are in order. To move 5 to its proper position using the insertion sort as described in this chapter, exactly how many key comparisons are executed?
The chapter does not do a very good job of explaining what key comparisons are in this case. My guess is there will be 1 key comparison, because it will compare 5 to 12, and realize that 5 < 12. Am I wrong? Can someone help explain this to me?
How does insertion sort work? Using this knowledge, you can tell how many comparisons will be made to move 5 to it's place.
Since most sorting algorithms need to compare the elements of a list in order to determine their place in the list, key comparisons refer to the method by which an element of the array/list is compared to another to determine it's new position
Read the article on insertion sort on Wikipedia:
http://en.wikipedia.org/wiki/Insertion_sort
Since most sorting algorithms need to compare the elements of a list in order to determine their place in the list, key comparisons refer to the method by which an element of the array/list is compared to another to determine it's new position
Read the article on insertion sort on Wikipedia:
http://en.wikipedia.org/wiki/Insertion_sort
So I believe I am right in my thinking. Basically, in insertion sort it will copy the number, place the number in a temp variable, copy the numbers before it, then place it in the correct order. I'm thinking it will look at 12 first, so it will make one comparison to 12, and notice it is smaller and 5 will be placed before it. Am I wrong?
Yes that is wrong. Hint, the values after 5 are already sorted. If you read the wikipedia page on insertion sort you will be able to understand how this sorting method works
Topic archived. No new replies allowed.