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.