6
\$\begingroup\$

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(n3) as far as I can think of.

\$\endgroup\$
  • \$\begingroup\$ There are two reasons I see to reject quickselect: 1) code/algorithmic complexity 2) O(n) memory or modification of the input. If the input can be inspected more than once, there are a number of procedures promising O(nlogn) time using little (additional) memory. So you want a code review of your counting sort & median determination code, and no suggestions modifying input or using substantial additional memory? How about O(nlogn) time, O(logn) space? \$\endgroup\$ – greybeard Apr 24 at 7:35
  • \$\begingroup\$ I would surely enjoy an algorithm with O(nlog(n)) but considering the input array I am not very much in favor of using an auxiliary space O(n) \$\endgroup\$ – Liger Apr 24 at 16:29
  • \$\begingroup\$ Just to keep a note, I was just mad at this, and how can such a simple problem does not have any efficient solution. Torben's Median Algorithm works charm, the main property of this algorithm is, "Bigger the array gets, better the algorithm becomes"! It dosen't sort the array. For odd number of elements, it returns the middle and for even it returns n/2 highest value. There is a slight improvement of this on github for even sized arrays to return actual median! Obviously it's better with O(log(N)) \$\endgroup\$ – Liger Apr 25 at 23:55
  • \$\begingroup\$ What is Torben's Median Algorithm? \$\endgroup\$ – greybeard Apr 26 at 5:42
  • \$\begingroup\$ You can find the source code here ndevilla.free.fr/median/median/src/torben.c \$\endgroup\$ – Liger Apr 26 at 11:37
7
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Wow! This significantly reduces the time required! Is that O(n)? I used Torben's method earlier which is O(log(N)) but this is even faster and much faster indeed! Can you throw some light on time complexity? I just changed the way to create a frequency array, did not incorporate any changes related to excessive temporary memory. \$\endgroup\$ – Liger Apr 24 at 16:32
  • 1
    \$\begingroup\$ You should be able to reason about the complexity yourself - it looks to me that it should be O(n) in time and O(max) in space. The multi-pass approach trades time for space: O(n log n) and O(1) respectively. \$\endgroup\$ – Toby Speight Apr 24 at 17:14
2
\$\begingroup\$

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";
}
\$\endgroup\$
  • \$\begingroup\$ (Nits: 1) in AboveBelow(), you take advantage of pguess->Value > i excluding < i: in FindMinMax(), initialise min & max to the first element of rgint to do the same. 2) in AboveBelow(), tol id unused 3) <climits> 4) whence round()?) In FindMedian, I'd expect below <= above + equal && above <= below + equal to cause less problems (median of [1, 2, 3]). \$\endgroup\$ – greybeard Apr 25 at 4:20
  • \$\begingroup\$ Thanks @greybeard. Keen eye and points well made - except for 3)... How/why should <climits> (not) be used? (Not doubting, in need of educating;-) All others items accepted and code updated. \$\endgroup\$ – AlanK Apr 25 at 19:25
  • \$\begingroup\$ I'm no expert in C++ standards. The online environment I used to tinker with the code presented complained about INT_MIN/MAX without <climits> - way back when those appeared. \$\endgroup\$ – greybeard Apr 25 at 20:17
  • \$\begingroup\$ I tried it with random array and I feel it gets stuck in an infinite loop for some inputs. I'll figure out the cases and will post it here \$\endgroup\$ – Liger Apr 26 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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