[missing feature] irrArray needs an addSorted function

[Ulf]

I needed a sorted array so just started looking at irrArray.

The irrArray can be sorted at any time.
The irrArray has some binary search functions that can obviously only be used when the array is in a sorted state. That's fine.

Don't you think the irrArray should have an addSorted functionality?
That is, you pass it the object, and it gets placed into the array sorted.
O(logn) per insert.

Otherwise, the whole array must be sorted after any insert or addition to the array. That seems a bit silly.

There are many cases where you don't just build the whole array and use it once.. or just keep using it as is.
You may want to keep it for the lifetime of the executable, adding and removing objects, and calling upon randomly so to speak.
It needs to be always sorted or else in the best case you will have to rebuild the heap in the same order, moving just one object (the object inserted after the last sort on the array).

Doesn't it need that? I mean shouldn't it have that?
It's simple to implement.

[BlindSide]

Yeah this makes sense. We need a better core::map too. I'll move this to bug reports.

[Ulf]

Yep. I knew this was a must.
Thanks Blindside.

[hybrid]

Well, we won't be able to make it any better than you could already do, it just saves some code from your app. Simply go through the array until your order check fails, then do an insert(). Also, what would insertOrdered do on a non-sorted array? And do you need a merge sort for adding another array?

[Ulf]

Well, we won't be able to make it any better than you could already do, it just saves some code from your app.

AND it implements something that should be part of a sorted array.
It should be in it. It makes sense.

Simply go through the array until your order check fails, then do an insert()

Yea, and that is O(n^2). Loop thru array, then move all nodes to the right of it by one position.

Also, what would insertOrdered do on a non-sorted array?

Firstly, it's called addSorted or addOrdered... NOT INSERT.
SO WHAT IT WOULD DO IS ADD IT TO THE END. THE ARRAY IS NOT SORTED!@!!!!!!

And do you need a merge sort for adding another array?

I suppose now you are just being an @##hole? Is that a good guess?.. Or after saying all the other stuff now you are serious?
Did I mention mergesort?...
Mergesort gives same result as heapsort so NO.

Anyway, a mergesort is easy to write.. Easier than heapsort.
I don't even know why I am answering you about that!

[CuteAlien]

Well, we won't be able to make it any better than you could already do, it just saves some code from your app. Simply go through the array until your order check fails, then do an insert(). Also, what would insertOrdered do on a non-sorted array? And do you need a merge sort for adding another array?

I think we have no way so far to use a binary_search to find a location to insert. We can only use binary_search to find existing items. Otherwise the user could do it with a binary_search, insert, set_sorted(true) combination. So unless I miss something it seem that insert could be speeded up in an sorted array.

@Ulf: I don't really get why you explode that much. Also just for adding something to the end I also fail to see how it would make sense as you can do that already.

[hybrid]

Simply go through the array until your order check fails, then do an insert()

Yea, and that is O(n^2). Loop thru array, then move all nodes to the right of it by one position.

Ok, since duplicates are desired for arrays, you could do the move together with the linear search. And coming from the back you could save N/2 accesses. And no, n^2 is not necessary even for the separated thing, you'd only have O(2N) which is still O(N).

Also, what would insertOrdered do on a non-sorted array?

Firstly, it's called addSorted or addOrdered... NOT INSERT.
SO WHAT IT WOULD DO IS ADD IT TO THE END. THE ARRAY IS NOT SORTED!@!!!!!!

Your CapsLock is stuck, try to fix your keyboard first. Next, look at the irrArray API and search for methods that are called add*(). Then search for methods that are named insert*(). The result should convince you that it will be called insertSorted or insertOrdered.

And do you need a merge sort for adding another array?

I suppose now you are just being an @##hole? Is that a good guess?.. Or after saying all the other stuff now you are serious?
Did I mention mergesort?...
Mergesort gives same result as heapsort so NO.

Anyway, a mergesort is easy to write.. Easier than heapsort.
I don't even know why I am answering you about that!

Seems like you didn't even try to understand what I said. If you add a method to insert one element sorted, it would be logical to extend this method to adding a whole array in an ordered fashion.
This would merge the two arrays (if both are sorted), otherwise you'd get O(N*M) which would be far from the optimal O(N+M) the merge sort would achieve.

And yes, your communication skills are also suboptimal.

[hybrid]

Well, we won't be able to make it any better than you could already do, it just saves some code from your app. Simply go through the array until your order check fails, then do an insert(). Also, what would insertOrdered do on a non-sorted array? And do you need a merge sort for adding another array?

I think we have no way so far to use a binary_search to find a location to insert. We can only use binary_search to find existing items. Otherwise the user could do it with a binary_search, insert, set_sorted(true) combination. So unless I miss something it seem that insert could be speeded up in an sorted array.

Ah, extending the binary_search to find the place faster could save some comparisons, yes. Would depend on the costs for comparison compared to the (always linearly for every element executed) memory moves.

