ACTIVITIES

• You will complete both the Bubble Sort and Merge Sort using an Excel spreadsheet that I’ve already set up. Note that the spreadsheet has two tabs, one for the Bubble Sort Exercise and the other for the Merge Sort Exercise.

• If you haven’t done so already, please download Excel to your laptop. As a student, you can get it or free through OIT: https://oit.colorado.edu/services/messaging-collaboration/microsoft-office-365/help/proplusLinks to an external site.

• Links to an external site.Once you’ve got Excel installed, please download the Week 3 Sorting Algorithms Worksheet here: Week 3 Sorting Algorithms Worksheet-1.xlsx

The Bubble Sort

In the words of Brad Miller and David Ranum, authors of the Creative Commons- licensed book Problem Solving with Algorithms and Data Structures using Python (Links to an external site.), a bubble sort is “an algorithm that makes multiple passes through a list. It compares adjacent items and exchanges those that are out of order. Each pass through the list places the next largest value in its proper place. In essence, each item ‘bubbles’ up to the location where it belongs.” The image below illustrates the point.

Figure 1 shows the complete First Pass for the Bubble Sort. But it will take additional passes before the sorting algorithm has finished its work.

For your Bubble Sort Exercise, you — a human computer — will carry out every step in every pass of a full bubble sort. You will find the work repetitive and tedious, which actually is part of the point. Your human brain can put the figures in order almost instantly, without having to work through the algorithm step-by-step. But as you know from Janelle Shane’s book, computers need to be given and execute very precise instructions.

Before trying it yourself, please watch this short demonstration. (Don’t get freaked out by the tech talk at the end. He’s speaking in pseudocode (Links to an external site.), something you’ll learn more about in a future module.)

The Merge Sort

Working through all of the steps in a bubble sort takes a long time. It’s even slow for a computer. How can the same sorting task be done more efficiently? Enter the merge sort!

According to Miller and Ranum (Links to an external site.), a merge sort algorithm is “a recursive algorithm that uses a ‘divide and conquer’ strategy that continually splits a list in half. If the list is empty or has one item, it is sorted by definition. If the list has more than one item, we split the list and recursively invoke a merge sort on both halves. Once the two halves are sorted, the fundamental operation, called a merge, is performed. Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list.”