From robert135@yahoo.com Mon Jan 2 06:12:59 2006 Date: Mon, 2 Jan 2006 05:13:28 -0800 (PST) From: Robert P To: Lawrence L Larmore Subject: Re: Question about sorting... [ The following text is in the "iso-8859-1" character set. ] [ Your display is set for the "US-ASCII" character set. ] [ Some characters may be displayed incorrectly. ] Sorry was busy the last few days. I am thinking of the general database style setup... max 100 columns, but hundreds of thousands if not more rows. I am just curious how to do it effectively so when you have a problem that needs this approach I don't have to revert to using a database just to solve it quickly. Lawrence L Larmore wrote: I now (think I) understand the problem. You want to sort the ROWS of a matrix, where order is determined lexically, where you specify the importance of the columns. Example: all officers in the US military are ordered by seniority, based on rank. If ranks are equal, by date of comission. If those are both equal, by age. If those are both equal ... etc. I've actually been faced with this problem. I have a simple solution, which takes O(n*m*log n) time, where n = number of rows and m = number of columns. This is reasonably efficient if n is much, much, bigger than m, which was true in my applications. I think that the choice of algorithm will depend on the application. What kind of values do you have for n and m in your application? ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ! Lawrence L. Larmore, Professor Office: TBE B378B ! ! Department of Computer Science email: larmore@cs.unlv.edu ! ! University of Nevada at Las Vegas Phone: (702) 895-1096 ! ! P.O. Box 454019 Dept: (702) 895-3681 ! ! Las Vegas, NV 89154-4019 FAX: (702) 895-2639 ! ! Home Page http://www.cs.unlv.edu/~larmore ! ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ On Fri, 23 Dec 2005, Robert P wrote: > Date: Fri, 23 Dec 2005 19:44:53 -0800 (PST) > From: Robert P > To: Lawrence L Larmore > Subject: Re: Question about sorting... > > OK here we go. Another way to say it might be sub sorting of data, sort of like the "order by" functionality in an SQL database.. so you can say "order by col1, col2, col3", and it will order primarily by column 1, then column 2, then column 3. > > Here is an example table where I will do only a col 1, col 2 sort (by sequence of declaration, it tells you the precedence of the sorts..) > > A B C D > 200 10 a 14 > 100 12 c 25 > 100 10 d 13 > 200 09 b 11 > > Sorted by column A alone, the results might be > A B C D > 100 12 c 25 > 100 10 d 13 > 200 10 a 14 > 200 09 b 11 > > but sorted by column primary A and secondary B you would get > A B C D > 100 10 d 13 > 100 12 c 25 > 200 09 b 11 > 200 10 a 14 > > Results would vary depending on which primary column, secondary, tertiary etc. you choose... but as a general solution, I would like to be able to specify any number or order of columns, and where as the above example, it would be 1,2 for the primart sort and sub sort.. I could go 4,3,2,1 or 4,2,3 or what ever... > > An example using MS Excel would be their sort function, where you input your data, and then generally just select what ever column you choose as the primary sort, then what ever column as the 2ndary sub sort, and another column for the 3rd sub sort, each sort having a level of precedence ... etc... > > The only way I have found to do it is very kludgy.. you sort the data first by the primary column, then must subdivide the dataset by the values that are alike into a new array, which then is sorted alone by the 2nd selected column, then again by a third ... etc.. finally to reconstruct the entire dataset. > > Ex from above on a 1,2 sort.. > After sorting by the first column... > Break up the dataset by values that are alike... > in this case, 100, and 200 > > 100 12 c 25 > 100 10 d 13 > > 200 10 a 14 > 200 09 b 11 > > then sort each of these by the 2nd column > 100 10 d 13 > 100 12 c 25 > > 200 09 b 11 > 200 10 a 14 > > then concatenating them back together as your result set... > 100 10 d 13 > 100 12 c 25 > 200 09 b 11 > 200 10 a 14 > > This seems kludgy, and I have no idea how to do it generally where I could select any column in the first place... when I started to code a solution, I started doing cases, and sub cases, and realized that it was not an elegant solution right there and figured there should be a recursive solution somewhere here ... So hence the question to you. > > > Lawrence L Larmore wrote: Hi! > > Great to hear from you. Merry Christmas to you, too! > > I do not understand the question. What do you mean by > "sort by columns?" An example might help. > > > > > > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > ! Lawrence L. Larmore, Professor Office: TBE B378B ! > ! Department of Computer Science email: larmore@cs.unlv.edu ! > ! University of Nevada at Las Vegas Phone: (702) 895-1096 ! > ! P.O. Box 454019 Dept: (702) 895-3681 ! > ! Las Vegas, NV 89154-4019 FAX: (702) 895-2639 ! > ! Home Page http://www.cs.unlv.edu/~larmore ! > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > > On Fri, 23 Dec 2005, Robert P wrote: > > > Date: Fri, 23 Dec 2005 03:05:48 -0800 (PST) > > From: Robert P > > To: larmore@cs.unlv.edu > > Subject: Question about sorting... > > > > Well here is a problem that I have not found an elegant solution to yet... > > > > You have a multidimensional array, perhaps 2 dimensions for ease of use. > > > > Now you want to sort this 2 dimensional array in multiple columns, perhaps if it has columns A,B,C,D,E you want to sort the array by columns B and C, C being after B, The sorting function doesn't matter, bubble sort would be fine for show. But in this case the answer must be general, in the case that you pass to a general sorting function the names or indexes of the arbitrarily many columns to sort in specific order... > > > > IE. > > > > Sort(myArray, 2,3); // would sort by the 2nd and 3rd columns, in that order of precedence.. > > > > or Sort(myArray, 4, 1, 3); // etc > > > > Any ideas on good ways to do this? It seems like a pretty common problem, but the solution so far is a little tricky. Thanks. > > > > Merry Christmas, > > > > Robert Powell > > > > > > > > > > --------------------------------- > > Yahoo! Shopping > > Find Great Deals on Holiday Gifts at Yahoo! Shopping > > > > > > --------------------------------- > Yahoo! Shopping > Find Great Deals on Holiday Gifts at Yahoo! Shopping ________________________________________________________________________________ Yahoo! DSL Something to write home about. Just $16.99/mo. or less