Spaghetti Sort is a custom-designed sorting algorithm for meticulous chefs inspi

Question

Spaghetti Sort is a custom-designed sorting algorithm for meticulous chefs inspired by the process of sorting uncooked spaghetti by length as follows Recipe for Sorting Spaghetti (a) Grab all noodles in one of your hands (b) Hold your hand above a flat surface like a table (c) Bring your hand down so that you can make the spaghetti bottoms level (d) Hover your other hand above the noodles (e) While there are still uncooked noodles i. Lower your non-spaghetti hand at constant velocity until it hits a noodle (this must be the longest one.) ii. Remove that noodle using that hand 11. Place it at the beginning of your noodle list. iv. Return vour hand to the position it was in when it hit a noodle If we imagine a different version of spaghetti sort in which, after ensuring the bot- toms of the noodles were level, we lowered the noodles into a vat of acid (gloves required!) until they were completely disintegrated 1, we might feel inspired to port this algorithm to pseudocode as follows Algorithm 3: spaghetti-sort(L) Data: An unsorted linked-list L of natural numbers Result: L, but sorted in ascending order Result a new, empty linked-list counter 0 while L is not empty do for each node n with value x N, in the standard linked-list iteration order do if x = 0 then Append the value of counter to the end of Result Remove node n from the linked-list Continue the "for" loop from the node which came immediately after n else x x-1 (Subtract one from the element in the list) end end counter counter 1 end return Result

Explanation / Answer

Answers:-

a.) The Asymptomatic Runtime Complexity of spaghetti-sort

Assume that the list has n elements.

We see that the algorithm continuously loops until, all nodes have been removed from the list.

Each loop takes n iterations to complete.

Hence total time required would be : n * ( no. of times the outer while loop executes )

  Now, the outer while loop executes until, all elements have been removed.
Clearly, the largest element in the list will determine the time taken by the outer while loop to complete.

So, quantitatively,

compelexity = n*[ max element of the list]

for example if the largest element in the list was 1000, so total time would have been ~ 1000n

Hence complexity = n*max_element_of_list

b.) Here we are given that the elements are not arbitrary natural numbers but 64-bit unsigned integers.

So, max value of an unsigned 64-bit integer can be: 264-1 =  18446744073709551615.

Hence, the upper bound on the runtime is now: 18446744073709551615*n

c.) As max value of a 64 bit unsigned integer is quite large, we wouldn't want to use spaghetti sort for practical purposes as this would prove to be too computationally expensive.

Generally, list sizes are in range of 105 to 106 and 264-1 is of the order 1019.

This will range in computation times in range of 1024 to 1025 which on all metrics is very high to compute.

Hence, it will be computationally very expensive.
Spaghetti sort is useful when the numbers are in reasonable range as in range till 10,000.   

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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