Hovedinnhold
Kurs: (Informatikk > Enhet 1
Leksjon 5: Sortering ved innsettingAnalyse av sortering ved innsetting
Like selection sort, insertion sort loops over the indices of the array. It just calls . Just as each call to
insert
on the elements at indices indexOfMinimum
took an amount of time that depended on the size of the sorted subarray, so does each call to insert
. Actually, the word "does" in the previous sentence should be "can," and we'll see why.Let's take a situation where we call elements, all might have to slide over by one position. Rather than counting exactly how many lines of code we need to test an element against a key and slide the element, let's agree that it's a constant number of lines; let's call that constant . Therefore, it could take up to lines to insert into a subarray of elements.
insert
and the value being inserted into a subarray is less than every element in the subarray. For example, if we're inserting 0 into the subarray [2, 3, 5, 7, 11], then every element in the subarray has to slide over one position to the right. So, in general, if we're inserting into a subarray with Suppose that upon every call to . The second time, . The third time, . And so on, up through the last time, when . Therefore, the total time spent inserting into sorted subarrays is
insert
, the value being inserted is less than every element in the subarray to its left. When we call insert
the first time, That sum is an arithmetic series, except that it goes up to rather than . Using our formula for arithmetic series, we get that the total time spent inserting into sorted subarrays is
Using big-Θ notation, we discard the low-order term and the constant factors and 1/2, getting the result that the running time of insertion sort, in this case, is .
Can insertion sort take less than time? The answer is yes. Suppose we have the array [2, 3, 5, 7, 11], where the sorted subarray is the first four elements, and we're inserting the value 11. Upon the first test, we find that 11 is greater than 7, and so no elements in the subarray need to slide over to the right. Then this call of calls to , then the total time for insertion sort is , which is , not .
insert
takes just constant time. Suppose that every call of insert
takes constant time. Because there are insert
, if each call takes time that is some constant Can either of these situations occur? Can each call to . What would it mean for every element to be less than the element to its left? The array would have to start out in reverse sorted order, such as [11, 7, 5, 3, 2]. So a reverse-sorted array is the worst case for insertion sort.
insert
cause every element in the subarray to slide one position to the right? Can each call to insert
cause no elements to slide? The answer is yes to both questions. A call to insert
causes every element to slide over if the key being inserted is less than every element to its left. So, if every element is less than every element to its left, the running time of insertion sort is How about the opposite case? A call to . This situation occurs if the array starts out already sorted, and so an already-sorted array is the best case for insertion sort.
insert
causes no elements to slide over if the key being inserted is greater than or equal to every element to its left. So, if every element is greater than or equal to every element to its left, the running time of insertion sort is What else can we say about the running time of insertion sort? Suppose that the array starts out in a random order. Then, on average, we'd expect that each element is less than half the elements to its left. In this case, on average, a call to elements would slide of them. The running time would be half of the worst-case running time. But in asymptotic notation, where constant coefficients don't matter, the running time in the average case would still be , just like the worst case.
insert
on a subarray of What if you knew that the array was "almost sorted": every element starts out at most some constant number of positions, say 17, from where it's supposed to be when sorted? Then each call to elements would be at most . Over all calls to , which is , just like the best case. So insertion sort is fast when given an almost-sorted array.
insert
slides at most 17 elements, and the time for one call of insert
on a subarray of insert
, the running time would be To sum up the running times for insertion sort:
- Worst case:
. - Best case:
. - Average case for a random array:
. - "Almost sorted" case:
.
If you had to make a blanket statement that applies to all cases of insertion sort, you would have to say that it runs in time. You cannot say that it runs in time in all cases, since the best case runs in time. And you cannot say that it runs in time in all cases, since the worst-case running time is .
This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.
Ønsker du å delta i samtalen?
Ingen innlegg enda.