Lab #5: Comparing Sorting Algorithms - Bubble Sort vs Merge Sort

(15 Points, Due Saturday, October 19th, 11:59 PM)

-Introduction-

A good programmer knows when to use one sorting algorithm over another. (Perhaps insertion sort would work better for this project? Maybe selection sort would be more efficient?)

This lab will go over two of the most commonly used sorting algorithms in computer programming, Bubble Sort and Merge Sort.

-Bubble Sort-

Bubble Sort is a sorting algorithm that compares adjacent elements of a data structure, and swaps their positions if they are in the wrong order. For example, let's look at a pseudoexample of an integer array A[] with elements = {7,4,5,2}. A Bubble Sort performed on this array would produce the following result:

As you can see, the algorithm parses through the array and swaps the values if one is greater than the other. This continues until there are no more swaps left

-Merge Sort-

Merge Sort is a divide-and-conquer algorithm that breaks down a list into a several sublists until each sublist contains a single element. The sublists are then merged back in a way that results into a sorted list.
Let's take a look at an array that contains the following elements: {9,7,8,3,2,1} Applying a Merge Sort on this list will produce the following:

-Requirements For This Lab-

You will write two C/C++ programs that read a file full of random numbers. One program will attempt to sort the numbers using Bubble Sort, and the other will attempt to sort using Merge Sort.

There are three files that you will be sorting: example10.txt, example100.txt, and example1000.txt. Each list contains 10, 100, and 1000 random integer values, respectively. Your programs must be able to parse each of these files and sort them. DO NOT WRITE BACK TO THE FILE!All sorting must be done within the program itself. Afterwards, you will display the amount of time it took for your program to sort the list.

The required files for this lab, along with a sampleOutput program of what your program should look like, can be found by typing the following command into the terminal:

cp ~araines/public_html/CMPS3120/Labs/Lab05/Files/* .

Then, run the following command to use the sampleOutput:

chmod 755 sampleOutput

I highly recommend use of the following C/C++ Libraries:

• iostream
• fstream
• chrono

I will check you off on the following things during the Lab Period:

• Program successfully opens and reads from file (1 point)
• Program successfully sorts example10 and example100 using Bubble Sort (2 points)
• Program successfully sorts example10 and example100 using Merge Sort (2 points)

The following requirements are assigned as "homework" and must be completed by next Saturday's deadline of midnight. Whatever is not completed during lab is also "homework."

• Program successfully sorts example1000 using Bubble Sort (2 points)
• Program successfully sorts example1000 using Merge Sort (2 points)
• Program displays the time each sorting algorithm took (1 point)

-Lab Report-(5 Points)

Please answer the following 3 questions in a lab report:

1. What is the time complexity of Bubble Sort? List it's best, average, and worst case scenarios in terms of O(n)
2. What is the time complexity of Merge Sort? List it's best, average, and worst case scenarios in terms of O(n)
3. What do you notice when comparing the results of Bubble Sort to Merge Sort? Is there a time difference? Which would be faster when sorting a list of 10,000 elements? 100,000 elements? Which is better for sorting smaller lists?

Name your Lab Report "lastName_firstName_Lab05" and submit as either a word doc or PDF to Blackboard.

Name your programs "bubbleSort.cpp" and "mergeSort.cpp", respectively, and submit your program to BlackBoard by the deadline. Late work can be submitted via my email, but will lose 1 point for each day it is late.