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?

Sparse matrix, How sparse matrix stored in the memory of a computer?

Midsquare hash method, I want to example for midsquare method

The quick sort algorithm exploit design technique, The quick sort algorithm...

Algorithm to merge the lists together, Q. Let X = (X1, X2, X3,....Xn) and Y...

Breadth first traversal, The data structure needed for Breadth First Traver...

Binary search tree (bst), Q. Explain what do we understand by Binary Search...

Algorithm to insert a node in between any two nodes, Q. Write down an algor...

Make adjacency matrix for un-directed graph, Q. Describe the adjacency matr...

Merging, merging 4 sorted files containing 50 10 25 and 15 records will tak...

Bubble sort, #question bubble sort..

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