Le 02/08/2010 17:46, Invisible a écrit :
> Insert-sort is an O(N^2) algorithm. It takes O(N) time to work out where
> the next item needs to go, and it takes O(N) time to move all the data
> down one slot in order to make room to insert the new item. And you have
> to do this sequence of operations exactly N times. Hence, O(N^2).

> Now, suppose I built a machine containing special RAM chips, where
> there's a special signal I can send that copies the contents of every
> memory register in a specified range into the next register along.
> Assuming all these shifts happen concurrently, I just made shifting an
> O(1) operation. (!!)

Congratulations,
that the difference between a linked list to store your data, and an
indexed array.

> 
> Depending on how wide your array slots are, you might need to perform
> several hardware-level shifts. But since the slot size is by definition
> fixed, that's still O(1).

If instead of a single value, the cells of your array contains also a
pointer to the next value in the list, you could sort it without moving
the value, and only updating the "next" index field.

That approach is trading memory (an additional explicit next-index value
for each cell) for better performance.

Notice: the size of the values to sort might be bigger than the value of
the next-index field, which only need to be able to store about the size
of the array in term of cells.


-- 
A: Because it messes up the order in which people normally read text.<br/>
Q: Why is it such a bad thing?<br/>
A: Top-posting.<br/>
Q: What is the most annoying thing on usenet and in e-mail?

Post a reply to this message