Bullies, Bubble Sort, and Soccer Tickets

Bubble sort is a simple sorting algorithm. The algorithm repeatedly passes through an array, swapping adjacent elements that are out of order. As a result, larger elements "bubble" up to the end of the array, while smaller numbers "sink" down. This process continues until the array is sorted. Like insertion sort, bubble sort's worst case performance is O(N^2).

Peter had been in line for two hours when he felt the tap on his shoulder. He felt a pang of fear as he looked behind him. Terrible Todd glared angrily back. Then again, Terrible Todd always looked angry to Peter.

Terrible Todd was best known for his recent performance at the annual Alexandria area rock throwing contest. He was the first candle maker's apprentice to win the main event. His winning throw used a two hundred pound rock and the reverberation could be felt two miles away. Unofficially, he was also known for being a mean bully.

"Hi Todd." Peter meekly greeted him.

Todd grunted back and motioned Peter out of the way. Peter held firm. He refused to give up his place in line. Season ticket sales for the East Alexandria soccer team started in an hour. This year Peter was determined to get premium season tickets. He had his heart set on midfield.

"I am sorry, Todd. I was here first." Peter explained.

Todd looked Peter up and down. Then, with a louder grunt, Todd picked up Peter, turned, and set him down behind himself.

"Hey!" Peter cried, but Todd was already tapping the shoulder of the next person in line.

Peter fumed. This was not fair. Why should Todd get to go in front simply because he was larger? There were principles to these things.

As Peter ranted silently in his own head, he watched Todd slowly work his way up the line. One person at a time, Todd swapped places with smaller people. Todd’s advance was only halted when he reached Wren, the muscular blacksmith.

Then Peter felt another tap on his shoulder. Turning, he saw Big Jim. With a sigh, Peter stepped to the side and let Jim go ahead. Like Todd, Big Jim worked his way forward through the line. To Peter's pleasure Jim even moved in front of Todd to take the spot behind Wren.

Now Tiny Mike stood behind Peter. Peter tried to glare at Tiny Mike, making it clear that Mike was not moving ahead. Mike did not even try.

This process continued for the next hour. Every time a larger person found themselves waiting behind a smaller person, there was a polite tap on the shoulder and a switching of positions. Each time Peter moved back in the line he felt a little more demoralized. He was not a big person, and thus he found himself unable to swap with anyone. By the end of the hour the entire line was sorted by size, and Peter was near the back. Discouraged, Peter left the line and returned to the library.

As Peter sulked behind the library's counter, he remembered that now tickets were also available by pigeon message. He hurriedly filled out the form, requesting "Best Available". The pigeon flapped away, carrying Peter's only hope for reasonable seats. Ten minutes later, the pigeon returned with a confirmation of second-row, mid-field. Peter was thrilled. He must have gotten his tickets before even Big Jim.

That day Peter learned two important lessons. First, bubble sort is great for bullies. Second, standing in line was not worth it in the age of near-instantaneous pigeon-based ordering.

-----------------------

Read more about sorting algorithms with Merge Sort and Lines of Kindergarteners, Why Tailors Use Insertion Sort, or Sorting During the Flu Outbreak.

Why Tailors Use Insertion Sort

Insertion sort is a trivial, although potentially inefficient, algorithm for sorting. Given an array of numbers, the algorithm iteratively builds an increasingly longer sorted prefix within the array, until the entire array is sorted.

At the i-th iteration of the algorithm, the first i numbers in the array are in sorted order and the remainder might not be. The algorithm then: takes the i+1 number in the array, finds the correct location to insert it in the sorted prefix, and inserts it (shifting the following numbers down). Thus, after this step, the first i+1 numbers in the array are sorted.

"Insertion sort!" scoffed Peter. After only three months into his apprenticeship at the library of Alexandria, Peter was already arrogant from the computational knowledge that he now wielded.

"Who would ever use insertion sort?" Peter continued, working himself into a full rant. "It is an O(N^2) algorithm! You need to learn the wonders of merge sort. I have the scroll right here."

"Oh," remarked the shocked patron, hesitantly taking the scroll. "Thank you?"

"What is going on?" asked the head librarian as he returned from the stacks.

"Your young apprentice was 'educating' me on the correct sorting algorithm to use in my shop," explained the patron.

"He is using Insertion Sort," added Peter mockingly. The librarian did not burst into laughter as Peter expected. Confused, Peter looked back and forth between the librarian and the patron waiting for some reaction.

"I thought you came for a scroll about removing blackberry stains. It took me a while to find that one." said the librarian. Blackberries were out of season and the librarian had had to go deep into the stacks to find the relevant scroll.

The patron nodded. "While I was waiting, I was just explaining to young Peter here how my tailoring shop works. He had some interesting questions about how I sort the jackets."

"Ah," said the librarian. He knew the tailor well. "I think insertion sort makes sense in your case."

Peter was shocked. "What?" he screamed. He felt the blood rise to his face. How could anyone disagree with such a clear difference in computational complexity? That was almost as bad as cheering against the East Alexandria soccer team.

The librarian looked sternly at Peter. Embarrassed, Peter looked down at the floor.

"I do not understand," Peter added quietly.

"Perhaps you should explain how your shop actually works," suggested the librarian.

"It is simple," explained the tailor. "The shop is small, so I only have a single rack for all my jackets. I like to keep them sorted by size, because it is easier when patrons come in. I use binary search to quickly find a jacket in any size I need."

"That makes sense," agreed Peter. Binary search was another one of Peter's favorite algorithms for solving problems. At least the tailor used a reasonable search algorithm.

"Each monday, I get a new shipment of jackets, which I need to add to the rack. I start by putting them on the end of the rack, so that they won't sit on the floor and get wrinkled. The new fabrics are finicky this year. I wish that silk could have stayed in style a little longer. Anyway, after I put them on the rack, I have N sorted jackets at one end and then M new unsorted jackets after them. So I take each of the new jackets and insert it into the already sorted set of jackets. After inserting the first jacket, I have N+1 sorted jackets and M-1 unsorted jackets. I keep doing this until everything is inserted."

Before Insertion

During Insertion

After Insertion

"But…" started Peter. The librarian cut him off.

"I think what Peter wants to know is: 'Why you do not just take all the jackets off the rack and use something like MergeSort?'" explained the librarian. "MergeSort can be faster."

"Because jackets are heavy," explained the tailor. "It is a pain to take them off the rack. But they 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 are missing is: when most people use insertion sort, the insertions are expensive," the librarian explained to Peter. "Consider an accountant who is 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 cannot 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 O(N) operation. That is a lot of erasing and rewriting."

"But, for a tailor, the insertion is an O(1) operation. You just push the coats down," added the librarian.

Peter nodded an acknowledgement. Inside he chaffed at the stupid technicality 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 it actually seemed like insertion sort was reasonable. He wondered what other real world applications might challenge his computational complexity assumptions.

Later that day, Peter tried using insertion sort on several carts worth of books. Unfortunately, the books did not 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 2am, angry at himself for not determining the cost of the insertion operation before he had started sorting.

-------------------

Read more about sorting algorithms with Merge Sort and Lines of Kindergarteners or Bullies, Bubble Sort, and Soccer Tickets.