User Account

All Pages

What is Oscillating Sort?, Data Structure & Algorithms

Assignment Help:
For the Oscillating sort to be applied, it is necessary for the tapes to be readable in both directions and able to be quickly reversed. The oscillating sort is superior to the polyphase for more than 6 tape units. The oscillating sort derives its name from the fact that the sort is performed by oscillating between distributions and merging. Rather than distribute all the inputs to the tapes and then commence merging, some of the inputs are distributed, then merged, and then more are distributed. The sort works exactly if the number of initial runs is a power of T - 1 where T is the number of working tapes used in the sort. When the number of initial runs is not a power of T -1 it is assumed that dummy runs are present to make up the difference.

Principle: Distribute all the inputs to the tapes and then commence merging. Some of the inputs are distributed, and then merged, and then more are distributed. This process is repeated till a sorted list is obtained.

Algorithm:

1. Let A be the given list of N unsorted elements.

2. Let T be the number of working tapes and R be the number of runs.

3. Initialize an index variable I ß 2.

4. Distribute T - 1 runs one in each working tape leaving T[I] empty.

5. Merge the above runs and put the new run in T[I].

6. Increment the value of I.

7. Repeat steps 4 to 6 till all inputs are exhausted.

8. The runs of equal length are merged and placed in empty tape.

In this example, five tapes are used with four of them considered as the working tapes. The first one simply holds the input. Step 2 shows the first distribution phase in which records with values 14, 26, and 3 are distributed on tapes 3, 4 and 5 respectively. In step 3 these are merged backward and the run (3 14 26) is placed on tape 2. Once more distribution is done in step 4 leaving 15 on tape 2, 6 on tape 4, and 35 on tape 5. These are merged again and placed on tape 3. Step 6 is the final distribution phase placing 19, 28 and 22 on tapes 2, 3 and 5 respectively. In step 7 these are merged and placed on tape 4. At this point the inputs are exhausted and have three runs of equal length. These three runs are merged and placed on tape 5.

Related Discussions:- What is Oscillating Sort?

Algorithm, write an algorithm for the gpa of six students

write an algorithm for the gpa of six students

Boar corloring, Board coloring , C/C++ Programming

Board coloring , C/C++ Programming

What are stored and derived attributes, What are stored and derived attribu...

What are stored and derived attributes?  Stored attributes: The attributes kept in a data base are called stored attributes.  Derived attributes: The attributes that are

Implementation of queue by using a single linked list, Q. Perform implement...

Q. Perform implementation of a queue using a singly linked list L. The operations INSER and DELETE should take O (1) time.

What are the properties of colour, Properties of colour Colour descript...

Properties of colour Colour descriptions and specifications generally include three properties: hue; saturation and brightness. Hue associates a colour with some position in th

Need help with working out. I dont really get it, Suppose there are exactly...

Suppose there are exactly five packet switches (Figure 4) between a sending host and a receiving host connected by a virtual circuit line (shown as dotted line in figure 4). The tr

Depth first traversal, A depth-first traversal of a tree visits a nodefirst...

A depth-first traversal of a tree visits a nodefirst and then recursively visits the subtrees of that node. Similarly, depth-first traversal of a graph visits a vertex and then rec

What is Polyphase Sort, One of the best known methods for external sorting ...

One of the best known methods for external sorting on tapes is the polyphase sort. Principle: The basic strategy of this sort is to distribute ordered initial runs of predetermi

Hashing, what is hashing? what are diffrent method of hashing?

what is hashing? what are diffrent method of hashing?

Depth of complete binary tree, What will be depth do , of complete binary t...

What will be depth do , of complete binary tree of n nodes, where nodes are labelled from 1 to n with root as node and last leaf node as node n

Write Your Message!

Captcha
Order Assignment

Featured Services

Order Now

Popular Subjects

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!

Submit Assignment

Academics

Major Subjects

Majors

Get In Touch

whatsapp: +91-977-207-8620

Phone: +91-977-207-8620

Email: [email protected]

TERMS & POLICIES

HELP & SUPPORT

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