2
\$\begingroup\$

I tried to implement https://en.wikipedia.org/wiki/Quickselect

quickselect is a selection algorithm to find the k-th smallest element in an unordered list.

this is the Pseudo code I was following

In quicksort, there is a subprocedure called partition that can, in linear time, group a list (ranging from indices left to right) into two parts: those less than a certain element, and those greater than or equal to the element. Here is pseudocode that performs a partition about the element list[pivotIndex]:

function partition(list, left, right, pivotIndex)
     pivotValue := list[pivotIndex]
     swap list[pivotIndex] and list[right]  // Move pivot to end
     storeIndex := left
     for i from left to right-1
         if list[i] < pivotValue
             swap list[storeIndex] and list[i]
             increment storeIndex
     swap list[right] and list[storeIndex]  // Move pivot to its final place
     return storeIndex

This is known as the Lomuto partition scheme, which is simpler but less efficient than Hoare's original partition scheme.

In quicksort, we recursively sort both branches, leading to best-case O(n log n) time. However, when doing selection, we already know which partition our desired element lies in, since the pivot is in its final sorted position, with all those preceding it in an unsorted order and all those following it in an unsorted order. Therefore, a single recursive call locates the desired element in the correct partition, and we build upon this for quickselect:

  // Returns the k-th smallest element of list within left..right inclusive
  // (i.e. left <= k <= right).
  // The search space within the array is changing for each round - but the list
  // is still the same size. Thus, k does not need to be updated with each round.
  function select(list, left, right, k)
     if left = right        // If the list contains only one element,
         return list[left]  // return that element
     pivotIndex  := ...     // select a pivotIndex between left and right,
                            // e.g., left + floor(rand() % (right - left + 1))
     pivotIndex  := partition(list, left, right, pivotIndex)
     // The pivot is in its final sorted position
     if k = pivotIndex
         return list[k]
     else if k < pivotIndex
         return select(list, left, pivotIndex - 1, k)
     else
         return select(list, pivotIndex + 1, right, k)

Please review the coding style and clarity

