440,016 Members | 2,262 Online
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].Xp[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
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" 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].Xp[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" 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" 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].Xp[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" 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 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].Xp[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 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" wrote in message news:eZ****************@TK2MSFTNGP10.phx.gbl... "Tamir Khason" 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" 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.