Analyse av sortering ved innsetting
inserton the elements at indices . Just as each call to
indexOfMinimumtook 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.
insertand 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 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, the value being inserted is less than every element in the subarray to its left. When we call
insertthe first time, . 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
inserttakes just constant time. Suppose that every call of
inserttakes constant time. Because there are calls to
insert, if each call takes time that is some constant , then the total time for insertion sort is , which is , not .
insertcause every element in the subarray to slide one position to the right? Can each call to
insertcause no elements to slide? The answer is yes to both questions. A call to
insertcauses 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 . 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.
insertcauses 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 . This situation occurs if the array starts out already sorted, and so an already-sorted array is the best case for insertion sort.
inserton a subarray of 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.
insertslides at most 17 elements, and the time for one call of
inserton a subarray of elements would be at most . Over all calls to
insert, the running time would be , which is , just like the best case. So insertion sort is fast when given an almost-sorted array.
- Worst case: .
- Best case: .
- Average case for a random array: .
- "Almost sorted" case: .