CODEWITHSUNDEEP
algorithmsorting
Oleg Vazhnev
Oleg Vazhnev

Reputation: 24067

algorithm to keep sorted order of changing array

I have 20-items array which contains decimal numbers. They are unsorted. On every iteration only several items of the array change (~1-3 items of 20-items array). After each iteration I need to have the same array but "sorted".

I shouldn't modify original array, instead I need to maintain "parallel" structure which represents the same array, but sorted. It's allowed to use pointers.

I do care about latency so I need straighforward solution! Obviously I can use double-linked list to "remember" sort order, but I will spent K*O(n) (with pretty big K) to update this list what sound a little bit to expensive. I'm looking for something better that two-linked list.

i will implement this on c# if this matter

Upvotes: 1

Views: 2734

Answers (2)

AlexWien
AlexWien

Reputation: 28727

Just use two structures: This is straightforward, robust since you use existing well working collectsions, and cheap by implementation costs:

Use two collections:

One unsorted: e.g in java ArrayList whch is a dynamic growing array
One sorted: use whatever you want.
Both "collections" as usual, point to the content object.

To make things threadsafe in case of multi threading:

encapsulate both collections in one class, where you syncronize all access, such that reading and writing to both collections is ever synced.

Upvotes: 0

amit
amit

Reputation: 178441

Assuming you keep track of the 1-3 changed elements, it can be done pretty efficiently using a single step of merge-sort, and an extra iteration over the array

  1. Collect all elements into two arrays changed and notChanged1 - in order.
  2. sort changed (for 1-3 elements, it should be fairly easy and quick).
  3. use merge(changed,notChanged) to get a sorted array

The complexity is O(n) with pretty good constants I believe, since merge() is done in a single iteration and so does the collection phase. Also, since we are still using arrays, this approach should be pretty cache efficient.

(1) Note that notChanged is sorted, because the not changed elements are sorted between themselves!

Upvotes: 3

Related Questions