Re: Worst-case Performance of Insertion Sort
- From: "eKo1" <berndlosert@xxxxxxxxxxxx>
- Date: 23 Feb 2007 07:49:16 -0800
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.
You may be right. However, in the worst and average case analysis
given in the text, the author is considering the condition of the
while loop as one comparison which is probably why I got confused.
.
- References:
- Worst-case Performance of Insertion Sort
- From: eKo1
- Re: Worst-case Performance of Insertion Sort
- From: GCRhoads
- Worst-case Performance of Insertion Sort
- Prev by Date: Re: Worst-case Performance of Insertion Sort
- 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
|
