Re: Worst-case Performance of Insertion Sort

On Feb 21, 9:58 am, "eKo1" <berndlos...@xxxxxxxxxxxx> wrote:
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?

let's see:

Set1:
9 8 7 6 5 1 2 3 4 (descending+ascending)

Set2:
1 9 2 8 3 7 4 6 5 (interleaved)

Set3:
Completely randomized input (NOT producing nearly sorted output)

Basically worst-case bound is "asymptotic" and will occur only when
the input is sorted in decreasing order.
Insertion sort works extremely well on "nearly sorted inputs" the rest
of the combinations all *tend to* O(n^2) (asymptotically). Have a look
at the text of "Introduction to algorithms: Cormen" for a better
insight

Regards,

Nupul

.

Relevant Pages

  • Re: direct calculation of prime numbers
    ... According to McCanney, the ... algorithm uses only addition and subtraction and can be taught ... It hints at secrets of immense importance, ...
    (comp.arch)
  • Re: random data
    ... Since my algorithm for creating random numbers failed the test completely, could anybody direct me to some source or ... give me some hints for creating a simple, ... At the moment I use the TSC of the processor and two system hooks for entropy. ... SHA512 to hash the data. ...
    (sci.crypt)
  • Re: How could I program this algorithm?
    ... to give me some hints though? ... I guess you're best chance is asking the original authors if they ... cial problem that the likelyhood of finding someone here who also ... implemented the algorithm might be rather small... ...
    (comp.programming)
  • IDEA algorithm
    ... is there any website out there, where i can learn something about the IDEA ... algorithm step by step? ... probably some example c-code or anything else? ... any hints are appreciated! ...
    (sci.crypt)
  • Re: Delete all items in the list
    ... It is useless for predicting how fast that algorithm will run, ... For what it's worth, for very small lists, the while...remove algorithm is ... insertion sort for small lists, only kicking off a high-overhead but O ...
    (comp.lang.python)