C# Programming > Data

Five-Element Sort Algorithm

The sorting steps are fairly straight forward. To understand the process, we are going to label the elements a, b, c, d, and e. These are assigned in the order in which the original list is given to the function.

The first step is to check if a is greater than b. If it is, then the values are swapped. This ensures that b is greater than a.

The second step is to check if c is greater than d. If it is, then the value are swapped. This ensures that d is greater than c.

The third step is to check if b is greater than d. If it is, then b and d are swapped and a and c are swapped. At this step we are sure of the following: a < b < d, and c < d. Note that we know nothing of c in terms of a and b, but we know for sure that c is less than d.

So far we have used 3 comparisons. We have 4 left.

The fourth step is to find the place of e within a < b < d. First compare e and b. If e is greater, then it is compared with d to see if e goes between b and d or if it is greater than both. The opposite is done with a. Notice that this took 2 comparisons and we end up with one of the following scenarios:
e < a < b < d
a < e < b < d
a < b < e < d
a < b < d < e

The fifth step is to find the place of c within the four sorted elements. This will take at most 2 comparisons. Why? Since we established on the third step that c is less than d, we do not have to compare c with d or anything greater than d.

Thus in the first three cases, we need to compare c only two elements:
e < a < b < d - compare to a first, then to either e or b.
a < e < b < d - compare to e first, then to either a or b.
a < b < e < d - compare to b first, then to either a or e.

For the last case, we only need a single comparison, since only two of the elements are less than d.
a < b < d < e - compare to either a or b.

The total number of comparisons are 3 from the first three steps, 2 from step four, and 2 from step five (1 in one case), which gives us 7 comparisons (6 in that one case).

Conclusion

This algorithm is indeed optimal in sorting five elements in a comparison-based manner. Some very basic benchmarks on my computer showed it to be twice as fast as the sort function built into C#.NET (which uses Quicksort). You can find the C# implementation below.

But remember that this is a very narrow case that works for sorting five elements optimally. So why is such a trivial case useful? There are other algorithms that work by dividing a problem into a number of smaller subproblems. Some of these algorithms actually end up with a subproblem that requires the sorting of five elements. Since our five-element sort consists of a fixed number of if-statements, it can be considered to run in constant time (O(1) instead of O(n log n) of other sorting algorithms), and thus does not affect the asymptotic running time of the algorithm solving the overall problem.

In plain english, if a complex function runs into a spot where it needs to sort exactly 5 elements. This algorithm is the way to go.

 

Page 1
<< Comparison-Based Sorting

Back to C# Article List