Sorting Algorithm required!

[agarwaldvk]

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

 

[Dave Ring]

Sure. You can reach me as dbring on pacbell dot net.

Dave

 

[agarwaldvk]

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

 

[Nigel]

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.

 

[agarwaldvk]

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

 

[Tom Ogilvy]

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)

 

[agarwaldvk]

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]

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

 

[Tom Ogilvy]

I clicked on the thread link at the bottom of your posting and looked at the
while discussion you had with David Ring. I followed his advice and the
Radix sort he posted. As per his post,

"P() is an array of
longs indexing the strings in A(), "

Your posting from the Excel Forum, according to your header information

(e-mail address removed)

If you think that is DevX, or you actually did get your information from
DevX, then I have no knowledge of that.