Efficient way to sort array of points

  • Thread starter Thread starter Tamir Khason
  • Start date Start date
T

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.X<p[i+1].X & p.Y<Avg(p).Y & p[i+1].Y<Avg(p).Y) |
(p.X>p[i+1].X & p.Y>Avg(p).Y & p[i+1].Y>Avg(p).Y) )
Swap(p,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
 
Use System.Array.Sort(p, new Class1()) where class1 implements IComparer and place your code in the compare routine.
 
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 said:
Use System.Array.Sort(p, new Class1()) where class1 implements IComparer
Click to expand...
and place your code in the compare routine.
--
Michael Culley


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.X<p[i+1].X & p.Y<Avg(p).Y & p[i+1].Y<Avg(p).Y) |
(p.X>p[i+1].X & p.Y>Avg(p).Y & p[i+1].Y>Avg(p).Y) )
Swap(p,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
Click to expand...
Click to expand...
 
Tamir Khason said:
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
Click to expand...

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?...
Click to expand...

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?
 
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.X*points.X+points.Y*points.Y,points);
 
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 said:
Try converting this vb6 code to C#. It should be very quick.

http://www.mikesdriveway.com/misc/sort.zip


I would have thought it would have a better algorithm than bubble. How
Click to expand...
many times does it call the Compare routine compared to your
 
Dan said:
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)."
Click to expand...

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. :-)
 
Back
Top