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?

Heap sort, We will start by defining a new structure called Heap. Figure 3 ...

We will start by defining a new structure called Heap. Figure 3 illustrates a Binary tree. Figure: A Binary Tree A complete binary tree is said to assure the 'heap con

Explain arrays, Arrays :- To execute a stack we need a variable called top,...

Arrays :- To execute a stack we need a variable called top, that holds the index of the top element of stack and an array to hold the part of the stack.

User-specified memory location, You need to implement a function which will...

You need to implement a function which will write out a given user-specified memory location to disk in base 10. That means that you have to convert the large number data structure

Tradeoff between space and time complexity, We might sometimes seek a trade...

We might sometimes seek a tradeoff among space & time complexity. For instance, we may have to select a data structure which requires a lot of storage to reduce the computation tim

Doubly linked list, code for count and display

code for count and display

Explain the memory function method, Explain the Memory Function method ...

Explain the Memory Function method The Memory Function method seeks to combine strengths of the top  down and bottom-up approaches  to  solving  problems  with  overlapping  su

Creation of doubly linked list, Program: Creation of Doubly Linked List ...

Program: Creation of Doubly Linked List OUTPUT Input the values of the element -1111 to come out : 1 Input the values of the element -1111 to come out : 2 Inpu

Determine the stereo vision, Determine the stereo vision There is still...

Determine the stereo vision There is still one more major item missing, before we can look at a computer display or plot and perceive it just as we see a real object, namely th

Stack and queue, write a algorithsm in c to perform push and pop operation...

write a algorithsm in c to perform push and pop operations stastic implementation using array ?

Dqueue, how can i delete from deque while deletion is restricted from one e...

how can i delete from deque while deletion is restricted from one end

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