StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I think you need to take a big step back from the problem and try to solve it as a whole - chances are good that the semi-sorted circular buffer is not the best way to store your data. If it is, then you're already committed and you will have to write the buffer to sort the elements - whether that means performing an occasional sort with an outside library, or doing it when elements are inserted I don't know. <strong>But at the end of the day it's going to be ugly because a FIFO and sorted buffer are fundamentally different.</strong></p> <hr> <p><em>Previous answer, which assumes your sort library has a robust and feature filled API (as requested in your question, this does not require you to write your own mod sort or anything - it depends on the library supporting arbitrary located data, usually through a callback function. If your sort doesn't support linked lists, it can't handle this):</em></p> <p>The circular buffer has already solved this problem using % (mod) arithmetic. QSort, etc don't care about the locations in memory - they just need a scheme to address the data in a linear manner.</p> <p>They work as well for linked lists (which are not linear in memory) as they do for 'real' linear non circular arrays.</p> <p>So if you have a circular array with 100 entries, and you find you need to sort the top 10, and the top ten happen to wrap in half at the top, then you feed the sort the following two bits of information:</p> <ul> <li>The function to locate an array item is (x % 100)</li> <li>The items to be sorted are at locations 95 to 105 </li> </ul> <p>The function will convert the addresses the sort uses into an index used in the real array, and the fact that the array wraps around is hidden, although it may look weird to sort an array past its bounds, a circular array, by definition, has no bounds. The % operator handles that for you, and you might as well be referring to the part of the array as 1295 to 1305 for all it cares.</p> <p>Bonus points for having an array with 2^n elements.</p> <hr> <h2>Additional points of consideration:</h2> <p>It sounds to me that you're using a sorting library which is incapable of sorting anything other than a linear array - so it can't sort linked lists, or arrays with anything other than simple ordering. You really only have three choices:</p> <ul> <li>You can re-write the library to be more flexible (ie, when you call it you give it a set of function pointers for comparison operations, and data access operations)</li> <li>You can re-write your array so it somehow fits your existing libraries</li> <li>You can write custom sorts for your particular solution.</li> </ul> <p>Now, for my part I'd re-write the sort code so it was more flexible (or duplicate it and edit the new copy so you have sorts which are fast for linear arrays, and sorts which are flexible for non-linear arrays)</p> <p>But the reality is that right now your sort library is so simple you can't even tell it how to access data that is non linearly stored. </p> <p>If it's that simple, there should be no hesitation to adapting the library itself to your particular needs, or adapting your buffer to the library.</p> <p>Trying an ugly kludge, like somehow turning your buffer into a linear array, sorting it, and then putting it back in is just that - an ugly kludge that you're going to have to understand and maintain later. You're going to 'break' into your FIFO and fiddle with the innards.</p> <p>-Adam</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload