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$

closed as off-topic by Bill Greene, Tyler Olsen, Kirill, nicoguaro Aug 13 '18 at 15:57

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "General computer science questions are off-topic here, but can be asked on Computer Science Stack Exchange." – Bill Greene, Tyler Olsen, Kirill, nicoguaro
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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.