Re: Sorting an array. Fastest way.

Andreas Leitgeb wrote:
Lew <lew@xxxxxxxxxxxxx> wrote:
Sanny wrote:
I have an array of int.

Given an initially sorted collection, the first element is
modified/replaced, and the collection needs to be re-sorted.

For an array, this means the described "algorithm":
I find using binarydearch the position "pos" where the ist elewment
need to go.
Then I do arraycopy to shift all elements by 1 and copy the 1st
element to the "pos" position.

Since the expensive part is shifting, it appears obvious that a
collection that allows easy inserting/removal of items may be
better, but unfortunately I think that such structures do not
behave as well with binary search (which requires random index
addressing)

I'm not entirely sure about other possible disadvantages, but
it looks like TreeMap or TreeSet might be an optimal collection
for OP's needs.

A TreeMap, which implements a red-black balanced binary tree, will give reasonable performance with any size of data set. Its performance isn't degraded by loading pre-ordered data: this is a problem with simple (unbalanced) unbalanced binary tree algorithms. Red-black trees are never blindingly fast, but don't have performance black holes either.

Operations on a TreeMap won't be as fast as on an array, but they don't degrade badly for a small dataset and do become spectacularly fast for extremely large data sets. When the tree is very small the search degenerates toward a sequential search, but as the data set grows the number of key comparisons drops dramatically - it can find a match from 8388608 entries with only 23 key comparisons. The only drawback is that an amendment that changes the key MUST be a deletion followed by an insert to maintain the tree's ordering, so an amendment will take approximately twice as long as a search.

A binary search on an ordered array will be quicker than walking the tree, but any array insertion involves either resorting the entire array or moving all higher keys up a cell to make space for the new value. Deletions and key amendments have similar large overheads for large data sets.

Finding the insertion point and making the insertion in a tree is much faster. Same applies to a deletion. A key amendment is simply a deletion plus an amendment.


--
martin@ | Martin Gregorie
gregorie. | Essex, UK
org |
.

Relevant Pages

  • Re: Easy balanced tree
    ... The tree can hold between 4 and 7 values, if it was lower than 4 ... then the array would be smaller so we ignore those cases. ... Secondly there is wasted space in the middle of the array (with ... rdrop nip nip; ...
    (comp.lang.forth)
  • Re: Is it possible to have mutable-in-place (associative-)array objects in PHP?
    ... This is the way all languages work. ... just that array variables aren't objects ... and for each I must find the appropriate path in the tree I'm ... treeptr <- rootOfTree ...
    (comp.lang.php)
  • Re: [opensuse] Recover md RAID-1.
    ... md: md0 stopped. ... Then try booting the array with just /dev/sdb1 as a member. ... A ball hitting a tree shall be deemed not to have hit the tree. ...
    (SuSE)
  • Re: data structure for network protocol
    ... As a first thought, I was considering linked lists, but they are probably ... The second option is tree. ... hash tables. ... in an ordinary array (the main cost is that, if the number of items gets ...
    (comp.programming)
  • Re: array moving left
    ... I have an array in which elements are present. ... Instead maintain a binary tree of deletion points. ... The left child weight of a node is the number of nodes under it on the ... deletions have occurred to the left of the element. ...
    (comp.programming)
Loading