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?

Tower of hanoi problem., Write an algorithm for getting solution to the Tow...

Write an algorithm for getting solution to the Tower's of Hanoi problem. Explain the working of your algorithm (with 4 disks) with appropriate diagrams. Ans: void Hanoi(int

Technique for direct search, Technique for direct search is    Hashing ...

Technique for direct search is    Hashing is the used for direct search.

Sparse metrics, Q. Define the sparse metrics and also explain the represent...

Q. Define the sparse metrics and also explain the representation of a 4X4 matrix using linked list.         Ans: A matrix in which number of zero entries is quite h

Two sparce matrices multipilcation algorithm, Write an algorithm for multi...

Write an algorithm for multiplication of two sparse matrices using Linked Lists.

Algorithm for pre-order traversal, Hear is given a set of input representin...

Hear is given a set of input representing the nodes of a binary tree, write a non recursive algorithm that must be able to give the output in three traversal orders. Write down an

Importance of game theory to decisions, Question: (a) Discuss the impor...

Question: (a) Discuss the importance of game theory to decisions. (b) Explain the following: (i) saddle point, (ii) two-person zero-sum game. (c) Two leading ?rms, ABC Ltd a

Lists, In the earlier unit, we have discussed about the arrays. Arrays are ...

In the earlier unit, we have discussed about the arrays. Arrays are data structures of fixed size. Insertion & deletion involves reshuffling of array elements. Thus, arraymanipulat

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