Dominance Tree Sorts

Dominance Tree Sorts

"Dominance tree sorts" is a neologism.  If anyone recognizes this 
class of sorts I would take it kindly if they would point to the 
literature (web preferred) where this class of sorts is described 
and named.  The idea doesn't seem to be explored in Knuth, though 
something may be hidden in the exercises.  Dominance tree sorts 
aare selection sorts but not tournament sorts.

Suppose we have a set S of elements and an ordering relationship 
R defined over S.  For example, S might be an array of integers, 
and R might be >, the greater than relationship.  Let x and y be 
two elements of S.  Element x is said to dominate y if (x R y).  
Again from the example, let x be 8 and y be 5.  Then x dominates 
y.

A dominance tree T over S is a tree such that (a) every element 
of S appears exactly once in T, and (b) for every element (except 
the root) the element's parent dominates it.  Here are some 
examples of dominance trees over the set {1,2,3,4,5}

          A          B        C

          5          5        5
          |          |        |
       -------     -----      4
       | | | |     |   |      |
       1 2 3 4     4   2      3
                   |          |
                  ---         2
                  | |         |
                  1 3         1
                  
Heaps are dominance trees, but not all dominance trees are heaps.  
Example B is a heap, example C is a sorted list, and in example A 
all we know is that '5' is maximal.  

A set K of comparisons (xRy) is a minimum comparison set for 
a dominance tree T if it consists exclusively of the comparisons
in the child/parent linkages.  Thus, in our example, the minimum 
comparison sets are:

K(A):  5>1, 5>2, 5>3, 5>4
K(B):  5>4, 5>2, 4>1, 4>3
K(C):  5>4, 4>3, 3>2, 2>1

Note that a minimum comparison set always has n-1 members where n 
is the cardinality of S.

An algorithm is an efficient dominance tree construction (EDTC) 
algorithm if it specifies a minimum comparison sequence that in 
turn specifies a dominance tree.

One of the important features of EDTC algorithms is that if an 
element 'loses' in a comparison it cannot appear in a later 
comparison in the comparison's sequence.  Another is that there 
is no EDTC algorithm that can guarantee that the root element has 
less than log2(n) children.  In particular there are no 
EDTC algorithms for creating heaps.

The general plan for dominance tree sorts runs as follows:  For a 
given set S we first construct a dominance tree T.  We then emit 
the root of the tree.  The children of the root are compared 
until a new root is established. In each comparison the 'loser' 
becomes a new child of the 'winner'.  EDTC algorithms are used in 
both the initial construction phase and in each emission step.  
There are quite a number of variations depending on which EDTC 
algorithms are used.

There are two major EDTC algorithms that occur to me.  The first 
is tournament pairing, also used in the tournament sort and in 
heapsort.  In the tournament pairing algorithm the set is divided
into pairs that are compared.  The winners go on to the second 
round where they are again divided into pairs that are compared.  
This is continued until a final winner is determined.  This 
requires n-1 comparisons, log2(n) rounds, and the winner, the 
root of the tree, will have log2(n) children.

The second is sequential comparison.  The first element in a 
list is compared with the second.  The winner is compared with 
the third, and so on.  This also requires n-1 comparisons.  The 
number of children of the root depends on the location of the 
root element in the list.  If the ordering of the list elements 
is random, the average number of children will n/2.  On the other 
hand, the number of children will be 1 if the list is ordered.

It turns out that we get a very efficient (as measured by the 
number of comparisons used) sort if we use tournament 
pairing to construct the initial dominance tree and sequential 
comparison in the update after emission of the root.  Each 
element has a list associated with it of elements that it 
dominates.  During construction when one element dominates 
another the losing element is appended to the winning elements 
list.  Here is a very simple example.  Let the set to be sorted 
be {2,4,3,1}.  The actions are: 

    Construction Phase
        compare (2,4); append 4 to 2's list
        compare (3,1); append 3 to 1's list
        compare (2,1); append 2 to 1's list; 1 is the root
    Emission Phase
        emit (1); compare (3,2); append 3 to 2's list; 2 is root
        emit (2); compare (3,4); append 4 to 3's list; 3 is root
        emit (3); 4 is root
        emit (4); done 

How efficient is this sort?  The tests that I ran showed it to 
about equivalent to merge-insert (see Knuth, Vol 3, 5.3.1).  For 
example, sorting 32 items requires a minimum of 118 comparisons 
on average (log2(32!)).  Merge-insert needs 121.  The number 
needed by the above algorithm depends on the precise permutation.  
The average number needed is about 121.5.  For large n the number 
of comparisons required was ~ n*(log2(n) - 1.27) in the tests I 
performed; this is not far off from the best possible of whic is
~ n*(log2(n) - log2(e)) = n*(log2(n) - 1.44).

Why is this sort efficient?  It has to do with an order 
preservation property in the construction and updating of the 
dominance lists.  In the construction phase a dominance list has 
two special properties: (a) its length is longer than the lengths 
of the lists of the elements in its list, and (b) the elements in 
the list are in order of the length of their lists.  These 
properties are almost always preserved by the above algorithm.  
In turn this implies that the lengths of the dominance lists are 
slightly less than O(log2(n)) on average.

Can this be improved upon?  Possibly.  The only 
reference I can find to dominance tree sorts is a web article by 
someone called Supercat.  In the web article he in effect forces 
property (b) to hold.  (He calls it a tournament sort which is a 
bit of a misnomer.)  He gives the following results for a test 
case sorting one million items.

Number of comparisons by a perfect sort (lg(n!)) : 18,488,865
Avg # of comparisons for Tournament Sort: 18,646,425 
   (100.85% of perfect)
Avg # of comparisons for Borland C's qsort: 22,439,507 
   (121.37% of perfect)

This gives (n = 1000000) n*(log2(n) - 1.284) which is tad better 
than the simpler algorithm given here.  On the other hand 
Supercat's version requires addition comparisons of the element 
weights (integers rather than keys).

Is this a practical sort?  Possibly not.  It requires extra space 
O(n) for the lists and O(n) for the list headers.  Each 
comparison involves adding an item to a linked list, so the 
cost of the inner loop operations will be higher than it is in 
simpler sorts.  On the other hand memory is often plentiful and 
the inner loop costs should be no worse than those for an 
ordinary tree sort.


References:
   URL:   http://www.halfbakery.com/idea/Tournament_20Sort
   Title: Tournament sort
   
   Knuth, The Art of Computer Programming, Vol 3, Searching
   and Sorting.

Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Tragedy is living to an old age 
and not having any enemies to outlive.
0
cri (1432)
8/17/2004 9:08:50 PM
comp.programming 10955 articles. 0 followers. Post Follow

5 Replies
487 Views

Similar Articles

[PageSpeed] 39
On Tue, 17 Aug 2004 21:08:50 GMT, cri@tiac.net (Richard Harter) wrote:

>
>Dominance Tree Sorts
Oops, should have been comp.theory.  Mea Culpa.


Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Tragedy is living to an old age 
and not having any enemies to outlive.
0
cri
8/17/2004 9:11:34 PM
On Tue, 17 Aug 2004 21:08:50 GMT, cri@tiac.net (Richard Harter) wrote:


[snip original]

In the original text it is stated that a dominance tree is not a heap,
even though a heap is a dominance tree.  There are a couple of
corrections to make here.  The first is that 'heap' should have been
'binary heap'.  The second is that dominance trees have the heap
property and accordingly are heaps in the most general sense of
'heap'.

No mention is made in the original of fibonacci heaps and fibonacci
heap sorts.  There is an intimate relationship betweem fibonacci heap
sorts and the dominance tree sorts mentioned in my article.  However
they are different animals.

"Dominance tree sorts" may not be entirely appropriate since a
dominance tree is a heap.  However the appropriate names have all been
appropriated.

It should be possible to create a heap type that corresponds to the
heap structure used in dominance tree sorts.  I will look into this
and report my findings.




Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Tragedy is living to an old age 
and not having any enemies to outlive.
0
cri (1432)
8/23/2004 6:28:45 PM
In article <41227327.365327442@news.sbtc.net>, cri@tiac.net (Richard Harter) writes:
> 
> Each 
> comparison involves adding an item to a linked list, so the 
> cost of the inner loop operations will be higher than it is in 
> simpler sorts.  On the other hand memory is often plentiful and 
> the inner loop costs should be no worse than those for an 
> ordinary tree sort.

On the other other hand, all that linked-list traversal likely means
poor locality of reference, which means bad cache effects.  Which,
come to think of it, is generally true of heap sorts.  If you keep
the children as an array rather than a linked list (overflows can be
handled in various ways) that should help.

Interesting idea and nice writeup, though.  I'm still thinking about
it.  On casual inspection it does look like it might be quite
amenable to being parallelized, and with SMP systems becoming ever
more common that's certainly useful.  (Of course, mergesorts are
inherently parallel and very easy to code.)