[Ulf]

@Ulf: I don't really get why you explode that much.

Hmmm.. I got a bad temper. I got no job, and I'm going insane.
I suppose I do read into things incorrectly sometimes. I had the shits with Hybrid before too, a few months ago.. haha. Sorry.
I am a headcase sometimes.
I read stuff like below and it shits me.

Well, we won't be able to make it any better than you could already do, it just saves some code from your app.

It's strange to me. Don't matter. I suppose I am strange.
I suppose I took it as sarcasm, and then I determined that the rest of the questions hybrid asked were not sincere.

I must be insane...

Also just for adding something to the end I also fail to see how it would make sense as you can do that already.

All I meant was that if someone tries to use the addOrdered, or insertOrdered on an unsorted array, it can just call the push_back function.

The function is called addOrdered in my opinion because you don't give it an index. You just add it, either in order or to the end if unsorted.
But I suppose insertOrdered does make sense, just don't give an index. yes that sounds right... EXCEPT for the fact that if not sorted, the item gets pushed onto the back of the array. So should it be called add?
The item should/must be pushed onto the back when not sorted simply for efficiency.

Seems like you didn't even try to understand what I said.

True.
I'll pull my head in and try harder. Ok?

Ok, since duplicates are desired for arrays, you could do the move together with the linear search. And coming from the back you could save N/2 accesses. And no, n^2 is not necessary even for the separated thing, you'd only have O(2N) which is still O(N).

It is O(n^2) isn't it?
For EACH insert or addition you do a linear search to find the place.
That is O(n).
Then you have to move up to a MAX of N elements. Even if it's N/2 or N/1000, it's still N. I know it matters how many comparisons and other operations occur as well.
But, when you are talking about a large N, it's still as good as N^2.

If it is O(N), it's the best binary insert I ever seen.

The best sorts are nlogn, in general cases. So the best inserts are nlogn. The search is logn. The insert is N. NlogN.

Am I confused?

@hybrid: if you are serious about the mergesort, then I'd say it's not necessary.
You said

If you add a method to insert one element sorted, it would be logical to extend this method to adding a whole array in an ordered fashion.

If you are merging 2 arrays, you may as well just put the elements in a new array and sort it using heapsort. Because you won't use the new array until the 2 arrays are merged.

The insertSorted functionality keeps an array sorted as you use it.
After any insert you can still use it as sorted.
Merging 2 arrays cannot be sorted until finished and you aren't going to try to pull stuff out of the array until you merge them anyway.
Does that make sense?

And yes, your communication skills are also suboptimal.

yea no worries. No hard feelings. I know you are very skillful and knowledgeable.

I think we have no way so far to use a binary_search to find a location to insert.

Ah, extending the binary_search to find the place faster could save some comparisons, yes.

Hmmm. I don't think a search function should be used or modified to insert. Or did I misunderstand?

The insert can be modified, but it doesn't make sense because insert requires an index.

Making a new function would make it more clear. IMO.

[CuteAlien]

<snip> and I'm going insane.<snip>

It's that c++ language - didn't I tell you it's dangerous using that for too long? ;-)

Hmmm. I don't think a search function should be used or modified to insert. Or did I misunderstand?

I was thinking about a new search function. Or basically - I was thinking how I would do it in stl. And there you could use lower_bound followed by insert. Because our insert automatically resets the sorted flag a call to set_sorted(false) would have to follow (stl doesn't remember that for you). Actually I suppose about every algorithm in stl will sooner or later be requested in every of our core-classes. Anyway - the search gives more information which can also be used otherwise and allows to do the same thing. With 3 lines instead of one, but as this is rather a special case using 3 lines is ok.

[Ulf]

It's that c++ language - didn't I tell you it's dangerous using that for too long?

I knew I was insane when I loved the freedom of C/C++ and all my friends loved the safety of Java.

On the topic of a new ordered insert:
I don't mind how it's implemented, except to say that I'm seeking an insert function that works in O(nlogn) time, just like the heapsort that sorts the whole array.
If the array is not sorted, it should push onto the back of the array OR possibly more consistent would be to sort the array and then insert the item in order with the new function.
Not 100% about that one.

I haven't actually looked into the implementation of heapsort.
When the array is sorted with heapsort, is it possible to insert into the heap without moving other elements? Or does the heap need a re-ordering function?

As I think about it, it's not so easy.. is it?
Because, the heapsort just sorts the array in nlogn time, but it doesn't keep any reference to the heap does it? It just returns an array.
So, it's not really possible to do a ordered insert in nlogn.
Is it? Still need to move the array elements over...

[CuteAlien]

Is it? Still need to move the array elements over...

Yes, you can only find the index faster, inserting still has to happen with usual insert.

[Ulf]

Yea, ok. That's still what I was looking for.
.. Starting to confuse myself ..