using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace ArrayQuestions
{
    [TestClass]
    public class QuickSelect
    {
        [TestMethod]
        public void QuickSelectAlgoTest()
        {
            int[] arr = {9, 8, 7, 6, 5, 0, 1, 2, 3, 4};
            int[] res = Select(arr,  6);
            for (int i = 0; i < 6; i++)
            {
                Assert.IsTrue(res[i] <= 6, $"The res[i] {res[i]} was not greater than six");
            }
        }

        //Partially sort array such way that elements before index position n are smaller or equal than element at position n
        //And elements after n are larger or equal.
        public int[] Select(int[] input,int n)
        {
            //keep original array
            int[] partiallySortedArray = (int[])input.Clone();
            int startIndex = 0;
            var endIndex = input.Length - 1;
            var pivotIndex = n;
            Random r = new Random();
            while (endIndex > startIndex)
            {
                pivotIndex = QuickSelectPartition(partiallySortedArray, startIndex, endIndex, pivotIndex);
                if (pivotIndex == n)
                {
                    break;
                }
                if (pivotIndex > n)
                {
                    endIndex = pivotIndex - 1;
                }
                else
                {
                    startIndex = pivotIndex + 1;
                }

                pivotIndex = r.Next(startIndex, endIndex);
            }

            return partiallySortedArray;
        }

        private int QuickSelectPartition(int[] array, int startIndex, int endIndex, int pivotIndex)
        {
            int pivotValue = array[pivotIndex];
            Swap(ref array[pivotIndex], ref array[endIndex]);
            for (int i = startIndex; i < endIndex; i++)
            {
                if (array[i].CompareTo(pivotValue) > 0)
                {
                    continue;
                }
                Swap(ref array[i], ref array[startIndex]);
                startIndex++;
            }
            Swap(ref array[endIndex], ref array[startIndex]);
            return startIndex;
        }

        private void Swap(ref int i, ref int i1)
        {
            int temp = i;
            i = i1;
            i1 = temp;
        }
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ @dfhwze this is like explaining what bubble sort is... I will edit, but Wiki link is the best description. \$\endgroup\$
    – Gilad
    Jun 24, 2019 at 19:26

2 Answers 2

5
\$\begingroup\$

Separate code and test. It's great that you've written a unit test, but the test code should be in a separate class (and typically a separate project) from the code under test.

The testing could also be a bit more exhaustive. Given the same input you can test each value of n: it'll still run in milliseconds. A separate test could handle repeated elements. A third test could handle the extreme of repeated elements: if you have an array of length one million where every element is the same and you give n = arr.Length / 2, does the performance take a nose-dive? I suspect it does, and that's something you might want to address with a Dutch flag partition. Other corner cases would be n = -1 or n = arr.Length: at present, I don't think either of those is particularly well handled.


Select as a name makes sense in context, but when you think about embedding it in a large project or library it isn't very specific. Naming things is hard: my best suggestion after two minutes' thought is PartitionAroundMedian.


pivotIndex is doing double duty. I think it would be clearer to separate out those duties; since I'm received a comment that this point was unclear, the first step in refactoring this would be

            var pivotIndexIn = n;
            Random r = new Random();
            while (endIndex > startIndex)
            {
                var pivotIndexOut = QuickSelectPartition(partiallySortedArray, startIndex, endIndex, pivotIndexIn);
                if (pivotIndexOut == n)
                {
                    break;
                }
                if (pivotIndexOut > n)
                {
                    endIndex = pivotIndexOut - 1;
                }
                else
                {
                    startIndex = pivotIndexOut + 1;
                }

                pivotIndexIn = r.Next(startIndex, endIndex);
            }

In fact, QuickSelectPartition doesn't strictly need to receive pivotIndexIn as an argument at all. If the reason for passing it in is to have a clear lifecycle of r, pass r instead.

Note that the scope of pivotIndexOut is narrowed to inside the loop body.

Since I'm talking about names: r is awful. My convention for instances of Random is to call them rnd; others might prefer random or rng (for random number generator).


I find it inconsistent to use the primitive type int for the array elements but CompareTo instead of the primitive > to compare them. Since it costs nothing, I would change the first: genericise the quick-select to operate on T where T : IComparable<T>.


The decision that Select does not modify its input can be reflected in the type signature by changing it from array to IReadOnlyList<> (or perhaps IEnumerable<> - see below). Similarly the return type could be IList<> or IReadOnlyList<> to indicate the expectation the method has of its user. (Personally I'd favour IList<>).


Select, QuickSelectPartition, and Swap don't use any instance members of the class, so you need a good reason not to make them all static. In fact, I'd be strongly tempted to make Select an extension method public static IList<T> PartitionAroundMedian<T>(this IEnumerable<T> elements, int n) where T : IComparable<T>.


            for (int i = startIndex; i < endIndex; i++)
            {
                if (array[i].CompareTo(pivotValue) > 0)
                {
                    continue;
                }
                Swap(ref array[i], ref array[startIndex]);
                startIndex++;
            }

There are times when a quick-reject and continue makes for readable code. I don't think this is one of them.

            for (int i = startIndex; i < endIndex; i++)
            {
                if (array[i].CompareTo(pivotValue) <= 0)
                {
                    Swap(ref array[i], ref array[startIndex]);
                    startIndex++;
                }
            }

is shorter and doesn't require mental effort to invert the condition.


            while (endIndex > startIndex)
            {
                pivotIndex = QuickSelectPartition(partiallySortedArray, startIndex, endIndex, pivotIndex);
                if (pivotIndex == n)
                {
                    break;
                }
                ...
            }

            return partiallySortedArray;

I'd cut to the chase by putting the return where the break is.


Minor quibbles on whitespace: there's inconsistency over whether , in an argument list is followed by a space or not. And I'd prefer to put a blank line after every } unless the following line is another } or directly related to it (e.g. the else is directly related to the if block).

\$\endgroup\$
3
  • \$\begingroup\$ Could you be more specific about pivotIndex is doing double duty, I don't see that? if (array[i].CompareTo(pivotValue) <= 0): Isn't it rather the original > that should be >= \$\endgroup\$
    – user73941
    Jun 25, 2019 at 9:39
  • 1
    \$\begingroup\$ @HenrikHansen, I've expanded on that first point. On the second, I was making an observation about readability rather than correctness. I haven't actually analysed for correctness: I just preserved the existing behaviour. Perhaps you could find a test case which the original code fails and add it to your answer? \$\endgroup\$ Jun 25, 2019 at 10:21
  • \$\begingroup\$ OK, that is a very orthodox definition of double duty IMO :-). About the > vs <= - I were just referring to the wiki pseudo code. \$\endgroup\$
    – user73941
    Jun 25, 2019 at 11:57
4
\$\begingroup\$

You are using an iterative approach which is normally faster than a recursive. That's a good optimization.


            if (array[i].CompareTo(pivotValue) > 0)
            {
                continue;
            }
            Swap(ref array[i], ref array[startIndex]);
            startIndex++;

Why not just:

      if (array[i].CompareTo(pivotValue) < 0)
      {
        Swap(ref array[i], ref array[startIndex]);
        startIndex++;
      }

      pivotIndex = r.Next(startIndex, endIndex);

The wiki is doing so but I don't see why instead of just taking the middle:

pivotIndex = startIndex + (endIndex - startIndex) / 2;

You could measure on a larger data set to see if there is any average difference in performance?


$"The res[i] {res[i]} was not greater than six"

Strictly speaking: you are not finding values lesser than 6 but the six smallest values in the data set. (n or k is an index not a value)

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I think you are right. \$\endgroup\$
    – Heslacher
    Jun 25, 2019 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.