1

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

Improve this question
6
  • Your original array however is modified to at least include the added items right? I assume each new item is added to the bottom of your original array? Commented Dec 5, 2012 at 16:43
  • If the application remembers which elements actually changed, you could move these "hot" items to there appropiate places, using insertion sort (memmove) or a "partial" bubblesort like method. If you insist on linked lists: finding the odd ones takes one sequential pass, sorting it is 3log(3), and remerging it is O(N) again. BTW: 20 is small. Maybe you don't need to keep it sorted. Commented Dec 5, 2012 at 16:44
  • @user1161318 items are not added. array also has constant size of 20. items only modify Commented Dec 5, 2012 at 16:51
  • @wildplasser i need to iterate array in sorted order pretty often Commented Dec 5, 2012 at 16:52
  • An other way would be to use a parallel index- or offset- (or even pointer-) array, which is modified, keeping the original array unaltered. This could be useful if the array elements are big or vary in size. Commented Dec 5, 2012 at 17:00

2 Answers 2

Reset to default
3

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!

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

1 Comment

sorry i don't understand that. i already have one original unsorted array where 1-3 elements change on each "iteration". how many extra arrays do I need? what is merge?
0

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.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.