Search code examples
pythonduplicateslist-comprehensionquicksort

Avoid unintentionally removing duplicates in list comprehension-based quicksort?


I am new to Python and learning that it also implements list comprehensions, like Haskell with which I have some experience. I attempted to write a Haskell-esque quicksort function. It does sort the given list, but also removes any duplicate elements; obviously this is not a feature one generally wants in a sorting function. Why does this happen and how can I fix it? (Python 3.6)

def quicksort(unsorted):
    """Sorts a list least to greatest numerically using quicksort
    """
    if not unsorted:
        return []
    else:
        pivot, *rest = unsorted
        lower_sorted = quicksort([a for a in rest if a < pivot])
        upper_sorted = quicksort([a for a in rest if a > pivot])
        return lower_sorted + [pivot] + upper_sorted

Solution

  • One of the conditions (either if a < lower_pivot or if a > upper_pivot) must include an equality test.