Romain Semler

Imagine ... You have an array of 100 boxes with inside 100 different numbers that were arranged randomly. Your goal is to sort all the numbers in this table in ascending order. How long will you take ?

A computer perform this sort in less than one millisecond ! And if we change size ? Suppose your table has now one million boxes so with a million different numbers to sort. Well for a computer, time still counts in milliseconds.

This project, that I realized with a teammate, were given during the study of computational complexity at the faculty. The goal was to implement, with the C programming language, some sorting algorithms (9 in our case) and test their average time to sort out 15 different sizes of tables. In addition, the algorithms must perform 20 times for sorting an array size. So, a total of 20 x 15 sorts for each algorithm. When a sort is performed on 20 arrays of the same size, we calculate, using another program, its average sorting time on the 20 arrays. Once the 15 sizes have been processed, the average times for each array size are listed and graphs drawn to obtain comparative curves.

Here are the different sorting algorithms that have been implemented :

In these sorts, there are "slow sort" (less efficient) and "fast sort" (more efficient). The first 5 are "slow" and the last 4 are "fast". In our project, we chose to stop the algorithms that take more than 5 minutes to sort the 15 array sizes. It turns out that in our final results, all the "slow" sorts take more than 5 minutes to sort all 15 sizes. "Quick" sorts, on the other hand, take less than 5 minutes. The comparison of the curves of the graphs obtained reveals the effectiveness of each algorithm.

The report containing the data, graphics and results is available below.