Empirical Lab Repository

Title: Sorting and Efficiency

Author: Dave Reed, Creighton University, davereed@creighton.edu

Possible Courses: CS1, CS2

Empirical Concepts Introduced: simulation, repeatability, analytical reasoning

Computer Science Concepts Used: sorting, efficiency, recursion, random values, timing code

Summary: This assignment takes an experimental approach to studying the efficiency of sorting algorithms. Two algorithms, Selection Sort and Merge Sort, are provided and the student is asked to perform various experiments to characterize the behavior of the algorithms. As part of the experimentation, the student must write a program to generate vectors of random data and time the algorithms on these vectors. By performing repeated experiments, the student investigates the rate-of-growth behavior of the algorithms, their sensitivity to presorting, and the number of swaps vs. inspections for each algorithm.

Variations: This assignment could easily be generalized to consider other sorting algorithms. To further emphasize the distinction between swaps and inspections, the code could be modified to keep a counter of each type of operation and display the final counts.

• Lab Handout (C++)
  
  
• Assignment Evaluation Form