Algorithms

3-Apr-09 4:00

You create a binary tree where the leaves represent the tournament's contestants. Each pair of contestants under an interior node play a match, and the winner then occupies that interior node.

Likewise, an interior node that has two other interior nodes under it represents the winner of the match between the winners corresponding to those two interior nodes.

The root of the binary tree represents the winner of the tournament.

Tree construction: One approach uses the Composite design pattern, an abstract Node class with two derived classes: Contestant and InteriorNode. Start with a list of Contestants. While that list has more than one element, combine two elements under a new InteriorNode, remove those elements from the list, and insert the new InteriorNode in the list. The list should be ordered by increasing depth, so that, for example, all Contestants are paired before any InteriorNodes are paired.

When the list is down to one element, that's the root of the tree.

modified on Friday, April 3, 2009 10:21 AM

Tree algo

dfreeser2-Apr-09 5:58

2-Apr-09 5:58

Is there an algorithm that does a upside-down, upside-down tree. i.e, right side up(root on bottom). Thanks.

Alan Balkany3-Apr-09 3:43

3-Apr-09 3:43

Tree algo:

1. Grasp page in both hands.
2. Turn page 180 degrees.

dfreeser3-Apr-09 5:15

3-Apr-09 5:15

Very insightful. I see why your an expert now. Would have never figured that one out myself.

Quick question. If said tree isn't on paper but on my computer screen, do I grab the computer screen and flip it 180 degrees or the computer itself.
Big Grin | :-D

Alan Balkany3-Apr-09 5:42

3-Apr-09 5:42

Seriously, it wasn't clear what your problem was. Do you just want to draw the tree upside down on the screen? If so, for a display of height H, substitute (H - y) for every y coordinate to flip the tree.

dfreeser3-Apr-09 6:02

3-Apr-09 6:02

Sorry. I want to know if is something like treeview but where the root is on the bottom and everything goes up.

Alan Balkany3-Apr-09 6:16

3-Apr-09 6:16

Oh, I thought you might be interested in an algorithm, since this is the Algorithms forum and your title was "Tree algo". Since you're looking for a suggestion on a graphics package, you might want to post your question in the Lounge.

dfreeser3-Apr-09 6:33

calculate polygon area and its centre in 3d

3-Apr-09 6:33

Sorry. I'll try there. Thanks for your help.

beko31-Mar-09 22:57

beko

31-Mar-09 22:57

Hello,

I have some 3d points (not self intersecting). the shape of the points is looking like / (forward slash) from profile, It is actually a slice of a 3d object, cut with a rotated plane.

I want to calculate the area of 3d points and its centre. For 2d case, i use the following

http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/[^]

but, how can i extend the 2d case to 3d for area and its centre?

Thanks in advance.

Bekir.

Re: calculate polygon area and its centre in 3d

Alan Balkany1-Apr-09 3:46

Re: calculate polygon area and its centre in 3d

1-Apr-09 3:46

If you could rotate the points so they all have the same Z coordinate, you could then ignore the Z coordinate and apply the 2D formulas for the area and centroid.

Rotation will not change the area. Apply the reverse rotation to the calculated centroid to get the centroid of the original 3D points.

beko1-Apr-09 19:26

beko

1-Apr-09 19:26

Thank you,

i will try that and i think it will solve the problem but it will create a bit of overhead.

Bekir.

Re: calculate polygon area and its centre in 3d

cp98761-Apr-09 20:10

cp9876

1-Apr-09 20:10

What you want is a 2D coordinate system in the plane of intersection, then you can use your equation for area.

Assume that your original points are represented as vectors {Vk} from some origin O (this is your original 3D coordinate system).

As you have the equation of the plane, choose one point on it as the new origin Op, and choose two orthogonal unit vectors (U1, U2) that lie in the plane as the new axes. (i.e. choose two orthogonal vectors orthogonal to the normal of the plane)

Then in your new coordinate system, the 2D coordinates of the point Vk are:
( (Vk-Op).U1, (Vk-Op).U2 )

i.e. you simply project the 3D vector from your new origin onto your new axes.

Note - this includes Alan's solution, the vectors U1 and U2 would be rows of his rotation matrix. It's just a different way of looking at things.

Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."

Stable Quicksort algorithm

Member 419459331-Mar-09 6:04

Member 4194593

31-Mar-09 6:04

Does anyone have a stable Quicksort? I have looked at many, and they all seem to have a problem in that they swap elements that are not equal to the pivot element before knowing whether the swapped elements match any other element. see the following example:

014447222563 where '3' is the pivot

You will swap the '4's and '2's leaving:

012227444563

and the final swap:

012223444567

however, the swaps of the '2's and '4's (done one at a time from the outside) put them out of order before you even get to see that they are duplicates.

The only way I know of is to supply an additional key element in the record (sorted along with the key) which contains the input record number of the key. This is time expensive, rebuilding the records just to sort them, only to unbuild them when the sort completes. It is easily done, however, with indirect sorting, where the indirect array is an array of structures containing both the pointer to the actual record and also the input record number. Swapping the indirect pointers as records keeps the original record number with its record definition where it can be checked when an equal comparison is encountered. Of course, indirect sorting is inefficient when huge arrays (> 2GB)are involved because the underlying data remains scattered in memory, and paging in huge blocks of memory to compare a small record is a terrible waste.

Dave Augustine

Lutosław31-Mar-09 12:39

Lutosław

31-Mar-09 12:39

If you are sorting numbers then consider using a bucket sort which is stable. It's also faster than QuickSort in some circumstances.

Greetings - Gajatko

Portable.NET is part of DotGNU, a project to build a complete Free Software replacement for .NET - a system that truly belongs to the developers.

Member 419459331-Mar-09 16:06

Member 4194593

31-Mar-09 16:06

gajatko,

Thank you for the reply, but I was specifically interested in a Stable Quicksort.

Off topic, I see that you answered this over 3 hours ago. I checked the forums no more than 5 minutes ago and this message was not there, I got your reply on my Email and answered it from there. Guess I'll have to tell Chris.

Dave.

Stephen Hewitt31-Mar-09 17:11

Stephen Hewitt

31-Mar-09 17:11

Have a look at STL's stable_sort[^]. Perhaps this is what you're after.

Steve

Member 41945931-Apr-09 17:16

Member 4194593

1-Apr-09 17:16

Steve,

Thank you for the reference. Turns out that StableSort is a merge sort. Of course it is stable. You are always comparing elements before you select one or the other to output. My contention, having read many of the Articles on quicksort and seen their algorithms, is that they attempt to be stable once the pivot and an element is compared, but totally ignore whatever has not been seen (between i and j) when swapping i and j elements to satisfy the sort conditions i < pivot, j >= pivot. Note that you have only compared i and pivot and j and pivot, (by the algorithm, i < j), but you know nothing about what lies between i and j. Swapping these two elements may cause an unstable sort as I demonstrated in my initial post.

My attempt is to build a stable quicksort which should be faster, and not require the additional mergesort memory (see The Knuth reference, last paragraph on page 161 (Volume 3, copyright 1973). I would quote it, but cannot due to copyright restriction.

Dave.