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.

Write Your Message!

Name

Email id

Message

Verfication Code

User Account

All Pages

What is Oscillating Sort?, Data Structure & Algorithms

Related Discussions:- What is Oscillating Sort?

Data Warehousing, Assume you are in the insurance business. Find two exampl...

Pseudocodes, how to write a pseudo code using Kramer''s rule

Design a binary search tree, Binary Search Tree usage: Write a progra...

Determine the algorithm for z-buffer method, Algorithm for Z-Buffer Method ...

State cmy model, CMY Model The cyan, magenta, yellow (CMY) colour mode...

Space and time complexity, why the space increase in less time programs

Use of asymptotic notation in the study of algorithm, Q. What is the need o...

Unification algorithm, i want to write code for unification algorithm with ...

Dgsd, Ask question #sdgsdgsdginimum 100 words accepted#

Usage of linked lists for polynomial manipulation, Q. Establish the usage o...

Write Your Message!

Featured Services

Online Tutoring

Project Development

Exam Preparation

Course Help

Assignment Help

Popular Subjects

Assured A++ Grade

Academics

Major Subjects

Majors

Get In Touch

TERMS & POLICIES

HELP & SUPPORT