Generating Almost Descending Sequences to Reduce the Number of Movements in Sorting

Sorting algorithms usually generate strictly descending sequences. However, almost descending sequences may be sufficient to fulfill our needs in practice, and the number of movements needed for generating such sequences can be greatly reduced. We call a sequence $S$ almost descending if $S[j]-S[i]< C$ for any $i< j$ and a positive number $C$ , which depends on the practical circumstances. Unless the difference between $S[j]$ and $S[i]$ exceeds the bound $C$ , we deem them indistinguishable. For example, when people are arranged in a line from tall to short, two people with heights of 1.751 meters and 1.752 meters can be considered visually indistinguishable (we can set the bound to $C=0.005$ meters in this case). Therefore, we do not need to adjust their positions, which leads to fewer movements in sorting. In this paper, three algorithms are provided to generate almost descending sequences, and their correctness is proven. The experimental results of the proposed algorithms demonstrate that our technique can reduce the number of movements in sorting. In addition, almost descending sequences are more stable than strictly descending sequences in dynamic sorting, which is useful in online sorting and sorting in noisy environments.