CODEWITHSUNDEEP
c#.netalgorithmsorting
enzom83
enzom83

Reputation: 8320

Most efficient way to sort a circular buffer

I've implemented a circular buffer using a fixed-length array. In order to point to the start of valid data, I use an index (_startIndex). Similarly, in order to point to the end of valid data, I use another index (_endIndex). Below is an example.

  9   8   7   6   5   4   3   2   1   0   <-- array indices
  3   2   1   0                   5   4   <-- buffer indices
-----------------------------------------
|   |   |   |   |   |   |   |   |   |   |
-----------------------------------------
              ^                   ^
             _startIndex         _endIndex

Now I need to rearrange the elements of this buffer: the smallest element should be moved to position 0 of the buffer, while the largest element should be moved to position 5 of the buffer.

My idea is based on the following method.

int GetArrayIndex(int bufferIndex)
{
    return (_startIndex + bufferIndex) % LENGTH;
    // LENGTH is the length of the array
}

In this way, the sorting algorithm could read the buffer sequentially, using the above method, without therefore having to be aware that the buffer consists of two non-contiguous portions of the same array. Are there better ways to sort a circular buffer?

Upvotes: 3

Views: 2823

Answers (3)

Jim Mischel
Jim Mischel

Reputation: 134085

If you want to do an in-place sort, then you should compress the buffer first. That is, make it one contiguous block from index 0 to index 5.

Then you can call the Array.Sort(T[], index, length) overload to sort that portion of the array.

You can move the items with a single operation, once you figure out what to move, and where.

There are three cases:

  1. start_index == 0: No movement needed

  2. start_index < end_index: Number of items to move is (end_index - start_index + 1). Move items from start_index through end_index to positions '0' through 'count-1'

  3. start_index > end_index: There is a "hole" in the array (as you've shown). You need to move items from start_index through the end of the array to position array.length - start_index - count.

Once you figure out the source and destination positions, you can call Buffer.BlockCopy to move the items.

I should note that, after the move and sort is done, you can set start_index to 0, and end_index to count-1. Or, if you really want the buffer to be in the same state it was in before (just with re-ordered items), you can move things back using the same kind of logic I described above. Why you'd want to do that is unclear.

Upvotes: 7

user287107
user287107

Reputation: 9417

I would propose implementing a modified quicksort.

quicksort is a "divide and conquer" algorithm, which means dividing the set into two pieces, and then continuing. your buffer is already splitted into two parts, they just need to be adjusted. the the first step would be sorting the two pieces, the first piece at the beginning of your array, and the second piece at the end of your array. you would just "presort" the elements so that every element in the second part is smaller than any part in the first part. then you can apply the quicksort algorithm to every piece and you are sorted

Upvotes: 1

Zoran Horvat
Zoran Horvat

Reputation: 11311

Simple solution:

  1. Move elements so that values occupy positions 0, 1, ... , M-1, where M is number of used positions in the array.
  2. Modify _startIndex = 0 and _endIndex = M-1
  3. Call Array.Sort on part of the buffer between 0 and _endIndex inclusively.

This solution runs in O(M) steps to rearrange elements and O(MlogM) to sort them, which totals O(MlogM) time. In other words - time required to rearrange elements to the beginning of the buffer is negligible compared to time required to sort them.

Alternative solution is to sort first and second part of the buffer separately and then to merge sort them to the beginning of the array. Running time is equal (slightly larger, to be precise), and code is more complicated.

Upvotes: 1

Related Questions