O(n) Sorting: A New, More Efficient Computer Sorting Algorithm

Overview

Objectives/Goals In this project, a new sorting algorithm was created using the language of C++. This sort would sort numbers digit by digit (by the one's space, then ten's space...) instead of as a whole. My goals were for this sort to run more efficiently (sort numbers faster) than any other sorting algorithm, and to have it run with an efficiency of O(n), which was previously said to be impossible. Methods/Materials To test the sort, I wrote a program in C++ that would have my new algorithm and five other commonly used sorting algorithms (insertion sort, selection sort, shell sort, bubble sort, and the quicksort) sort random arrays of numbers. The arrays of numbers would range in length from 10000 to 100000 numbers. The program would be run ten times for each size array (100 times total) to get accurate readings. Results My results were that the new sorting algorithm that I developed did run faster than all the other sorting algorithms that I tested it against. The quicksort was the next fastest, then the insertion sort, the selection sort, then the shell and bubble sorts. Conclusions/Discussion My conclusion was that my sort ran faster than all of the other sorting algorithms. I also concluded that it did run with an efficiency of O(n). Since the new sort only needed to make the same number of passes through the array regardless of it's size, that mathmatically proves it to be an O(n) sorting algorithm.

Competition history

• CSEF 2003 Mathematics & Software · Entry S1226

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Computational Sciences projects
• CSEF Computational Sciences projects
• Every CSEF 2003 project