Running Time of an Insertion SortDate: 08/06/99 at 11:24:45 From: Elizabeth Thomas Subject: Running time of an insertion sort Here's my question: "Insertion sort" is the procedure that sorts an array of n numbers as follows: Search through the entire array, find the smallest element, and place it in the first position in the array. Then find the next-smallest number, and place it in the second position of the array. Continue until the array is sorted. Write and solve a recurrence formula for the running time of an insertion sort. Which is better, insertion sort or merge-sort? I tried to sort A[1...n], by recursively sorting A[1...n-1] and inserting the final element, but I must be doing something wrong. Thanks for your help; it is greatly appreciated. Date: 08/07/99 at 21:52:52 From: Doctor Tom Subject: Re: Running time of an insertion sort Hi Elizabeth, Here's how to do it. First, figure out what you're counting. In this case, let's look at the number of numbers you have to examine to complete the sort. If there's only one number in the list, no work is required, so zero numbers need to be examined, right? If there are two numbers in the list, you examine both to find the smaller (that's two examinations) but then you're done, because you know the other is larger. That's two total examinations. If there are three numbers, you look at all three to find the smallest, and after you have that, you're still faced with an insertion sort of the remaining two numbers, which we know from the previous paragraph requires 2 more examinations: 5 total. Et cetera. For n items, you need n examinations plus the number of examinations to sort n-1 items. Here's how it looks: Items to sort Examinations 1 0 2 2 3 3+2 4 4+3+2 5 5+4+3+2 : : For the analysis of a merge sort, let's just look at a sort of 2^n items. To sort 1 item (1 = 2^0) requires zero examinations. To sort 2^n items, you need to do 2 merge-sorts of 2^(n-1) and then look (at worst) at 2^n items to do the final merge sort: Items to sort Examinations 1 0 = 0 2 2 = 2 4 4 + 2*2 = 8 8 8 + 2*8 = 24 16 16 + 2*24 = 64 : : Notice that for a merge sort this is an upper bound. If you do a merge and you finish one list, you don't need to look at the others in the list. - Doctor Tom, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/