Problem 4: External Sorting Answer the following questions for each of these sce

Question

Problem 4: External Sorting Answer the following questions for each of these scenarios, assuming that our most general external sorting algorithm is used:

A. A file with 100,000 pages and 30 available buffer pages.

B. A file with 200,000 pages and 50 available buffer pages.

C. A file with 20,000,000 pages and 170 available buffer pages.

Questions: 1. How many runs will you produce in the first pass?

2. How many passes will it take to sort the file completely?

3.What is the total I/O cost of sorting the file?

4. How many buffer pages do you need to sort the file completely in just two passes?

Explanation / Answer

Answer)
1. In first pass, sorted runs are: (N/B), N-number of file pages, B - number of available buffer pages
a) (100000/30) = 3334 sorted runs
b) (200000/50) = 4000 sorted runs
c) (20000000/170) = 117648 sorted runs

2.
Formula is = logB?1 [N/B]) + 1
The number of passes will it take to sort the file completely are:
a) (log2 3334) + 1 = 13 passes
b)   (log4 4000) + 1 = 7 passes
c) (log16 117648) + 1 = 6 passes

3. Total I/O cost of sorting the file using formula 2*N*(number of passes) are:
a) 2*100000*13 = 2600000
b) 2*200000*7 = 2800000
c) 2*20000000*6 = 240000000

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.