1

I am currently implementing the Quickselect Algorithm to get the best n elements in a list. The "best" element is in this case the largest.

My problem is the following:
I discovered that this gives poor performance in case of many duplicate elements, because at the end the values that are not sorted will all be the same and at that point the left border will only be incremented by 1 at each iteration regardless of the pivot index.

Is there any way to fix this and abort in this case?

Karsten
  • 1,814
  • 2
  • 17
  • 32
  • Note also that an alternative selection method using a heap will be faster than QuickSelect when you're selecting less than 1% of the items. See http://blog.mischel.com/2011/10/25/when-theory-meets-practice/ for details. If you're selecting the top 1,000 items from a list of millions, for example, then use the heap selection algorithm. – Jim Mischel May 04 '15 at 17:08
  • 1
    do a three-way partition instead of two-way - pick one pivot, and partition into smaller, equals, and greater elements. – Will Ness May 05 '15 at 00:05

1 Answers1

2

Quickselect is based on the Quicksort-Algorithm.

According to Quicksort complexity when all the elements are same? , Quicksort can hit its worst-case time-complexity when all the elements are equal.

The link also provides a solution [1] how to speed up Quicksort. Since Quickselect is based on Quicksort, a similar solution might help you.

  • [1] The solution mentiones a partitioning-idea. CS.SE has some question that does include code and compares 2 partitioning algorithms for Quicksort, namely the approach suggested by Lomuto and the one by Hoare: CS.SE: Quicksort Partitioning Hoare vs Lomuto.
    The marked answer also states that Hoare's variant is more efficient, while Lomuto's is easier to implement correctly. So depending on your situation, the latter might be sufficient.

  • [2] QuickSort and Hoare Partition

Community
  • 1
  • 1
Slizzered
  • 869
  • 2
  • 9
  • 23
  • This seems promising, but the answer you linked to is too vague for me to implement it that way... – Karsten May 04 '15 at 16:56
  • 1
    @Karsten I added 2 links to questions dealing with the implementation of this partitioning algorithm (and the different variants as proposed by Hoarde and Lomuto), hope it helps you! – Slizzered May 04 '15 at 17:02