Optimal Sorting

Neeraj Gogate

Suhraab Alimi

Brook Asnake

Karthik Peravali

Flowchart

Sort Analysis

Data Spreadsheet Bubble Sort Insertion Sort Selection Sort

The sorting algorithms all have an average time complexity of O(n^2), which essentially means that the average time functions of the algorithms are all quadratic with respect to the number of elements. This results in all of the plotted functions having a roughly quadratic curve of best fit, as the highest term in the function should be on average some multiple of n^2. Despite this, certain algorithms fare better than other ones when you vary the relative order of the files. Namely, Bubble Sort and Insertion Sort were able to go much faster when the files were already sorted. This is because both of these algorithms have ways to be O(n) through them not making any extraneous comparisons and absolutely no swaps, something that selection sort can’t do. This contributes to Selection Sort being overall worse than both of these algorithms, as it is unable to make optimizations to know when it is sorted.

Despite the fact that these languages have certain strengths over each other, they are overall extremely slow. Most of the tests reached the point of being over a second at a mere 10,000, and all but Insertion Sort for the Ordered file reached a point of timing out at 100,000 words. This makes them incredibly impractical and frankly impossible to use in any modern application or webpage. They are simply just too slow, and they would cause the total dismantlement of simple problems and applications. There are simply too many better alternatives to these algorithms. Despite this, however, they are still incredibly important on a conceptual level. They are rather simple when compared to algorithms such as merge sort or quick sort, and thus provide more of a measurable gauge as to what and what doesn’t work in a sorting algorithm.