labSorting: Big-Oh Exploration

< Previous  Next >

---

Due Date

See the calendar for due date.

Objectives:

• Implement sorting algorithms
• Practice algorithm analysis
• Gain appreciation for what the growth-rate of a function means

Description:

Implement the following sorting algorithms and measure their execution times. Discuss if the timing agrees with the theoretical algorithm analysis for each algorithm.

• Insertion sort
• Bubble sort
• Heapsort
• Mergesort
• Quicksort

Requirements:

1. Use the following source code as the driver for this lab: labSorting-main.cpp. Do not modify it. Implement each of the above sorting algorithms, so that the callback functions stored in the sortingFunctionCallbacks vector execute and return the number of seconds that that algorithm required to run. To measure the timing, use something similar to the following to time each execution:

   #include <time.h>
   ...
   double diffClocks(clock_t clock1, clock_t clock2){
       double diffticks = clock1 - clock2;
       double diffsecs = diffticks / CLOCKS_PER_SEC;
       return diffsecs;
   }
   ...    
       clock_t begin, end;
       begin = clock();
       _______SortMain( ...);
       end = clock();
   
       return diffClocks( end, begin);
   ...    
   

   Notice that nothing is executed between the timing calls except for the call to the sorting algorithm.
2. If possible, perform the timing on a lightly loaded machine (e.g., your own machine, NOT ranger or shemp)
3. To establish trends in the data, each sorting algorithm must have multiple values that are not 0.0
4. Create a file labSorting-results.txt and insert a brief discussion for each sorting algorithm as to whether or not the theoretical growth function matches up with the execution times. Provide justification. If it's helpful, graph the results, include them in your project directory and indicate the filename(s) in labSorting-results.txt.
5. Your program must compile and run in both Visual Studio 2012 and on ranger. On ranger, it must compile with the following command:
   
   g++ -std=c++0x *.cpp -o labSorting
6. Do not include spaces in directory names or file names.
7. Include a completed rubric and number of hours spent on the assignment. Please copy and paste the rubric into a new file inside your project directory. Name the file: rubric-yourlastname.txt.

Submission

Before preparing your project for submission, remove the debug and ipch directories (if present) and any .sdf files. Additionally, remove any other files not associated with lab5. Zip the whole project folder (e.g., by right-clicking on the folder and choosing send to::Compressed (zipped folder)). Name your zip file as lab5.zip. Make sure that all of the source code file(s) are in your zipped file. Submit your zip file at https://3110.cs.mtsu.edu/.

Rubric:

Points      Item
----------  --------------------------------------------------------------
_____ / 10  Documentation:
            + All source code files (.h & .cpp) include file name, author, description etc. 
            + Functions and variables
            + All non-trival variables are commented 
            + All functions preceded by brief comments 
            + Comments included before major portions of code 
            + Functions should be no longer than 1 page
_____ /     Compiles and runs in Visual Studio and on ranger
_____ / 25  Requirements met:
_____ /     + Insection Sort
_____ /     + Bubble Sort
_____ /     + Heapsort
_____ /     + Mergesort
_____ /     + Quicksort
_____ / 45  Execution times
_____ / 20  Discussion of correlation
_____ /     Completed rubric (estimates for each line including hours spent)
	    
_____ /100  Total

_____  Approximate number of hours spent
      

Helps

• If you don't have one of the specified sorting algorithms working, comment out the call to push_back() for both the name and the callback function vectors to reach the maximum amount of partial credit.
• You can have the g++ compiler optimize your code by using the -O3 flag.
• Other Animations & Videos:
  • www.sorting-algorithms.com
  • Hungarian dancing sorting algorithms
  • Barack Obama answers "What is the most efficient way to sort a million 32-bit integers?"
  • Mike Bostock's Visualizing Algorithms Video and transcript/webpage
• From a previous student:
  When testing out the output for my lab, I noticed that I kept getting stack overflows whenever I tried sorting an array larger than 50000, which confused me, because I DID dynamically allocate the array. After several hours of researching and trying to figure out what was wrong, I came upon a Yahoo! Answers response which pointed out that when you use the debugger to compile in Visual Studio, the compiler does not recognize tail recursion, and the solution to this was to change the debugger configuration from "debug" to "active(release)".

Optional (worth 0 points!)

1. Add in a Shellsort, selection sort, bucket sort, radix sort, (or another sort), time it's execution and provide justification / an explanation for the theoretical and empirical results.
2. Extend the average-case analysis above with a best-case and/or worst-case analysis.