Posted by Weasel on 1999-07-17
Ng Oon Keat wrote:
>
> Hi. Do you guys know what is the best case and worst case for Insertion
> sort, Merge Sort and Heap sort ? Besides, what are the O-Notation for these
> sorting algorithm ? Thanks
>
Insertion Sort:
best case:
the dataset is already sorted or is reverse-sorted. Which of them is the
best case depends on your implementation of insertion sort. if adding at
the end is cheap, i.e. O(1) as in an array then already sorted is good,
if adding at the "beginning" of your data structure is cheap, as in a
simple linear list then reverse sorted is good.
In this case the time complexity of insertion sort is O(n) since you
have to go through n of your items and insert them at the right position
(which is as mentioned O(1) ) we have n * O(1) -> O(n)
worst case:
the dateset is sorted the other way as in the best case. You have to
move all previous handled items or go through your entire list to find
the right position for the new item. So the time complexity to insert
one new item in the already sorted list is O(k) when k elements are
already in the list.
now we sum this up and have sum(k) with k in 1..n which gives us
(n+1)*n/2 or something like this. so it's O(n^2).
average case:
in order to find the place an item goes to we have to go through 50% or
the already handled items. so we have (as in the worst case) sum(k/2)
with k in 1..n. -> O(n^2)
Heap Sort:
don;t know about best and worst case but the average compelxity is O(n
log n)
Merge sort:
I don't know but I think there are several ways of doing merge sort. In
general it is much slower than the two others sort algorithms since it
is a so called external sort algorithm while the other two are internal.
(external: your data is stored on an external storage and your internal
(fast) storage is that samll that you can only have some of the data in
it. internal: all the data is stored in an internal (fast) storage)
PS: I don't claim this is right. This is what I remember from one of my
programming courses at the university. Don't have the papers any more.
--
Weasel http://www.cosy.sbg.ac.at/~ppalfrad/
main(i){putchar(354603184>>(i-1)*5&31|!!(i<6)<<6)&&main(++i);}
The software said Windows95 or better, so I got Linux...
Previous post | Next post | Timeline | Home