Re: Worst-case Performance of Insertion Sort
- From: "eKo1" <berndlosert@xxxxxxxxxxxx>
- Date: 23 Feb 2007 08:00:57 -0800
InsertionSort( list, N )
list the elements to be put into order
N the number of elements in the list
for i = 2 to N do
newElement = list[ i ]
location = i - 1
while (location >= 1) and (list[ location ] > newElement) do
// move the larger elements out of the way
list[ location + 1 ] = list[ location ]
location = location - 1
end while
list[ location + 1 ] = newElement
end for
In the average case analysis of the algorithm above, would it make
sense to determine the average amount of iterations done by the while
loop?
The while loop will iterate at most i - 1 times so the average amount
of iterations is (0 + 1 + 2 + ... + i - 1) / i = (i - 1) / 2. Since i
varies from 2 to N, the total amount of iterations of the while loop,
on average, is
sum (i = 2 to N) (i - 1) / 2 = sum(i = 1 to N - 1) i / 2 = N(N - 1) /
4 = O(N^2)
which is right. What do you think?
.
- References:
- Worst-case Performance of Insertion Sort
- From: eKo1
- Worst-case Performance of Insertion Sort
- Prev by Date: Re: Worst-case Performance of Insertion Sort
- Next by Date: A restricted case of graph coloring, is this a known problem?
- Previous by thread: Re: Worst-case Performance of Insertion Sort
- Next by thread: CEX - Context-Free Expression Filter
- Index(es):
Relevant Pages
|
