beanz Magazine

Sorting Algorithms

rjp on Flickr

What do bubbles, pancakes, and spaghetti all have in common? They're all great for sorting!

Whether it is books in a library or clothes in a closet, keeping data organized makes it easier to find the things you need. Sorting is a simple task if you’re human. But if you’re a computer, things get a bit more tricky. Imagine trying to arrange your books alphabetically, except the room is pitch black, and your flashlight can only reveal one book title at a time! You’ll probably have to go backwards and forwards through the shelf multiple times to make sure everything’s just right.

When a computer needs to sort a list with billions of elements, it can’t afford to be inefficient. Enter sorting algorithms. These are strategies a program uses to minimize the number of times it has to go backwards and forwards through a list.

Some strategies are designed to be fast. Some take minimal space, some are simple, and some are complex. In this article, we’re going to look at the sorting algorithms with the funniest, quirkiest names!

BUBBLE SORT

If you look at a fizzy drink, you’ll see the bubbles slowly rise to the top. Similarly, in our bubble sort algorithm, each element slowly rises through the list until it finds its ideal sorted position.

If you want to follow along with the steps, grab any group of sortable things — like books, cards, or stuffed animals of different sizes — and lay them out in a row. Make sure the order is nice and random!

STEP 1. Start at the beginning of your row. Compare the first element with the second. If the first is bigger, swap the two objects.

STEP 2. Now compare the second element with the third. If the second is bigger than the third, do the swap. If not, keep the list as is.

STEP 3. Keep going through your list, looking at pairs of objects then swapping as needed, until you reach the end. Resist the temptation to sort the list as a human would!

The list is now more sorted than before — but still not completely sorted.

STEP 4. Keep repeating steps 1-3, starting at the beginning of the list and swapping pairs of objects until you reach the end. The algorithm ends when your list is completely sorted. You may have to go through this step many times.

Here’s a great video illustrating the bubble sort algorithm.

PANCAKE SORT

This sorting strategy requires your objects to be stackable. While pancakes are delicious, they can be messy, so a stack of books might be easier to handle.

In pancake sort, you use an imaginary spatula to flip sections of the stack. You can flip the whole stack, half of it, or even a single “pancake” or two! The goal is to sort the “pancakes” from smallest to largest — or A to Z — in a minimum number of flips.

STEP 1. Find the largest element in your stack, then insert your imaginary spatula under it, and flip! The largest element should now be at the top.

STEP 2. Flip over the entire stack, so that the largest element is at the bottom.

STEP 3. Repeat steps 2-4, ignoring the pancakes that are already sorted at the bottom. If you started with 10 elements, you shouldn’t have to do this step more than 10 times!

Click here to see pancake sort in action!

SPAGHETTI SORT

In this sorting strategy, you’ll need a small handful of dry spaghetti noodles. Break the tips off so that each noodle is a different length.

STEP 1. Grip the handful of spaghetti, then slowly lower it so that the bottom of each noodle rests on a flat surface.

STEP 2. Lower your other hand onto the handful to determine which noodle is the longest.

STEP 3. Set the longest noodle aside.

STEP 4. Repeat steps 1-4 until all the spaghetti noodles have been sorted.

Here’s a visual representation of spaghetti sort.

PIGEONHOLE SORT

In pigeonhole sort, our elements are pigeons. Our “pigeonholes” are subgroups of data. Often, these are ranges of numbers. Maybe the first pigeonhole covers numbers 1-10, the second pigeonhole 2-20, etc. Or perhaps the pigeonholes are suits of cards: clubs, diamonds, hearts, then spades. The important thing is that our categories match the elements in our list, and the categories can also be organized from smallest to largest.

Choose your pigeonholes, then let’s get started!

STEP 1. Assign the first “pigeon” to its appropriate pigeonhole.

STEP 2. Within that pigeonhole, sort the pigeon so that it’s correctly ordered with the other pigeons roosting there.

STEP 3. Repeat steps 1-2 until all pigeons have been placed.

STEP 4. Starting with the smallest pigeonhole, remove the pigeons and place them back (in sorted order) into the list.

STEP 5. Continuing from smallest to largest, repeat Step 4 with all the other pigeonholes.

CONCLUSION

These sorting algorithms might seem weird and inefficient when you’re a clever human who can look over their list and quickly spot the biggest and smallest elements. But these strange techniques — whether its bubbling up, flipping pancakes, or creating special categories for pigeons — are essential to computers. They key is that computers can only compare two elements at once, which limits their ability to find and remember data.

There are many other sorting algorithms, such as quicksort and mergesort, and each one is best for a different situation. Check out the links below to learn more!

Learn More

On Sorting

https://www.kidscodecs.com/on-sorting/

Comparison Sorting algorithms

https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

Bubble Sort

https://www.kidscodecs.com/bubble-sorts/

Bubble sort video

https://www.youtube.com/watch?v=nmhjrI-aW5o

Pancake Sorting

https://www.geeksforgeeks.org/pancake-sorting/

Pancake sorting animation

http://www.youtube.com/embed/kk-_DDgoXfk

Spaghetti Sort

https://en.m.wikipedia.org/wiki/Spaghetti_sort

Spaghetti sort animation

https://www.youtube.com/watch?v=dJEn4Xc5F2o

Pigeonhole Sort

https://www.geeksforgeeks.org/pigeonhole-sort/

Sorting Algorithms

https://www.geeksforgeeks.org/sorting-algorithms/

Sorting Algorithms video

https://video.search.yahoo.com/yhs/search?fr=yhs-Lkry-SF01&hsimp=yhs-SF01&hspart=Lkry&p=sorting+algorithms#id=8&vid=61a19b4c1cd0edecd82c7eb02be0e745&action=click

Sorting lesson plan for teachers

https://www.lessonplanet.com/teachers/lightest-and-heaviest-sorting-algorithms?msclkid=c1480f2f483b13b56846515fb1a4f82f&utm_source=bing&utm_medium=cpc&utm_campaign=DSA%20(WS)&utm_term=lessonplanet&utm_content=All%20Webpages

Bubble sort facts

https://kids.kiddle.co/Bubble_sort

(Visited 1 times, 1 visits today)

Also In The April 2020 Issue

As students reach the age of 13 the importance of them understanding their rights and privacy online becomes crucial.

The iDTech summer camp recently posted 102 questions. Here are a few with links to the full list.

Being well-read is essential in everything in life, and coding is no exception! Here are some book recommendations to make you a coding master.

The circus is in town, but they're missing one of their colourful balls. Let's make one for them!

Sundials were one of the first ways people kept track of time. But how did they work?

New to physical computing? MircoPython may be perfect or you!

It's project time! In this article we go over how the same processes used in big factories can be used to control a simple LED.

What do bubbles, pancakes, and spaghetti all have in common? They're all great for sorting!

Yee-ha! In the wild wild west of the internet, antivirus software is a must-have partner.

Exploring the concept of RAM and how it helps your MInecraft game run better.

Breaking down big problems into smaller ones is a great way to solve them. Let's see how recursion helps us do this!

How did this pale blue dot that we call Earth first begin? The answer is even more fascinating than imagined.

Have you ever wondered why your computer's mouse is called that? Well it all started with a fellow named Douglas and a block of wood...

How do you power devices at the top of mountains and the bottom of oceans? Let's find out!

Links from the bottom of all the April 2020 articles, collected in one place for you to print, share, or bookmark.

Interesting stories about computer science, software programming, and technology for April 2020.