Odd-even transposition algorithem, Computer Networking

Assignment Help:

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


Related Discussions:- Odd-even transposition algorithem

Distance vector multicast routing protocol, DVMRP • Distance vector mu...

DVMRP • Distance vector multicast routing protocol: Distance vector multicast routing protocol are abbreviated as DVMRP. These protocols are suitable for small networks which

Determine the signal bandwidth and the amplitudes, 1. A low voltage digital...

1. A low voltage digital device has a low state of 0 V and a high state of 1.8 V. It generates a signal train of high pulses at a rate of 1 MHz, these pulses having a 10 ns width a

What are the working of software team, What are the working of software tea...

What are the working of software team The software team has to learn every bit of things related to computers. Since different users work on different platforms and application

Simple mail transfer protocol ( smtp), Simple Mail Transfer Protocol ( SMTP...

Simple Mail Transfer Protocol ( SMTP) SMTP is the principal  application layer protocol for  internet electronic  mail. It uses the reliable data transfer  service of TCP  to

How can you manage a network using a router, How can you manage a network u...

How can you manage a network using a router? Routers have built in console that lets you configure dissimilar settings, like security and data logging. You can allocate restric

Icmp process, Some of the ?elds of IP and ICMP datagrams will be ?xed, some...

Some of the ?elds of IP and ICMP datagrams will be ?xed, some will be settable by the application, and others will computed according to the situation. You must set all ?elds of th

Architecture of cisco ios software, Architecture of Cisco IOS software ...

Architecture of Cisco IOS software Cisco IOS might not  applications like ms word,multimedia softwares. It is mainly for switching data packet and concentrated on switching p

Show the congestion control in TCP, Q. Show the Congestion control in TCP? ...

Q. Show the Congestion control in TCP? Congestion control in TCP TCP assumes that the cause of lost segment is due to congestion in the network Retransmission of

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd