Online Sorting Algorithm for fixed size array/list

What would be the best way to maintain and sort a fixed-size array (or linked list?)? To make situation clear, suppose that 100 samples of data are stored in a buffer (assume they're sorted for simplicity), then when the next sample comes in, oldest one goes out and the new sample must be put in the buffer in a location such that its sorted.

What would be the best way to store these samples, arrays or linked list? And how to sort the list for the latest chunk of开发者_开发技巧 sample?

[Initially the buffer may be initialized to 0]

Both arrays and linked lists are pretty bad to keep data that must be kept sorted after each update. Either have to resort the list (O(nlogn)) after an update, or insert/remove/move the new element to its appropriate position in the sorted list (O(n)).

A better idea is to use a data structure that is inherently sorted and maintains that property after each update in O(log(n)). Both binary search trees and skip lists have that property. Many languages have a container that is implemented as a fast sorted data structure (e.g. set in C++ and TreeSet in Java).

Is this homework?

Either way, it sounds like the answer you're looking for is the heap-backed priority queue. As MAK pointed out, both arrays and linked lists have linear time inserts. Linked lists seem like they'd be nicer because they would have constant-time extractions, but the extract-and-insert procedure takes asymptotically linear time anyways. Heaps (and other tree structures) allow for logarithmic extraction and inserts.

Basically, you have two sorts here - one sort by value, one by time. You might consider a balanced BST for the value sort, and maintain a simple queue of pointers/references (depending on language) for the time-based sorting (assuming you're removing the "oldest" value in terms of when it was added, not some external timestamp).

insert: add to BST add to queue if queue.size() > MAX_SIZE: node_to_remove = queue.dequeue() BST.remove_node(node_to_remove)

Add to BST = O(lg n), add to queue = O(1), remove from BST = O(lg n) - so your inserts are still O(lg n), which is basically the best you can do for a sorted insert anyhow.

Probably a heap tree will be good. You can use the Merge sub routine in Merge sort with a little modification.