Finding median from unsorted array with duplicate elements without sorting it

Question

I am implementing a method to find the median of an unsorted array using a counting sort. I would happily go for a median of medians or selection algorithm for better performance but they are essentially sorting the array (or partially sorting the array if I choose to go for minHeap) which I am not in favor of.

int getRange(int *array, int count)
{
    int i, max = 0;
    for(i = 0; i < count; i++)
    {
        if(array[i] > max)
        {
            max = array[i];
        }
    }
    return max;
}

int countFreq(int *array, int size_array, int item)
{
    int i, freq = 0;
    for(i = 0; i < size_array; i++)
    {
        if(array[i] == item)
            freq++;
    }
    return freq;
}

int median(int *array, int count)
{
    int range = getRange(array, count);
    int i, mid_index, addition = 0;

    //Yes I can use calloc here
    int *freq = (int *)malloc(sizeof(int) * range + 1);
    memset(freq, 0, sizeof(int)* range + 1);

    for(i = 0; i < range + 1; i++)
    {
        //Count i in array and insert at freq[i]
        freq[i] = countFreq(array, count, i);
    }

    if(count % 2 == 0)
    {
        mid_index = count / 2;
    }
    else
    {
        mid_index = count / 2 + 1;
    }

    for(i = 0; i < range + 1; i++)
    {
        addition += freq[i];
        if(addition >= mid_index)
        {
            break;
        }
    }
    free(freq);
    return i;
}

I followed this answer to implement using C. Certainly, I want to improve upon this or maybe a better algorithm that doesn't sort the array. For me, this algorithm has some problems:

1. What if there are just 2 elements, say {10, 10000}; this will still go on for creating an array of size 10000 which essentially has zeros in it except at the last index.

2. I find it hard to digest the performance of this algorithm with larger arrays to sort, for now, this is O(n³) as far as I can think of.

Answer 1

If we never modify the elements of array, then it should be passed as a pointer to const: int const *array.

The frequency counts can be unsigned, and ought to be able to represent any size of input array (that suggests that count should be a size_t).

We absolutely must test that the return value of malloc() (and family) is not null before trying to dereference it (including passing it to memset()). Additionally, it's not necessary or desirable to cast it to the target type:

size_t *freq = calloc(sizeof *freq, range + 1);
if (!freq) {
    fputs("Memory allocation failed!\n", stderr);
    exit(EXIT_FAILURE);
}

The algorithm has undefined behaviour if any element in the array is less than zero. We need to find the minimum as well as maximum value, or perhaps change the input to be an unsigned type.

The counting is strange, with the nested loop. Normally, we'd loop just once, incrementing the index for each element we look at - something like this:

for (int i = 0;  i < count;  ++i) {
     ++freq[array[i]];
}

To avoid excessive temporary memory use for the count array, we could use a multi-pass approach.

• Divide the range [min,max] into into (say) 256 buckets.
• Count the inputs into those buckets.
• Identify the median bucket. Call that M.
• Now divide the range represented by M into buckets.
• Make another pass over the inputs, counting values within M into these new buckets (discarding values not in M).
• Repeat until the bucket size is 1.

Answer 2

I like @toby-speight's answer (and have up-voted). He's reviewed your code. Here's the result of scratching my head for an hour while driving home FWIW.
One up-side is it should deal with all ints.
Temporary (working) storage requirement is O(1).
Time complexity obviously a lot worse - I estimate ~O(nlog n) but haven't put too much thought into it. E&OE.

/*  THE APPROACH
 *  ************
 *  This is not exactly a code review, but an algorithm suggestion
 *  Based on trading off between
 *    (i)   O(n) intermediate storage (for counts) and
 *    (ii)  reducing storage at the cost of increasing time-complexity
 *  Obviously I'm going down rabbit hole (ii) (given points 1 & 2 following your code)
 *  Thought process something like this...
 *  - Not allowed to sort
 *  - Can't keep counts
 *  - How to search?
 *    - Need max and min entries, costing 1 pass over the array (count n)
 *    - Worst-case search is binary "chop", costing O(log n) PASSES (O(n log n) (hope I've got that thumb-thuck right;-)
 *    - Improvement maybe possible... let's see how we go
 *  - Note adopted definition: median of 1,2,3,4 (even number of data points) is (2+3)/2
*/

#include <iostream>
#include <vector>
#include <climits>

size_t nPasses = 0;

void FindMinMax(const std::vector<int>& rgint, int& min, int& max)
{
  min = max = rgint[0];
  for (auto i : rgint)
  {
    if (i < min) 
      min = i;
    else if (i > max) 
      max = i;
  }
}

struct DataPointInfo
{
  double Value{};
  int low{};
  int high{};
  int nearestBelow = INT_MIN;
  int nearestAbove = INT_MAX;
  size_t countBelow = 0;
  size_t countEqual = 0;
  size_t countAbove = 0;
};

void AboveBelow(const std::vector<int>& rgint, DataPointInfo* pguess)
{
  pguess->countAbove = pguess->countBelow = pguess->countEqual = 0;
  pguess->nearestBelow = INT_MIN;
  pguess->nearestAbove = INT_MAX;
  for (auto i : rgint)
  {
    if (pguess->Value > i)
    {
      pguess->countBelow++;
      if (i > pguess->nearestBelow) 
        pguess->nearestBelow = i;
    }
    else if (pguess->Value < i)
    {
      pguess->countAbove++;
      if (i < pguess->nearestAbove) 
        pguess->nearestAbove = i;
    }
    else pguess->countEqual++;
  }
}

double FindMedian(const std::vector<int>& rgint)
{
  int min, max;
  FindMinMax(rgint, min, max);
  nPasses++;
  DataPointInfo dpi{ (static_cast<double>(min) + max) / 2, min, max };
  do
  {
    AboveBelow(rgint, &dpi);
    nPasses++;
    if (dpi.countBelow <= dpi.countAbove + dpi.countEqual && dpi.countBelow + dpi.countEqual >= dpi.countAbove) 
      return dpi.countEqual > 0 ? dpi.Value : (static_cast<double>(dpi.nearestBelow) + dpi.nearestAbove) / 2; //  found
    if (dpi.countBelow < dpi.countAbove)  //  must be "to the right"
      dpi.low = dpi.nearestAbove;
    else  //  must be "to the left"
      dpi.high = dpi.nearestBelow;
    dpi.Value = (static_cast<double>(dpi.low) + dpi.high) / 2;
  } while (true);
}

int main()
{
  const std::vector<int> testData{ 1,2,3,8,3,2,3,5,0,1,2,7,6,5,4,2,3,4,5,9 };
  double median = FindMedian(testData);
  std::cout << median << " found in " << nPasses << " passes over the dataset";
}