Computer Science Senior Project Statistical Analysis of Sorting Algorithm Efficiency

Abstract

This project presents a statistical analysis of the efficiency (in terms of raw speed) of eleven sorting algorithms: bubble sort, heap sort, insertion sort, merge sort, quick sort, "enhanced" quick sort, "fast" quick sort, radix sort, selection sort, shaker sort, and Shell sort. (A brief description of the working of each algorithm is contained within the program.)

Each algorithm is used to sort 300 arrays of random integers. The first 100 arrays are of increasing length, from 100 to 10,000 elements, and the remaining 200 arrays each contain 5,000 elements. Every sort is timed to the nearest millisecond, and each algorithm's set of sort times is saved in a file. The data from the first 100 arrays is used to plot a line graph of sort time vs. array size for each algorithm, and the data from the other 200 arrays is used to plot a histogram of sort times for each algorithm. The mean, median, and standard deviation of this data is calculated and displayed with the histogram. The user also has the option to display a composite line graph of each algorithm's first 100 sort times, for a direct visual comparison of the speed of the algorithms.

A simple graphical user interface, consisting mainly of a hierarchy of push-button menus, is used to guide the user through the program and present the data in an easy-to-follow fashion. The graphs themselves (with the exception of the composite line graph) are labeled interactively, so as to clearly illustrate the meaning of each data point or column of data.

Advisor: Joe Daugherty

Image: 
Student Name: 
Dave Young