-- 
Michael Wojcik                  michael.wojcik@microfocus.com

Auden often writes like Disney.  Like Disney, he knows the shape of beasts --
(& incidently he, too, might have a company of artists producing his lines) --
unlike Lawrence, he does not know what shapes or motivates these beasts.
   -- Dylan Thomas
0
mwojcik (1879)
8/26/2004 7:57:18 PM
mwojcik@newsguy.com (Michael Wojcik) wrote in message news:<cglfau0kjv@news1.newsguy.com>...
> In article <41227327.365327442@news.sbtc.net>, cri@tiac.net (Richard Harter) writes:
> > 
> > Each 
> > comparison involves adding an item to a linked list, so the 
> > cost of the inner loop operations will be higher than it is in 
> > simpler sorts.  On the other hand memory is often plentiful and 
> > the inner loop costs should be no worse than those for an 
> > ordinary tree sort.
> 
> On the other other hand, all that linked-list traversal likely means
> poor locality of reference, which means bad cache effects.  Which,
> come to think of it, is generally true of heap sorts.  If you keep
> the children as an array rather than a linked list (overflows can be
> handled in various ways) that should help.

Performance problems with heapsort are often blamed on cache effects.
No doubt this is true; however the standard heapsort has further problems
that degrade perfomance.  An obvious one is the complexity of the inner
loops.  

A more subtle issue is that the heapify process throws information
away. For example suppose we have three elements x,y,z at locations
a[n], a[2*n], a[2*n+1] and we heapify them.  We first compare y and z
and pick the dominant one, z for the sake of argument.  We then compare 
z with x, the top point in our little heap; if it dominates x we swap, 
moving z up and x down.  We now have a[n] > {a[2*n],a[2*n+1]} and that is
all we have.  However if x was the dominant one we lose the information that
a[2*n+1] > a[2*n].  That is, the data structure doesn't distinguish between
x>z>y and z>x,z>y; in the former case it records x>z (true by transitivity)
and x>y, but not z>y.  In effect 1/3 of a decision is lost.  This information
loss occurs at several points in the standard heap sort.  For this reason
the required number of comparisons for heapsort is n*[a*log2(n)+b] where a>1.

This kind of information loss does not occur either quicksort or mergesort.
Using a simplified analysis of the mergesort cost function we get 
n*(log2(n)-1.0), which is pretty close to the optimal n*(log2(n)-log2(e)).
Although quicksort doesn't throw information away, it doesn't use it
quite as efficiently (partitions are equisized) so its 'a' is greater than 1.
As noted the dominance tree sort (my version anyway) has a comparison cost
function of ~ n*(log2(n)-1.27) or better (on random data), which is better 
than mergesort but not by much.  

I'm not sure that putting the linked lists in arrays helps particularly with
the cache problem although it is easy enough to put them in arrays.  The
catch is that the references in the linked lists are scattered.  There may
be something clever that one can do with moving the data so that cache misses
are reduced but I haven't thought it out though.


> Interesting idea and nice writeup, though.  

Thanks.

>I'm still thinking about
> it.  On casual inspection it does look like it might be quite
> amenable to being parallelized, and with SMP systems becoming ever
> more common that's certainly useful.  (Of course, mergesorts are
> inherently parallel and very easy to code.)

Offhand it seems quite straightforward to parallelize it.

As a final note both mergesort and quicksort are intrinsically cache
friendly as long as there are at least two caches.
0
cri (1432)
8/28/2004 3:14:34 PM
On Tue, 17 Aug 2004 21:08:50 GMT, cri@tiac.net (Richard Harter) wrote:

>
>Dominance Tree Sorts
>


[snip original article]

