By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,016 Members | 2,262 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,016 IT Pros & Developers. It's quick & easy.

Efficient way to sort array of points

P: n/a
Let's say I have Point[] and I want to sort it circle way (e.g.
2;2.4;1,8;2,8,5;4;8,2;7,1;4
The algo for this is:
if ((p[i].X<p[i+1].X & p[i].Y<Avg(p).Y & p[i+1].Y<Avg(p).Y) |
(p[i].X>p[i+1].X & p[i].Y>Avg(p).Y & p[i+1].Y>Avg(p).Y) )
Swap(p[i],p[i+1]);
where Avg(p).Y is the middle (average) of all Y values.
Other words:
First of all all point with Y above the Middle of Ys acsending and then
all point with Y under the Middle of Ys descending

Is there more effecient way to do this except buble sort for 2 axes?

TNX

--
Tamir Khason
You want dot.NET? Just ask:
"Please, www.dotnet.us "

Nov 16 '05 #1
Share this Question
Share on Google+
6 Replies


P: n/a
Use System.Array.Sort(p, new Class1()) where class1 implements IComparer and place your code in the compare routine.

--
Michael Culley
"Tamir Khason" <ta**********@tcon-NOSPAM.co.il> wrote in message news:u1**************@TK2MSFTNGP12.phx.gbl...
Let's say I have Point[] and I want to sort it circle way (e.g.
2;2.4;1,8;2,8,5;4;8,2;7,1;4
The algo for this is:
if ((p[i].X<p[i+1].X & p[i].Y<Avg(p).Y & p[i+1].Y<Avg(p).Y) |
(p[i].X>p[i+1].X & p[i].Y>Avg(p).Y & p[i+1].Y>Avg(p).Y) )
Swap(p[i],p[i+1]);
where Avg(p).Y is the middle (average) of all Y values.
Other words:
First of all all point with Y above the Middle of Ys acsending and then
all point with Y under the Middle of Ys descending

Is there more effecient way to do this except buble sort for 2 axes?

TNX

--
Tamir Khason
You want dot.NET? Just ask:
"Please, www.dotnet.us "

Nov 16 '05 #2

P: n/a
TNX for response.
Did it at first try, but it works even slower then straight forward
algorithms. Maybe did something wrong?, but prety sure that did not
As far as I nuderstand IComparer did the same old Buble sort, so why it
slower?...

--
Tamir Khason
You want dot.NET? Just ask:
"Please, www.dotnet.us "
"Michael Culley" <mc*****@NOSPAMoptushome.com.au> wrote in message
news:u5*************@TK2MSFTNGP12.phx.gbl...
Use System.Array.Sort(p, new Class1()) where class1 implements IComparer and place your code in the compare routine.
--
Michael Culley
"Tamir Khason" <ta**********@tcon-NOSPAM.co.il> wrote in message

news:u1**************@TK2MSFTNGP12.phx.gbl...
Let's say I have Point[] and I want to sort it circle way (e.g.
2;2.4;1,8;2,8,5;4;8,2;7,1;4
The algo for this is:
if ((p[i].X<p[i+1].X & p[i].Y<Avg(p).Y & p[i+1].Y<Avg(p).Y) |
(p[i].X>p[i+1].X & p[i].Y>Avg(p).Y & p[i+1].Y>Avg(p).Y) )
Swap(p[i],p[i+1]);
where Avg(p).Y is the middle (average) of all Y values.
Other words:
First of all all point with Y above the Middle of Ys acsending and then
all point with Y under the Middle of Ys descending

Is there more effecient way to do this except buble sort for 2 axes?

TNX

--
Tamir Khason
You want dot.NET? Just ask:
"Please, www.dotnet.us "


Nov 16 '05 #3

P: n/a
"Tamir Khason" <ta**********@tcon-NOSPAM.co.il> wrote in message news:uf*************@TK2MSFTNGP12.phx.gbl...
TNX for response.
Did it at first try, but it works even slower then straight forward
algorithms. Maybe did something wrong?, but prety sure that did not
Try converting this vb6 code to C#. It should be very quick.

