Worst-case Performance of Insertion Sort
- From: "eKo1" <berndlosert@xxxxxxxxxxxx>
- Date: 20 Feb 2007 20:58:21 -0800
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?
.
- Follow-Ups:
- Re: Worst-case Performance of Insertion Sort
- From: eKo1
- Re: Worst-case Performance of Insertion Sort
- From: GCRhoads
- Re: Worst-case Performance of Insertion Sort
- From: NUPUL
- Re: Worst-case Performance of Insertion Sort
- Prev by Date: Re: Do Write Once TM's Halt?
- Next by Date: Re: Doubt
- Previous by thread: Doubt
- Next by thread: Re: Worst-case Performance of Insertion Sort
- Index(es):