Login

Create Account
+14156709189
info@expertsmind.com
Submit Homework/Assignment
Get quote & make Payment
Get Solution
What is Oscillating Sort?, Data Structure & Algorithms
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.
Posted Date: 2/22/2014 9:49:16 AM  Location :
Ask an Expert
Related Discussions:
What is Oscillating Sort?, Assignment Help, Ask Question on What is Oscillating Sort?, Get Answer, Expert's Help, What is Oscillating Sort? Discussions
Write discussion on What is Oscillating Sort?
Your posts are moderated
Write your message here..
Related Questions
Test whether a binary tree is a binary search tree, Q. Write down an algori...
Q. Write down an algorithm to test whether a Binary Tree is a Binary Search Tree. A n s . The algorithm to check whether a Binary tree is as Binary Search
Array implementation of lists, In the array implementation of the lists, we...
In the array implementation of the lists, we will use the array to hold the entries and a separate counter to keep track of the number of positions are occupied. A structure will b
Full binary trees, Full Binary Trees: A binary tree of height h that had 2...
Full Binary Trees: A binary tree of height h that had 2h 1 elements is called a Full Binary Tree. Complete Binary Trees: A binary tree whereby if the height is d, and all of
Array implementation of a multiqueue, Program gives the program segment by ...
Program gives the program segment by using arrays for the insertion of an element to a queue into the multiqueue. Program: Program segment for the insertion of any element to t
Algorithams example, any simple algoritham questions with answers
any simple algoritham questions with answers
Algorithm, give me algorithm of simple interest
give me algorithm of simple interest
Userspecified memory location, You need to implement a function which will...
You need to implement a function which will write out a given userspecified memory location to disk in base 10. That means that you have to convert the large number data structure
Postfix expression, : Write an algorithm to evaluate a postfix expression. ...
: Write an algorithm to evaluate a postfix expression. Execute your algorithm using the following postfix expression as your input: a b + c d +*f .
Explain the concept of hidden lines and surface removal, Explain the concep...
Explain the concept of hidden lines The problem of hidden lines or surfaces was implicit even in 2D graphics, but we did not mention it there, because what was intended to be
For loop, for (i = 0; i sequence of statements } Here, the loop e...
for (i = 0; i sequence of statements } Here, the loop executes n times. Thus, the sequence of statements also executes n times. Since we suppose the time complexity of th
Assignment Help
Accounting Assignment Help
Economics Assignment Help
Finance Assignment Help
Statistics Assignment Help
Physics Assignment Help
Chemistry Assignment Help
Math Assignment Help
Biology Assignment Help
English Assignment Help
Management Assignment Help
Engineering Assignment Help
Programming Assignment Help
Computer Science Assignment Help
IT Courses and Help
ExpertsMind Services
Online Tutoring
Projects Assistance
Exam Preparation
Coursework Help
Programming Courses
Engineering Courses
Why Us ?
~Experienced Tutors
~24x7 hrs Support
~Plagiarism Free
~Quality of Work
~Time on Delivery
~Privacy of Work