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

Network, do you do paraphrase

do you do paraphrase

What happens in cdma systems, Question: (a) Suppose that you are a comm...

Question: (a) Suppose that you are a communication engineer and you have to construct a mobile telephone network with bandwidth W = 4.2 MHz in each link. The data rate is

Initialization - network layer and routing , Initialization  Imagine t...

Initialization  Imagine that  all routers in our  sample internetwork  comes up  at the  same time. Each router sends a greeting packet to its  neighbours to find  out the  sta

Estimate of average delay deviation, Consider the procedure described for e...

Consider the procedure described for estimating average delay di. Suppose that u=0.1. Let r1-t1 be the most recent sample delay, let     r2 -t2 be the next most recent sample delay

List of many potential users of the intranet, List of many potential users ...

List of many potential users of the Intranet List of many potential users of the Intranet, both commonly used and not so commonly used. Company Documents o   Manu

What is multistation access unit, Multistation Access Unit (MAU) C...

Multistation Access Unit (MAU) Combines individual automatic switches May perhaps daisy chain to support more stations

What is dos, What is DoS? A do, or Denial-of-Service attack, is an atte...

What is DoS? A do, or Denial-of-Service attack, is an attempt to stop users from being able to access the internet or any other network services. Such attacks might be come in

State the list of protocols supported by the intranet, State the list of pr...

State the list of protocols supported by the Intranet The following is the list of protocols supported by the Intranet: ARP: Address resolution Protocol is used to resol

How does a switch use store and forward, The LAN switch copies the whole fr...

The LAN switch copies the whole frame into its onboard buffers and then looks up the destination address in its forwarding, or switching, table and verifies the outgoing interface

State the term - netbios and imap, State the term - NetBIOS and IMAP Ne...

State the term - NetBIOS and IMAP NetBIOS: Network Basic Input Output System is an API (applications programming interface) used with other programs to transmit messages betwee

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