Odd-even transposition algorithem, Computer Networking

Algorithm: Odd-Even Transposition

//Input: N numbers that are in the unsorted form

//Assume that element bi is assigned to pi

for I=1 to N

{

If (I%2 != 0) //i.e Odd phase

{

For j=1,3,5,7,..................2*n/2-1

{

Apply compare-exchange (Pj, Pj+1) //Operation is executed in parallel

}

}

Else // Even phase

{

For j=2,4,6,8..................2*(n-1)/2-1

{

} I++

}

 Apply compare-exchange(Pj, Pj+1) //Operation is executed in parallel

}

Let us take an example and illustrate the odd-even transposition algorithm.

Analysis

The above algorithm needs one „for loop? starting from I=1 to N, i.e. N times and for every value of I, one „for loop? of J is implemented in parallel. Thus, the time difficulty of the algorithm is O (n) as there are total n phases and each phase executes either odd or even transposition in O(1) time.

2417_Example.png

                                                                             Example

Posted Date: 3/2/2013 6:53:00 AM | Location : United States







Related Discussions:- Odd-even transposition algorithem, Assignment Help, Ask Question on Odd-even transposition algorithem, Get Answer, Expert's Help, Odd-even transposition algorithem Discussions

Write discussion on Odd-even transposition algorithem
Your posts are moderated
Related Questions
Explain in detail about wireless network Think about unseen terminal problem. Imagine a wireless network consist of five stations, A through E, such that each one them is in r

Interconnection Network An interconnection network is designed for transferring data between two processors in a Multi-stage network. Memory bottleneck is a fundamental limitat

Difference among the communication and transmission? Transmission is a physical movement of information and concern issues as bit polarity, synchronization, clock etc. Commu

Question : (a) Explain the ‘RAD' methodology with a suitable diagram. (b) One of the activities to be performed during Rapid Application Development is Rapid Business Analys

bus topology disadvantage?

Reliability Reliability  is the measure of how  often  a network is usable. MTSF( Mean time  Between Failure) is a measure of the average time  a component  is expected to ope

Categorization according to kind of instruction and data According to types of instruction and data subsequent types are identified under this classification: Scalar Pi

explain the three classification of operation research


What is EGP (Exterior Gateway Protocol)? It is the protocol the routers in neighboring autonomous systems use to recognize the set of networks that can be reached within or by