+1(978)310-4246 credencewriters@gmail.com
Select Page

Description

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.

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

, 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

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