Suppose you would like to sort n music files using a comparison-based sorting al

Question

Suppose you would like to sort n music files using a comparison-based sorting algorithm (i.e. no bucket sort), but you only have an old, unreliable computer, which you have nicknamed "Rustbucket". Every time Rustbucket compares two music files, x and y, there is an independent 50 - 50 chance that it has an internal disk fault and returns the value -1, instead of the correct result of 1 for true or 0 for false, to the question, "x lessthanorequalto y?" Otherwise, Rustbucket correctly performs every other kind of operation (including comparisons not involving music files). Describe an efficient algorithm that can use Rustbucket to sort n music files correctly and show that your algorithm has expected running time that is 0 (n log n).

Explanation / Answer

Ans

To sort n music files we can use selection sort algorithm
As we know music files not only include music file name but also unique number to manage files,
it path,name and artist information ,skip count and many more.
so to sort them we use the unique number
In this method follow these steps
->it performs n-1 comparision
->it finds minimum value and compare it with from first element
->as minimum found it starts to fill from first location
->as the comparision decreses it its performance increases

For the current scenerio we are searching the files in disk too and sorting them so for this
-> Firstly we load all music files from system to an array
-> Then

ruskbucket[]=all files from disk
then
if from the reading from an array there is fault it will return -1
then sort them from selection sort and exchange value

for k<- 0 to n-1
ruskbucket[k]=reading from files
if fault
return -1
else
for i 0 to n – 1
// where n is number of music files
do
max min i
for j i + 1 to n – 1
do
if ruskbucket[ j ] <= ruskbucket[ min ]
min j
return 1;
else if ruskbucket[ j ] > ruskbucket[ max ]
max j
return 0;
done
if min != i
exchange ruskbucket[ i ] <-> ruskbucket[ min ]
if max != n – 1
exchange ruskbucket[ n - 1 ] <-> ruskbucket[ max ]
n n - 1
done

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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