446,302 Members | 1,453 Online Need help? Post your question and get tips & solutions from a community of 446,302 IT Pros & Developers. It's quick & easy.

# help with sorting d-dimensional points

 P: 3 Hi, I would like some help as how to approach the following problem: I have a set of d-dimensional points (e.g (3,5,8,9,5) is a 5-dimensional point), and I need to sort the points on each of the coordinates. The algorithm that I am trying to implement says that the resulting data structure is a multi-pointer list ((d-1)tuply threaded list), each node of which is threaded in each of the single pointer lists corresponding to the chosen coordinates. This is a preprocessing stage of my implementation. I need this sorting of the points so that I could use it in a recursive divide and conquer approach to find the maximal elements among the points. what i am looking for, is a list where the points are sorted by coordinate 1, then another list with points sorted by coordinate 2, and so on. But somehow all the lists should be connected, so that when I delete an element from a certain list (e.g. one sorted by coord 1), it would also be deleted from all the other lists. I suppose that's why they call it threaded, in the algorithm. Is there anything around that can do that? I want to use the STL to solve the problem. Any ideas as how this preprocessing structure might look like? and sort the points in each coordinate using maybe quicksort? AJ. Jun 25 '06 #1
3 Replies

 Expert Mod 5K+ P: 8,916 I am not sure that it is possible to use the STL to solve this problem unless you actually have n separate lists. However you are asked to produce an n threaded list. I would interpret this as a single list with several different lists of sorting. For a list of 5 dimensional coordinates you would need a structure similar to Expand|Select|Wrap|Line Numbers struct coordinates {     int Coord;  // Orordinate     struct coordinates *next;   // Next pointers in 5 dimensions };   static struct coordinates *pListStart;   Since you are talking about using STL I assume you are using C++, you need an N dimensional solution, so we can build our N dimensional solution using a template. Something like Expand|Select|Wrap|Line Numbers template  struct coordinates {     int Coord[N];  // N dimensional Corordinate     struct coordinates *next[N];   // Next pointers in N dimensions       static struct coordinates *start[N]; // Start pointers in N dimensions, this                                           // assumes only having 1 instance of                                           // a given dimension };   You will need to add some methods to that structure to add and remove members from the list, if you like make it a class instead of a structure but there are few differences between the 2 (only 1 really). Jun 27 '06 #2

 100+ P: 293 How about using redirection arrays/vectors? I prefer vectors because it has all the memory management worked out. Suppose you have input: (3, 6, 0) (2, 3, 5) (1, 8, 9) then have one vector for each coordinate, so after sorting, vector sortCoord1 = (0,1,2) // 3 > 2 > 1 vector sortCoord2 = (2,0,1) // 8 > 6 > 3 vector sortCoord3 = (2,1,0) // 9 > 5 > 0 then if you needed to remove (2,3,5), you could just delete 1 from each vector and the result would be (0,1) (1,0) (1,0) assuming the others get shifted down. Jun 27 '06 #3

 Expert Mod 5K+ P: 8,916 Hi D_C, you ar trying to get the vector to do something it was not designed to do as well as introducing lots ofoverhead by having instances of multiple classes to do the job. When you remove an entry you have to iterate through all the entries in your vectors to modify all the indexes so that they remain correct. Using a single dedicated class, properly written to handle it's own memory correctly will result in clearer, faster and more maintainable code. That is of course just my opinion :D Cheers Ben Jun 27 '06 #4 