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

Show the ip address representation, Q. Show the IP Address Representation? ...

Q. Show the IP Address Representation? IP Addressing IP Address Representation Binary notation - IP address is displayed as 32 bits Dotted-decimal notation -

Explain categorization according to pipeline configuration, Categorization ...

Categorization according to pipeline configuration According to the configuration of a pipeline, the below categories are recognized under this classification: Unifunct

Explain semantic web , What the Semantic Web is? Ans) The Semantic Web ...

What the Semantic Web is? Ans) The Semantic Web is a vision, that thinks to join together dispersed bits of data on the internet, very much like web pages are presently joined

Which layers are user support layers, Which layers are user support layers?...

Which layers are user support layers? Three layers are come under user support layer:- a. Session Layer b. Presentation Layer and c. Application Layer

Dns cache poisoning, DNS cache poisoning The DNA cache poisoning gener...

DNS cache poisoning The DNA cache poisoning generally refers to the process of maintaining or developing the false information, in the cache of DNS server. This process refers

State the difference between byte streams and message, State the difference...

State the difference between Byte streams and message Byte streams and message are different. In a message stream, network keeps track of the message boundaries. In a byte stre

Determine about the security systems, Determine about the Security Systems ...

Determine about the Security Systems If the company intends to connect to the Internet, then it should pay great attention to the configuration of firewalls. Just as no one wo

Concept of data transmission, Overview of Data transmission network model ...

Overview of Data transmission network model A network is a combination of hardware and software that sends data from one location to another. The hardware consists of the physi

What is passive topology , When the computers on the network basically list...

When the computers on the network basically listen and receive the signal, they are referred to as passive due to they don't amplify the signal in any way.

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