Re: Worst-case Performance of Insertion Sort
- From: "GCRhoads" <rhoads@xxxxxxxxxxxxxxx>
- Date: 22 Feb 2007 11:43:24 -0800
On Feb 20, 11:58 pm, "eKo1" <berndlos...@xxxxxxxxxxxx> wrote:
Here is the version of insertion sort I'm using:
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
The while loop will iterate at most i - 1 times, i = 2 to N, and this
happens when newElement is less than all the elements of list[1...(i -
1)]. This can only happen when the list is in decreasing order. I'm
asked to find another class of input that produces the worst-case
behaviour of this algorithm but I just can't think of another one. Any
hints or tips as to what that other input class might look like?
Yes, the worst case for the above code occurs only when the list
is in reverse order.
Perhaps the author means the worst case number of comparisons
(comparisons of array elements); these comparisons occur only in
the loop test. The apparent semantics of the test "(location >= 1
AND list[location] > newElement)" means that the second half will
not be tested when the first half is false (i.e. when location < 1).
Consequently, the worst case number of comparisons occurs precisely
when each successive element is small enough that it will get
compared to the first element in the list **regardless** of the result
of that comparison. For example, the following two lists will elicit
the maximum number of comparisons for the above code.
1 9 8 7 6 5 4 3 2
9 8 7 6 5 4 3 2 1
But there will be fewer data movements for the first list because
the inner loop will execute one fewer time per iteration of the outer
loop.
.
- Follow-Ups:
- Re: Worst-case Performance of Insertion Sort
- From: eKo1
- Re: Worst-case Performance of Insertion Sort
- References:
- Worst-case Performance of Insertion Sort
- From: eKo1
- Worst-case Performance of Insertion Sort
- Prev by Date: Re: Do Write Once TM's Halt?
- Next by Date: Re: Worst-case Performance of Insertion Sort
- Previous by thread: Re: Worst-case Performance of Insertion Sort
- Next by thread: Re: Worst-case Performance of Insertion Sort
- Index(es):
Relevant Pages
|
