Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 0 down vote favorite
1

I have trouble understanding how to calculate the depth of a sorting network on $n$ inputs.

For example, in case of selection sort, we have:

$\qquad \displaystyle D(n)=D(n-1)+2\\\qquad D(2)=1$

which leads to

$\qquad \displaystyle D(n)=2n-3=\Theta(n)$

I have confirmed that the depth of selection sort is equal to $2n-3$ by hand, but I can't understand how the recurrence $D(n)=D(n-1)+2$ is derived.

share|improve this question
3  
Welcome! I am confused as to what is being asked here. Are you asking how to read a recurrence, or why this recurrence applies to selection sort? Do you have a sorting network implementation of selection sort at hand, or are you talking about the algorithm and its recursion depth? – Raphael♦ Jul 29 '12 at 21:45
1  
Have you tried drawing a picture of the selection-sort sorting network? What does it look like? – JeffE Jul 30 '12 at 2:54

migrated from cstheory.stackexchange.com Jul 29 '12 at 20:22

1 Answer

up vote 0 down vote

For selection/bubble sorting network algorithms, the main tricky point is that "some operations are overlapped" or in other words because of pipeling! (it is shown in figure below) You can find more information in these lecture notes by Rolf Karlsson.

This is the reason why the time complexity is linear! enter image description here

share|improve this answer
I'm not sure pipelining (as seen in processors?) is a good analogy here; it's more like perfect parallelism, isn't it? – Raphael♦ Feb 3 at 1:23
@Raphael: I changed the picture which shows the pipeline concept better! – Reza Feb 3 at 3:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.