Computational Fairy Tales by Jeremy Kubica

Author:Jeremy Kubica [Kubica, Jeremy]
Language: eng
Format: epub, pdf
Published: 2012-06-24T23:00:00+00:00

Before Insertion

During Insertion

After Insertion

“But—” started Peter. The librarian cut him off.

“I think what Peter wants to know is why you don’t take all the jackets off the rack and use something like merge sort,” said the librarian. “Other sorting algorithms can be faster.”

“Because jackets are heavy,” explained the tailor. “It’s a pain to take them off the rack. It would be tiring. But the jackets do slide easily down the rack.”

Peter looked confused. Why did it matter how hard it was to take things off the rack? This was an argument about computational complexity.

“I think the factor that you’re missing is: when most people use insertion sort, the insertions are expensive,” the librarian explained to Peter. “Consider an accountant who’s trying to sort a list of accounts in one of his books. Each line is one account—like entries in a computer’s array. You can’t just insert something and have the rest shift down automatically. That would take a most tedious form of magic. Every time the accountant wants to do an insertion, he has to manually shift down everything below that. A single insertion is an expensive O(N) operation. That’s a lot of erasing and rewriting.

“But, for a tailor, the insertion is a simple O(1) operation. He pushes the coats down,” added the librarian.

Peter nodded an acknowledgement. Inside he chafed at the technicalities of the physical world impacting the cost of different operations. The theoretical world was so much cleaner. However, he did agree with the librarian and the tailor; in this case, insertion sort seemed reasonable. He wondered what other real-world applications might challenge his computational assumptions.

Later that day, Peter tried using insertion sort on several carts’ worth of books. Unfortunately, the books didn’t move easily between the carts’ shelves, and Peter found himself spending the entire night shifting books between shelves. It took him an extra three hours to finish the sorting. He left the library at 2 a.m., angry at himself for not determining the cost of the insertion operation before he started sorting.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.