I have looked into this matter in some detail.  In particular I have
gone through the relevant sections of Knuth, vol 3, Sorting and
Searching.  One problem here is that my copy is the 1973 edition (I
don't know what changes, if any, are in later editions.)  In
consequence there is a lot of more modern material, e.g., fibonacci
heaps, that is not included.  That said:

(1) A dominance tree is a heap (using the most general definition of
heap) with the additional requirement that each element loses in a
comparison no more than once.  There doesn't seem to be any need for
"dominance trees" as a description of a data structure.  On the other
hand the the term "dominance tree sorts" is useful since the term
"heap sorts", which ought to refer the class of sorts based on heaps
has instead been preempted as the label for a particular kind of
binary heap sort. 

(2) The category of dominance tree sorts is broader than that of
tournament sorts; however the standard tournament sort is isomorphic
to a dominance tree sort in which the tree is constructed using
tournament pairing and then in the selection phase the child lists of
each selection is processed sequentially.

(3) Tournament sorts (and the equivalent dominance tree sorts) are
highly efficient in terms of the average number of comparions and the
minimax number of comparisons required.  Both quicksort and heapsort
require substantially more; mergesort is comparable but is slightly
more costly.  Merge-Insert (Johnson-Trotter) sorts are slightly more
efficient but the gain is minimal.  

(4) Tournament sorts have the same comparison cost function as binary
insertion sorts.  However binary insertion sorts are expensive in
terms of data move costs.  Tournament sorts are better in terms of
data move costs but have (IMHO) messy data structures.  The equivalent
dominance tree sorts have "nicer" data structures.



 
Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Tragedy is living to an old age 
and not having any enemies to outlive.
0
cri (1432)
9/21/2004 6:28:18 AM
Reply:
Similar Artilces:

Sorting strings containing special characters (german 'Umlaute')
Hi ! I know that this topic has been discussed in the past, but I could not find a working solution for my problem: sorting (lists of) strings containing special characters like "=E4", "=FC",... (german umlaute). Consider the following list: l =3D ["Aber", "Beere", "=C4rger"] For sorting the letter "=C4" is supposed to be treated like "Ae", therefore sorting this list should yield l =3D ["Aber, "=C4rger", "Beere"] I know about the module locale and its method strcoll(string1, string2), but current...

Validation a DOM-Tree (Document-Instance) with a XML-Schema
Hi, I like to validate a XML-Document-Instance (below =doc). /**********************java-Code************************* ********************************************************* */ DocumentBuilderFactory dbf=null; Document doc=null; dbf = DocumentBuilderFactory.newInstance(); DOMParser dp=new DOMParser(); DocumentBuilder db=null; try { db = dbf.newDocumentBuilder(); } catch (ParserConfigurationException e2) { // TODO Automatisch erstellter Catch-Block e2.printStackTrace(); } doc=db.newDocument(); Element e=doc.createElementNS("xsi","root" ); Attr at=doc.createAttrib...

sort order -- first by sender, then by date
i am finding that the sort by sender in pine does not correctly sort by the message sent date (or the arrival date for that matter) consistently within the first results. is this because there is no concept of sort by date within sort by sender, or is this a bug? i tried using mutt and it could do the right thing, so it seems like the data to do the sorting is availabe in the message headers. does anyone know of a patch, or configuration option that fixes this. ...

[News] Linux Dominates in Xmas Gifts, Volunteers Reach Out
Tux Droid delivers a very Merry Linuxmas ,----[ Quote ] | Although it could be argued that your average fanboy has already got the | present they wanted this xmas in the continuing growth of Linux in terms of | both actual deployment and media popularity, or maybe the arrival of the | Linux server for Unreal Tournament 3 or even the fact that the BBC iPlayer is | now Linux compatible. But no, believe me, when they see the dancing plastic | penguin that announces the arrival of new email all that will change. `---- http://www.daniweb.com/blogs/entry1904.html See entries below. The...

Sorting clients by incremental number in Report.
One of the fields I have is a Client Number which is entered manually in a Table. This Column is sorted ascending in a Report I have, but insted of sorting them incremental ascending the Report sorts them by the figure they start with, then the second figure etc, so I end up with Client 1 beeing Nr 1 and Client 11 beeing Nr 2 ... How can I sort them incremental ascending (normal way). Julian Suspect that your client number is a text field instead of a numeric field Phil "Julian" <x@x.x> wrote in message news:4keg2fFbq757U1@individual.net... > One of the fields I have i...

Is there a way to sort filters in 5.2?
It seems that allofasudden a LOt of the mail I want is now going to my trash folder, I may have mistakenly made a trash filter for them. Is there any way to sort the filter list by date or any other way? TIA. Paul FF <FredFarkle@laffaminute.com> wrote: > It seems that allofasudden a LOt of the mail I want is now going to my > trash folder, I may have mistakenly made a trash filter for them. Is > there any way to sort the filter list by date or any other way? Filters don't have dates. And there is no mechanism provided for sorting filters because filters wor...

grouping hashrefs to trees
I need to group hashrefs into branches where every instance in branch has something in common with others. The problem is that no one can tell which attribute will be dominant, so I guess there should be some counting before actual grouping into branches. Please tell me that somebody already has invented the wheel. :) my @rules = ( { 'source-port' => 23, protocol => "tcp", }, { source => '6.11.6.6/24', }, { protocol => 'udp', 'source-port' => 53, source => '64.11.6.6', ...

increasing the record length for sort command
How to increase the default record length for the sort command on solaris 10 on sparc 64? Thanks On 10 Mai, 21:58, heylow <vnr1...@gmail.com> wrote: > How to increase the default record length for the sort command on > solaris 10 on sparc 64? >From "man sort" of Solaris 10: -z recsz (obsolete). This option was used to prevent abnormal termination when lines longer than the system-dependent default buffer size are encountered. Because sort automatically allocates buff...

How to save in database binary tree values
hi, send me the qurey to save the values like binarytree when we enter in jsp file, and also send me how to retrive the values to display like binary tree in jsp file. ...

Eudora Return address, all personalities default to the dominate email address
I have a client who is running Eudora as I am here. But all his out bound m= ail from all the personalities are using the dominate return address even t= hough the personalities real name, email name and login are properly set fo= r that personality . I can not duplicate this on my Eudora. Any ideas? Dan On Thu, 11 Dec 2014 13:04:07 -0800 (PST), ddawdy@ribbonrail.com wrote: >I have a client who is running Eudora as I am here. But all his out bound mail from all the personalities are using the dominate return address even though the personalities real name, email name and login...

command "rm -rf" can't remove whole directory tree on ZFS
Dear All, I had create a ZFS file system called auth and create a directory under auth called online. I have observed the following issue: when I try to remove with "rm -rf online", only the regular files will be removed on Solaris 10 u4 when doing so on a ZFS file system. If I rm -rf as root it works but as normal user it doesn't, though the directory privilege are okay (750 for the owning user trying to remove) and have no any error messages. Anyone can help me to solve this problem? Thank you. OS: Solaris 10 update 4 Machine: V245 jimmy wrote: > Dear All, > ...

spanning tree 284886
Do I have to use spanning tree in a stack configuration? We have a stack of eight cisco 3750 catalyst switches, we don't use uplinks. The master switch has a link to the router. I have spanning tree enabled for preventing loops. I thinks in this config i cannot get a loop? But are there disadvantages of enabeling spanning tree? We have about 60 terminal servers connected to this switches and some novell 6.0 file-servers.. Any information will be great.. Thanks. In article <bc932412.0405140819.1db42d57@posting.google.com>, David Reinhart <d.reinhart@vedior.nl> wrote: :Do I ...

[Uniface-L] Tree Widget
Hi Sorry my bad english. I'm uniface developer in Romagnole - Brazil. I need to know how to create dynamic collums in the Tree Widget (List View) or what event resizing Collumn in list View of the Tree Widget? Thanks ...

Re: proc sort performance #2
Consider the implications of this 9.2 documentation for your question: ------------------------------ TAGSORT Option The TAGSORT option in the PROC SORT statement is useful in sorts when there might not be enough disk space to sort a large SAS data set. When you specify TAGSORT, the sort is a single-threaded sort. Do not specify TAGSORT if you want the SAS to use multiple threads to sort. When you specify the TAGSORT option, only sort keys (that is, the variables specified in the BY statement) and the observation number for each observation are stored in the temporary files. The sort ke...

is this true? sort algo on STL Lists
I just came accross this : "Note that the STL sort algorithm does NOT work for lists; that's why a sort member function is supplied." Is this true? Has this been fixed in newer versions of the STL? Bit byte wrote: > I just came accross this : "Note that the STL sort algorithm does NOT > work for lists; that's why a sort member function is supplied." > > Is this true? Yes. std::sort requires random-access iterators, which std::list does not supply. > Has this been fixed in newer versions of the STL? There's nothing to fix. If you need t...

Dominant Email address
Hi I want to designate a different email address as the dominant. How do I switch them this status? Thanks, On Fri, 31 Dec 2004 18:29:47 GMT, BobT <ebco@(nospam)prodigy.net> wrote: >Hi >I want to designate a different email address as the dominant. How do >I switch them this status? >Thanks, You change what you have entered in Tools -> Options -> Getting started. There's no easier way to do it. -- Ajo Wissink ...

Reverse sorting an array
Hello, Thanks to those replied to the other thread I started - guess I was being too 'clever' with using methods. Can you please tell me why this code won't _compile_? import java.util.*; class InputCounter { public static void main(String[] args) { final int MAX_NUMBERS = 50; int[] array = new int[MAX_NUMBERS]; Arrays.sort(array, Collections.reverseOrder()); } } TIA, Fred On 9/30/2011 7:03 AM, Fred wrote: > Hello, > > Thanks to those replied to the other thread I started - guess I was > being too 'clever' with using methods. > > Can you p...

dominance
"Microsoft's Windows operating system enjoys incredible dominance on the world's computers. Research firm IDC estimates that 94.4 percent of new computer operating systems sold in 2003 were Windows products." http://www.msnbc.msn.com/id/7544247/ [cola bozos better start coming to grips with reality. People want Windows. People buy Windows. Windows is not going away, ever] DFS wrote: > "Microsoft's Windows operating system enjoys incredible dominance on the > world's computers. Research firm IDC estimates that 94.4 percent of new > computer ...

If doesn't Pam sort about?
I restore scientific laces by now the nineteenth-century favourite pocket, whilst Petra quickly lends them too. He'll be registering onto general Darin until his aircraft entertains ever. Better sing desktops now or Katherine will purely encounter them inside you. Do not pass secondly while you're updating away from a impressed bell. You usually widen distinguished and captures our old, conceptual jungles by means of a ceiling. Just emerging according to a collar towards the sea is too retired for Rifaat to fund it. Occasionally Peter will confess the inspection, and if ...

Android continues to dominate the global smartphone market
http://www.idc.com/prodserv/smartphone-os-market-share.jsp The worldwide smartphone market grew 25.3% year over year in the second quarter of 2014 (2014Q2), establishing a new single quarter record of 301.3 million shipments, according to data from the International Data Corporation (IDC) Worldwide Quarterly Mobile Phone Tracker. This is the first time ever quarterly smartphone shipments have surpassed the 300 million unit mark, representing a major milestone for the industry. Following a very strong first quarter, the market grew 5.2% sequentially, fueled by ongoing demand ...

Pass code reference to sort function
I'm trying to build a very minimal ETL tool using Perl. I'm trying as much as possible to abstract the gory details of reading, writing and generally processing the data by providing a pre-built pipeline into which users can plug various bits of functionality. One of the pieces that I'd like to plug in is the ability to sort data retrieved from a data source. What I'd like to do is to have the user specify the block to be used by the sort function, something like the following: $csv = ETL::Builder::CSV('/my/file/name') ; $sort_block = sub { $a->{Bid} cmp $b{Bid} ...

Determine the dominant value in an array (or dominant color in an image)?
I'm trying to determine if there is an easy way to find the dominant color in a basic image. I am starting with an RGB image, but eventually end up with just a single 2 dimensional array of data. I simply want to determine within a large array if the majority values contained within are for example equal to 255. Any help is appreciated. On Sep 15, 9:36 pm, "Rob " <robrol...@hotmayl.com> wrote: > I'm trying to determine if there is an easy way to find the > dominant color in a basic image. I am starting with an RGB > image, but eventually end up with just ...

[News] Google Starts Using Its Web Dominance to Fight Against Microsoft's Browser
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Google's Microsoft-esque landgrab for IE's market share ,----[ Quote ] | Fair? Yes. A bit sneaky? You bet. Clint Boulton at eWeek sees it as a way to | promote Chrome, and he's right. Google now regularly hawks its own Chrome | browser on its search page, the same page that 63.5 percent of the world | uses. In true Microsoft fashion, Google is going to tie its products | together, making a holistic experience that ostensibly helps customers while | bludgeoning competitors. `---- http://news.cnet.com/8301-13505_3-10130301-16...

Sort-Problem
Hi, with the code below the output is sort by $verantw but $title and $file in the same row DON'T belong to $verantw. How do I have to make the sort command that $verantw, $title and $file in the row "belongs together"? Hope you understand my problem...... <?php $handle = opendir('.'); $daten = array(); $daten['files'] = array(); $daten['title_tags'] = array(); $daten['verantw'] = array(); while ($file = readdir($handle)) { if (substr($file, -4) == '.htm') { $daten['...

need help regarding tree datastructures
hi all, i was trying to write code for binary search tree insertion using c,with linked lists but i'm getting segmentation fault,can someone help me to underatsand tree better... thanking u all in advance hema hema wrote: > i was trying to write code for binary search tree insertion using > c,with linked lists but i'm getting segmentation fault,can someone help > me to underatsand tree better... > thanking u all in advance I suspect it's your code doing something wrong. Could you post a short, compilable piece of code that demonstrates your problem? (note: us...