QuickSelect works in linear time

QuickSelect is a selection algorithm that finds the kth smallest number from a list. QuickSelect is O(n) algorithm. I built a simple prototype to verify that QuickSelect works in linear time.

QuickSelect uses a random pivot to partition the array. The items to the left of the pivot are lesser than the pivot. The items to the right of the pivot are greater than the pivot. After the partition, the position of pivot is checked for the kth element. Depending on the position of the pivot, the remaining array is recursively partitioned till the kth element is found. The code for QuickSelect is below:

class QuickSelect
{
    private int _start = 0;
    private int _end = 0;
    private int _iteration = 1;
    private Random _random = new Random();

    public int GetMedian(int[] array)
    {
        var list = new LinkedList<int>(array);
        _start = 0;
        _end = array.Length - 1;

        return Select(list, array.Length / 2, _start, _end);
    }

    private int Select(LinkedList<int> list, int index, int start, int end)
    {
        // Print.PrintList(list);

        if (start == end)
            return GetNode(list, start).Value;

        int pivot = start + _random.Next(end - start + 1);
        if (pivot != start)
        {
            var startNode = GetNode(list, start);
            var pivotNode = GetNode(list, pivot);
            AddBefore(list, startNode, pivotNode);
        }

        // Console.WriteLine("Start: {0}, End: {1}, Pivot: {2}", start, end, pivot);
        int newPivot = Partition(list, start, end);

        if (newPivot == index)
        {
            return GetNode(list, newPivot).Value;
        }
        else if (newPivot > index)
        {
            _end = newPivot - 1;
            return Select(list, index, _start, newPivot - 1);
        }
        else // if(newPivot < index)
        {
            _start = newPivot + 1;
            return Select(list, index, newPivot + 1, _end);
        }
    }

    private int Partition(LinkedList<int> list, int start, int end)
    {
        //var watch = new Stopwatch();
        //watch.Start();

        var endNode = GetNode(list, end).Next;
        var pivotNode = GetNode(list, start);

        int pivot = start;
        var curNode = pivotNode.Next;
        while (curNode != endNode)
        {
            if (curNode.Value < pivotNode.Value)
            {
                var tmpNode = curNode.Next;
                AddBefore(list, pivotNode, curNode);
                pivot++;
                curNode = tmpNode;
            }
            else
            {
                curNode = curNode.Next;
            }
        }
        //watch.Stop();
        //Console.WriteLine("Iteration {0} took {1} ms", _iteration++, watch.ElapsedMilliseconds);
        return pivot;
    }

    private void AddBefore(LinkedList<int> list, LinkedListNode<int> node, LinkedListNode<int> newNode)
    {
        list.Remove(newNode);
        list.AddBefore(node, newNode);
    }

    private LinkedListNode<int> GetNode(LinkedList<int> list, int index)
    {
        int pos = 0;
        var node = list.First;
        while (pos < index)
        {
            node = node.Next;
            pos++;
        }
        return node;
    }
}

QuickSelect uses a random pivot. So, the running time of the algorithm for the same input varies based on the chosen pivot. The average running time of QuickSelect varies linearly by the input size. For this experiment, five array sizes of 50K, 100K, 200K, 500K, 1000K were used to measure the running times. The result of the experiment is shown below:

QuickSelect

The running time is shown in milliseconds. For million numbers, QuickSelect runs at an average of 1.064 seconds. The final column shows the slope of the line. It is roughly between 0.8 and 1.1. It is nice to see for myself that QuickSelect works in linear time.

Related Posts

Leave a Reply

Your email address will not be published.