http://www.mikesdriveway.com/misc/sort.zip
As far as I understand IComparer did the same old Buble sort, so why it
slower?...


I would have thought it would have a better algorithm than bubble. How many times does it call the Compare routine compared to your
bubble sort?

--
Michael Culley
Nov 16 '05 #4

P: n/a
Works your algorithmus?
If I had an array of points to be sorted by distance of origin [0;0], I
would calculate the sum of the square of x and y and sort by this number

Point[] points=....;
System.Collection.SortedList sortedList=new
System.Collection.SortedList(points.Length);
for(int i=0;i<points.Length;i++)
sortedList.Add(points[i].X*points[i].X+points[i].Y*points[i].Y,points[i]);
"Tamir Khason" <ta**********@tcon-NOSPAM.co.il> schrieb im Newsbeitrag
news:u1**************@TK2MSFTNGP12.phx.gbl...
Let's say I have Point[] and I want to sort it circle way (e.g.
2;2.4;1,8;2,8,5;4;8,2;7,1;4
The algo for this is:
if ((p[i].X<p[i+1].X & p[i].Y<Avg(p).Y & p[i+1].Y<Avg(p).Y) |
(p[i].X>p[i+1].X & p[i].Y>Avg(p).Y & p[i+1].Y>Avg(p).Y) )
Swap(p[i],p[i+1]);
where Avg(p).Y is the middle (average) of all Y values.
Other words:
First of all all point with Y above the Middle of Ys acsending and then
all point with Y under the Middle of Ys descending

Is there more effecient way to do this except buble sort for 2 axes?

TNX

--
Tamir Khason
You want dot.NET? Just ask:
"Please, www.dotnet.us "

Nov 16 '05 #5

P: n/a
Dan
The documentation says that Array.Sort(myArray, IComparerObject) uses a
quicksort:

"This method uses the QuickSort algorithm. This is an O(n ^2) operation,
where n is the number of elements to sort, with an average of ?(n log n)."
"Michael Culley" <mc*****@NOSPAMoptushome.com.au> wrote in message
news:eZ****************@TK2MSFTNGP10.phx.gbl...
"Tamir Khason" <ta**********@tcon-NOSPAM.co.il> wrote in message news:uf*************@TK2MSFTNGP12.phx.gbl...
TNX for response.
Did it at first try, but it works even slower then straight forward
algorithms. Maybe did something wrong?, but prety sure that did not


Try converting this vb6 code to C#. It should be very quick.

http://www.mikesdriveway.com/misc/sort.zip
As far as I understand IComparer did the same old Buble sort, so why it
slower?...


I would have thought it would have a better algorithm than bubble. How

many times does it call the Compare routine compared to your bubble sort?

--
Michael Culley

Nov 16 '05 #6

P: n/a
"Dan" <da*@dontspamme.com> wrote in message news:eE**************@tk2msftngp13.phx.gbl...
The documentation says that Array.Sort(myArray, IComparerObject) uses a
quicksort:

"This method uses the QuickSort algorithm. This is an O(n ^2) operation,
where n is the number of elements to sort, with an average of ?(n log n)."


I tested the ArrayList sort and compared it to my* sort. I thought mine was fast but the arraylist sort was significantly faster
(3.6 times faster). The bubble sort took huge amounts of time, I stopped it before it finished. If the op is getting poor results it
must be because their algorithm is slow. It could also be slow because of incorrect data being returned , eg if you tell it A > B
and B > A it is bound to get confused.

Results for sort of 100,000 items (Time (ms), Comparison Count):
My Sort 2895, 4,066,741
Arraylist sort 771, 2,223,288
Bubble Sort 2,500,000, 5,000,000,000
The time for the bubble sort was estimated cause I got sick of waiting :-)

*It's not really my sort, I pinched it from a website somewhere, all I did was package it into a reusable class. :-)

--
Michael Culley
Nov 16 '05 #7

This discussion thread is closed

Replies have been disabled for this discussion.