|
Sorting Algorithm required!
Hi Dave Thanks for your response! Greatly appreciated! I am still trying to understand the code - it is definitely more than mouthful for me. I am also downloading some documents from the internet on radix sort a suggested by you. Although, my superficial intent is to be able to use it but I woul rather understand, then write and then use it (hopefully, I wil eventually succeed!!!). Dave, if I do get stuck, is it possible and OK by you for me to contac you by email outside of the forum? Best regards Deepa -- agarwaldv ----------------------------------------------------------------------- agarwaldvk's Profile: http://www.excelforum.com/member.php...fo&userid=1134 View this thread: http://www.excelforum.com/showthread.php?threadid=27231 |
Sorting Algorithm required!
Dave I now recall where I got to know of you! Here it was! I have now been able to implement your MSD Radix sort to suit my requirement. It works OK for a one dimensional array of strings - no problems. However, how can I get it going where I have a 2 dimensional array of strings ('n' rows and 'm' columns) and I need to sort the same by more than one column. I have tried 2 ways of doing it (in both cases by repeatedly Radix sorting the array from the least significant column to the most significant column) - both go through their entire cycles but neither give the correct output. One of the ways that I have gone is to split the original array in to 2 arrays :- One containing only data from the column that the array is to be sorted by and The other containing the data from all the other columns in the array There was no problem working with the data from the array that the column is to be sorted by. But, even after all this much of effort I still have got no idea how to determine and associate the position of the corresponding strings from the other columns (these are in the second array) belonging to the same row - to ensure that all the data along a single row from all the columns stay together - with the data from the column that the array is being sorted by. If it might help I can send my version of your modified code to you. Or you might even give me just a guidance as how to get around the above problem. Any suggestions please! Best regards Deepak Agarwal -- agarwaldvk ------------------------------------------------------------------------ agarwaldvk's Profile: http://www.excelforum.com/member.php...o&userid=11345 View this thread: http://www.excelforum.com/showthread...hreadid=272317 |
Sorting Algorithm required!
Not entirely sure what the thread history is here, but in the general case I
would create a common key that combines each column required in the sort module into a single value then sort on that. Specifically add a new column value that combines the string values for each array column 1st level on the left, 2nd next etc., if you have numeric data left pad the data with leading zeroes to give correct sequence then sort you array on this new common key. -- Cheers Nigel "agarwaldvk" wrote in message ... Dave I now recall where I got to know of you! Here it was! I have now been able to implement your MSD Radix sort to suit my requirement. It works OK for a one dimensional array of strings - no problems. However, how can I get it going where I have a 2 dimensional array of strings ('n' rows and 'm' columns) and I need to sort the same by more than one column. I have tried 2 ways of doing it (in both cases by repeatedly Radix sorting the array from the least significant column to the most significant column) - both go through their entire cycles but neither give the correct output. One of the ways that I have gone is to split the original array in to 2 arrays :- One containing only data from the column that the array is to be sorted by and The other containing the data from all the other columns in the array There was no problem working with the data from the array that the column is to be sorted by. But, even after all this much of effort I still have got no idea how to determine and associate the position of the corresponding strings from the other columns (these are in the second array) belonging to the same row - to ensure that all the data along a single row from all the columns stay together - with the data from the column that the array is being sorted by. If it might help I can send my version of your modified code to you. Or you might even give me just a guidance as how to get around the above problem. Any suggestions please! Best regards Deepak Agarwal -- agarwaldvk ------------------------------------------------------------------------ agarwaldvk's Profile: http://www.excelforum.com/member.php...o&userid=11345 View this thread: http://www.excelforum.com/showthread...hreadid=272317 |
Sorting Algorithm required!
Nigel I am not sure if I understand you. This is in the context of MSD Radix Sort. Tell me if I understand you correctly. Say if I have a 50000 row x 4column array and I want to sort this array first by column2 in the descending order and then within column2 by column3 in the ascending order. Since MSD Radix Sort is a stable, my idea was to repeatedly call MSD Radix Sort and sort the array from the least significant to the most significant sort column, and the end of it all get the sorted array as the desired output. If I understand you correctly, then, in the first pass, I have to concatenate the strings from all the 4 columns beginnng with the string from column3 and then from the other columns, then create a new array and populate it with this combined string and sort this array using the principles of MSD Radix Sort. Following this, in the second pass, I have to concatenate the strings from all the 4 columns beginnng with the string from column2 and then from the other columns, then create a new array and populate it with this combined string and sort this array using the principles of MSD Radix Sort. If this is what you meant, that is exactly what I tried but by doing that what happens is that the array gets sorted on the entire string which is the concatenation of the strings from all the four columns and sorted to the order of the column being currently sorted overwriting the previous sorted output. Hence, I am not getting the array sorted by each of the sortby columns to the desired sort order. I hope I have clarified the problem. If not please feel free to ask for further clarifications. Any further suggestions?????????? Best regards Deepak Agarwal -- agarwaldvk ------------------------------------------------------------------------ agarwaldvk's Profile: http://www.excelforum.com/member.php...o&userid=11345 View this thread: http://www.excelforum.com/showthread...hreadid=272317 |
Sorting Algorithm required!
Why not read the original post by David Ring. He explains exactly how to do
it using array A1 and Array A2. Assume you scenario of sorting on column2 and then column3. You would have the original array, you would copy column2 values to A1, then copy column3 values to A2. You would sort on A2, then sort on A2. The result would be the final sort order in the P array. Sub Main() Dim A1() As String, A2() As String Dim P() As Long, Q() As Long Dim MyArray() As String Dim MyArray1() As String Dim dum() As String, i As Long, j As Long Dim lMax As Long lMax = 100 ReDim dum(1 To 62) Dim k As Long For i = 0 To 10 dum(i + 1) = i Next k = 65 For i = 11 To 11 + 25 dum(i) = Chr(k) k = k + 1 Next k = 97 For i = 37 To 37 + 25 dum(i) = Chr(k) k = k + 1 Next Range("A1:A62") = Application.Transpose(dum) ReDim MyArray(0 To lMax, 0 To 3) ReDim MyArray1(0 To lMax, 0 To 3) ReDim A1(0 To lMax): ReDim A2(0 To lMax) ReDim P(0 To lMax): ReDim Q(0 To lMax) For i = 0 To lMax For j = 0 To 3 For k = 1 To 1 ' < = set your string length if you wish MyArray(i, j) = MyArray(i, j) & dum(Int(Rnd() * 62 + 1)) Next Next Next Range("C1:C" & lMax + 1).Resize(, 4) = MyArray For i = LBound(MyArray, 1) To UBound(MyArray, 1) A1(i) = MyArray(i, 2) A2(i) = MyArray(i, 3) P(i) = i Next i pRadixS A1, P, Q, LBound(A1, 1), UBound(A1, 1) pRadixS A2, P, Q, LBound(A2, 1), UBound(A2, 1) For i = 0 To lMax For j = 0 To 3 MyArray1(i, j) = MyArray(P(i), j) Next Next Range("H1:H" & lMax + 1).Resize(, 4) = MyArray1 End Sub I found that if the arrays fed to the routine were not zero based, the sort routine crashed. Some other observations: There is no option for ascending There sort is Ascii (Z comes before a) -- Regards, Tom Ogilvy "agarwaldvk" wrote in message ... Nigel I am not sure if I understand you. This is in the context of MSD Radix Sort. Tell me if I understand you correctly. Say if I have a 50000 row x 4column array and I want to sort this array first by column2 in the descending order and then within column2 by column3 in the ascending order. Since MSD Radix Sort is a stable, my idea was to repeatedly call MSD Radix Sort and sort the array from the least significant to the most significant sort column, and the end of it all get the sorted array as the desired output. If I understand you correctly, then, in the first pass, I have to concatenate the strings from all the 4 columns beginnng with the string from column3 and then from the other columns, then create a new array and populate it with this combined string and sort this array using the principles of MSD Radix Sort. Following this, in the second pass, I have to concatenate the strings from all the 4 columns beginnng with the string from column2 and then from the other columns, then create a new array and populate it with this combined string and sort this array using the principles of MSD Radix Sort. If this is what you meant, that is exactly what I tried but by doing that what happens is that the array gets sorted on the entire string which is the concatenation of the strings from all the four columns and sorted to the order of the column being currently sorted overwriting the previous sorted output. Hence, I am not getting the array sorted by each of the sortby columns to the desired sort order. I hope I have clarified the problem. If not please feel free to ask for further clarifications. Any further suggestions?????????? Best regards Deepak Agarwal -- agarwaldvk ------------------------------------------------------------------------ agarwaldvk's Profile: http://www.excelforum.com/member.php...o&userid=11345 View this thread: http://www.excelforum.com/showthread...hreadid=272317 |
Sorting Algorithm required!
Hi Tom I will have a look at your suggestions but just out of interest where are his original postings. The site where I got was the "devx" website but I didn't find related link to sort 2 dimensional arrays. Can you please give me url where I can get to see his original solution to this scenario. Best regards Deepak Agarwal -- agarwaldvk ------------------------------------------------------------------------ agarwaldvk's Profile: http://www.excelforum.com/member.php...o&userid=11345 View this thread: http://www.excelforum.com/showthread...hreadid=272317 |
Sorting Algorithm required!
Hi Tom I did have a look at your solution and I am still a bit lost. Can you help me a bit further? Two things :- I do not know how this Radix Sort implementation pRadixS A1, P, Q, LBound(A1, 1), UBound(A1, 1) works. In the one that I have seen from Dave Ring, the equivalent array in his implementation of your array P() contains the byte location of the first character of the ith string. If your array P() also contains the same information, then how would I be able to decipher the string position of the strings in the columns other than the column being sorted from the contents of your array P(). Secondly, if I am trying to sort the array first by column2 and then within column2 by column3, I am still not able to understand how array P() guarantees the correct location of the strings both in column3 and column2 - column3 is supposed to be sorted within column2. Whilst I am at it, please advise me of the the URL where I can find the original post by David Ring. Best regards Deepak Agarwal -- agarwaldvk ------------------------------------------------------------------------ agarwaldvk's Profile: http://www.excelforum.com/member.php...o&userid=11345 View this thread: http://www.excelforum.com/showthread...hreadid=272317 |
| All times are GMT +1. The time now is 01:32 PM. |
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
ExcelBanter.com