Online Sorting Algorithm for fixed size array/list

Question

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]

MAK · Accepted Answer · 2011-07-15 16:12:56Z

5

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).

answered Jul 15, 2011 at 16:12

MAK

26.6k11 gold badges57 silver badges86 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

anasimtiaz Over a year ago

Thanks, I'm looking at skip lists now.

Fabio Over a year ago

Should be balanced binary trees

MAK Over a year ago

@Fabio: yes, but better to introduce a simpler data structure before showing the more complicated version.

user684934 · Accepted Answer · 2011-07-15 16:13:53Z

3

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.

answered Jul 15, 2011 at 16:13

user684934

2 Comments

anasimtiaz Over a year ago

No, its not homework. Its work. And since I'm not from a Comp Sci background I am not aware of the algorithms used and their advantages.

Don Reba Over a year ago

Slightly offtopic, but in practice, linked lists are often slower than arrays even when insertions and deletions are common, because memory is heavily optimized for sequential traversal.

James · Accepted Answer · 2011-07-18 05:44:59Z

1

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.

answered Jul 18, 2011 at 5:44

James

8,6361 gold badge28 silver badges27 bronze badges

Comments

K'' · Accepted Answer · 2011-07-21 19:43:00Z

0

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

answered Jul 21, 2011 at 19:43

K''

5,2987 gold badges35 silver badges43 bronze badges

Collectives™ on Stack Overflow

Online Sorting Algorithm for fixed size array/list

4 Answers 4

3 Comments

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related