1
$\begingroup$

I would like to insert elements into a ring (circular) buffer one at a time and maintain a permutation array which keeps track of the sorted elements in ascending order. To do this, I have adapted the "Insertion Sort" algorithm to use circular array indexing:

/* sort ringbuf entries with insertion sort algorithm */
void
ringbuf_isort(const ringbuf *rbuf, int *idx)
{
  const int n = ringbuf_n(rbuf);
  int i, j;

  for (i = 1; i < n; i++)
    {
      int id = idx[i];
      double v = rbuf->array[(rbuf->head + id) % rbuf->size];

      for (j = i; j > 0; j--)
        {
          if (rbuf->array[(rbuf->head + idx[j-1]) % rbuf->size] < v)
            break;

          idx[j] = idx[j-1];
        }

      idx[j] = id;
    }
}

This algorithm works correctly - the idx array contains the permutation of the buffer elements which tracks their sorted status. The problem is that the algorithm is extremely slow, due to the modular arithmetic needed for the circular indexing, i.e. (head + idx) % size.

In fact, I have found it is faster to simply copy the ring buffer into a linear array and use a quicksort algorithm each time an element is added, rather than use the code above. For a linear array, I have confirmed the insertion sort algorithm outperforms quicksort when only a single element is changed, so I am hoping I can find a better solution for the ring buffer.

Does anyone know how to optimize the code above to speed up the modular arithmetic (or avoid it altogether?)

$\endgroup$
  • $\begingroup$ Welcome to scicomp! This question is a pure CS question, so it would be better suited for cs.stackexchange or stackoverflow. $\endgroup$ – Tyler Olsen Aug 13 '18 at 4:32

Browse other questions tagged or ask your own question.