Efficient way to sort array of points

[Tamir Khason]

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 "

[Michael Culley]

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 "

[Tamir Khason]

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 "

[Michael Culley]

"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

[Zürcher See]

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 "

[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

[Michael Culley]

"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