Item Retention Improvements to Dropsort, a Lossy Sorting Algorithm

摘要

This paper presents the Dropsort algorithm and suggests improvements. Dropsort is a simple comparison sorting algorithm that performs in θ(n) time by simply removing those elements that are not already in the correct order. Because of this, it is not a true sorting algorithm as the output does not contain all the elements of the input. In other words it is a lossy "sorting algorithm" that performs far more quickly than true sorting algorithms. Much of the original data is lost when using this algorithm unless the numbers to sort are in a mostly ordered format already. If more than a few elements are far from their correct position nearly all of the elements are removed. Two major improvements are proposed that greatly broaden the applicability of the Dropsort algorithm. In the first improvement, a concept of recent memory is added to the algorithm. For example, if several elements are consecutively dropped, the preceding element is assumed to be far from ordered and is removed instead. This is shown to increase the usefulness of Dropsort by increasing the number of retained elements. With a specific type of introduced error, 10,000% more of the original elements are retained over standard Dropsort. In the second improvement, each element is compared to not only determine if it is in sorted order, but if the next element is in order as well. Only if both elements are in order is the item kept. It is important to note that neither of these suggested improvements greatly increase the complexity or execution time of the Dropsort algorithm. Finally, the applications and limitations of these improvements and Dropsort in general are explored. This improved algorithm has many applications to very quickly sort large data sets when specific elements are not as important as the assurance that the list is sorted. This could be the case when a sorted list is critical but the source providing the pre-sorted input is not trustworthy. Also, applications in fields with large data sets and where speed is of utmost importance are discussed.