skipbo
asked on
Sorting a 2 dimension array??
Hello everyone,
Is there a way to sort a 2 dimension array other then hard coding? I've tried with ArraySort, but it doesn't work with complex variable. So basically, is there a way around this or will I have to code it? I only want to sort on the first dimension of the array.
Any idea how to code this if I have to?? I guess a quicksort would do the trick, is there more efficient sorting algos?? (those arrays tends to get huge)
Thanks
skip
Is there a way to sort a 2 dimension array other then hard coding? I've tried with ArraySort, but it doesn't work with complex variable. So basically, is there a way around this or will I have to code it? I only want to sort on the first dimension of the array.
Any idea how to code this if I have to?? I guess a quicksort would do the trick, is there more efficient sorting algos?? (those arrays tends to get huge)
Thanks
skip
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Hi,
SBennett, I tried your solution, it works really well with small arrays, but when things get bigger, it's really taxing on the server resources.
I'll check if I could mix in cheekycj idea and see what happens.
I wonder if the quicksort can be implemented in cold fusion. It use some recursion, but what do you guys think??
Thanks a lot guys. I'll let you know what happens...
skip
SBennett, I tried your solution, it works really well with small arrays, but when things get bigger, it's really taxing on the server resources.
I'll check if I could mix in cheekycj idea and see what happens.
I wonder if the quicksort can be implemented in cold fusion. It use some recursion, but what do you guys think??
Thanks a lot guys. I'll let you know what happens...
skip
Yes, I can see how my suggestion would take a lot of proccessing time if the array is extremely large.
I've never really done that before so that was the first solution I thought of. If you come up with a faster solution pleas post it so I can refer to it later.
-scott
I've never really done that before so that was the first solution I thought of. If you come up with a faster solution pleas post it so I can refer to it later.
-scott
ASKER
Hello guys,
I spent some time looking around and found this answer from CF_SPIKE. It implements the quick sort algo. So thanks to him and here it is:
-------------------------- ---------- ---------- --------
Answer provided by : CF_SPIKE
-------------------------- ---------- ---------- --------
Calling Page:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<title>Quick Sort</title>
</head>
<body>
<!--- 2 Dimensional array sorting. Second Array dimension represents:
1 - Employee No
2 - Name
3 - Age
4 - Sex
5 - Date of Birth
6 - Department --->
<CFSCRIPT>
myArray = ArrayNew(2);
myArray[1][1] = '1';
myArray[1][2] = 'Spike';
myArray[1][3] = '28';
myArray[1][4] = 'Male';
myArray[1][5] = 'CreateDate(1972,08,10)';
myArray[1][6] = 'Training';
myArray[2][1] = '2';
myArray[2][2] = 'Jon';
myArray[2][3] = '26';
myArray[2][4] = 'Male';
myArray[2][5] = 'CreateDate(1974,10,23)';
myArray[2][6] = 'Consulting';
myArray[3][1] = '2';
myArray[3][2] = 'Bob';
myArray[3][3] = '22';
myArray[3][4] = 'Male';
myArray[3][5] = 'CreateDate(1979,03,23)';
myArray[3][6] = 'Sales';
myArray[4][1] = '2';
myArray[4][2] = 'Jane';
myArray[4][3] = '20';
myArray[4][4] = 'Female';
myArray[4][5] = 'CreateDate(1980,11,29)';
myArray[4][6] = 'Sales';
</CFSCRIPT>
<CF_QuickSort
Array="#MyArray#"
r_Array="SortedArray"
SortType="Numeric"
SortItem="1">
</body>
</html>
custom Tag:
<CFPARAM NAME="Attributes.Array">
<CFPARAM NAME="Attributes.r_Array">
<!--- SortItem is the index in the second dimension
of the array which we want to sort by --->
<CFPARAM NAME="Attributes.SortItem" >
<!--- SortType can be Numeric, Text, TextNoCase --->
<CFPARAM NAME="Attributes.SortType" >
<!--- SortOrder can be Desc, Asc --->
<CFPARAM NAME="Attributes.SortOrder " DEFAULT="Asc">
<!--- Initialize a list to hold the array elements --->
<CFSET NameList = "">
<!--- Loop over the Array creating a list of the
elements by which we want to sort --->
<CFLOOP From="1" To="#ArrayLen(Attributes.A rray)#" index="i">
<CFSET NameList = ListAppend(NameList,Attrib utes.Array [i][Attrib utes.SortI tem])>
</CFLOOP>
<!--- Create a new sorted list. Sorting by the
parameters delcared above --->
<CFSET NewList = ListSort(NameList,Attribut es.SortTyp e,Attribut es.SortOrd er)>
<!--- Create a New array sorted according to our requirements --->
<CFSET NewArray = ArrayNew(2)>
<CFSET Counter = 1>
<CFLOOP LIST="#newList#" INDEX="i">
<CFSET NewArray[counter] = Attributes.Array[ListFind( NameList,i )]>
<CFSET Counter = Counter + 1>
</CFLOOP>
<CFSET "Caller.#Attributes.r_Arra y#" = NewArray>
I spent some time looking around and found this answer from CF_SPIKE. It implements the quick sort algo. So thanks to him and here it is:
--------------------------
Answer provided by : CF_SPIKE
--------------------------
Calling Page:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<title>Quick Sort</title>
</head>
<body>
<!--- 2 Dimensional array sorting. Second Array dimension represents:
1 - Employee No
2 - Name
3 - Age
4 - Sex
5 - Date of Birth
6 - Department --->
<CFSCRIPT>
myArray = ArrayNew(2);
myArray[1][1] = '1';
myArray[1][2] = 'Spike';
myArray[1][3] = '28';
myArray[1][4] = 'Male';
myArray[1][5] = 'CreateDate(1972,08,10)';
myArray[1][6] = 'Training';
myArray[2][1] = '2';
myArray[2][2] = 'Jon';
myArray[2][3] = '26';
myArray[2][4] = 'Male';
myArray[2][5] = 'CreateDate(1974,10,23)';
myArray[2][6] = 'Consulting';
myArray[3][1] = '2';
myArray[3][2] = 'Bob';
myArray[3][3] = '22';
myArray[3][4] = 'Male';
myArray[3][5] = 'CreateDate(1979,03,23)';
myArray[3][6] = 'Sales';
myArray[4][1] = '2';
myArray[4][2] = 'Jane';
myArray[4][3] = '20';
myArray[4][4] = 'Female';
myArray[4][5] = 'CreateDate(1980,11,29)';
myArray[4][6] = 'Sales';
</CFSCRIPT>
<CF_QuickSort
Array="#MyArray#"
r_Array="SortedArray"
SortType="Numeric"
SortItem="1">
</body>
</html>
custom Tag:
<CFPARAM NAME="Attributes.Array">
<CFPARAM NAME="Attributes.r_Array">
<!--- SortItem is the index in the second dimension
of the array which we want to sort by --->
<CFPARAM NAME="Attributes.SortItem"
<!--- SortType can be Numeric, Text, TextNoCase --->
<CFPARAM NAME="Attributes.SortType"
<!--- SortOrder can be Desc, Asc --->
<CFPARAM NAME="Attributes.SortOrder
<!--- Initialize a list to hold the array elements --->
<CFSET NameList = "">
<!--- Loop over the Array creating a list of the
elements by which we want to sort --->
<CFLOOP From="1" To="#ArrayLen(Attributes.A
<CFSET NameList = ListAppend(NameList,Attrib
</CFLOOP>
<!--- Create a new sorted list. Sorting by the
parameters delcared above --->
<CFSET NewList = ListSort(NameList,Attribut
<!--- Create a New array sorted according to our requirements --->
<CFSET NewArray = ArrayNew(2)>
<CFSET Counter = 1>
<CFLOOP LIST="#newList#" INDEX="i">
<CFSET NewArray[counter] = Attributes.Array[ListFind(
<CFSET Counter = Counter + 1>
</CFLOOP>
<CFSET "Caller.#Attributes.r_Arra
The CF_SPIKE solution and its variants won't work properly if the data in the array contains duplicate values in the sorted column. I came to this site looking for an answer to the original question in this thread, and tried this solution. But I couldn't use it because I do have duplicate values.
I came up with two different ways of doing this, both of which work no matter what the values are. The first is to loop through the array, combine the rows using a separator - I used CHR(30) - into a single dimension array, sort it using arraysort(), and then set up a new array and loop through your sorted array, populating the new array by pulling each element apart again using GetToken().
However, I still had a little problem to overcome. The column which I want to sort contains numeric (integer) values. But now with the combined data, a numeric sort fails because the data is no longer a number, and a text sort returns incorrect order (1,10,2, etc.). The solution: use the NumberFormat operator to pad zeros in front of the number, do a text sort, and then use NumberFormat again to drop the zeros in the final array.
Sample code, for a 2D array with 3 columns:
<CFSET MyDelim = Chr(30)>
<CFSET My1DArray = ArrayNew(1)>
<CFLOOP INDEX="LoopCount" FROM = "1" TO = "#ArrayLen(MyOld2DArray)#" >
<CFSET My1DArray[LoopCount]= "#NumberFormat(MyOld2DArra y[LoopCoun t][1],0000 000.)##MyD elim##MyOl d2DArray[L oopCount][ 2]##MyDeli m##MyOld2D Array[Loop Count][3]# ">
</CFLOOP>
<CFSET temp = ArraySort(My1DArray, "TextNoCase", "Desc")>
<CFSET My2DArray = ArrayNew(2)>
<CFLOOP INDEX="LoopCount" FROM = "1" TO = "#ArrayLen(My1DArray)#">
<CFSET My2DArray[LoopCount][1] = NumberFormat(GetToken(My1D Array[Loop Count],"1" , "#MyDelim#"))>
<CFSET My2DArray[LoopCount][2] = GetToken(My1DArray[LoopCou nt],"2", "#MyDelim#")>
<CFSET My2DArray[LoopCount][3] = GetToken(My1DArray[LoopCou nt],"3", "#MyDelim#")>
</CFLOOP>
But this is pretty clunky. The more elegant solution, if you have access to a SQL database, is to create a dedicated table to do the sorting. Delete all rows in the table, insert your array, then query the table using "ORDER BY" and then empty the table again when you are done.
I came up with two different ways of doing this, both of which work no matter what the values are. The first is to loop through the array, combine the rows using a separator - I used CHR(30) - into a single dimension array, sort it using arraysort(), and then set up a new array and loop through your sorted array, populating the new array by pulling each element apart again using GetToken().
However, I still had a little problem to overcome. The column which I want to sort contains numeric (integer) values. But now with the combined data, a numeric sort fails because the data is no longer a number, and a text sort returns incorrect order (1,10,2, etc.). The solution: use the NumberFormat operator to pad zeros in front of the number, do a text sort, and then use NumberFormat again to drop the zeros in the final array.
Sample code, for a 2D array with 3 columns:
<CFSET MyDelim = Chr(30)>
<CFSET My1DArray = ArrayNew(1)>
<CFLOOP INDEX="LoopCount" FROM = "1" TO = "#ArrayLen(MyOld2DArray)#"
<CFSET My1DArray[LoopCount]= "#NumberFormat(MyOld2DArra
</CFLOOP>
<CFSET temp = ArraySort(My1DArray, "TextNoCase", "Desc")>
<CFSET My2DArray = ArrayNew(2)>
<CFLOOP INDEX="LoopCount" FROM = "1" TO = "#ArrayLen(My1DArray)#">
<CFSET My2DArray[LoopCount][1] = NumberFormat(GetToken(My1D
<CFSET My2DArray[LoopCount][2] = GetToken(My1DArray[LoopCou
<CFSET My2DArray[LoopCount][3] = GetToken(My1DArray[LoopCou
</CFLOOP>
But this is pretty clunky. The more elegant solution, if you have access to a SQL database, is to create a dedicated table to do the sorting. Delete all rows in the table, insert your array, then query the table using "ORDER BY" and then empty the table again when you are done.
well, it wasnt trivial, but here is the bubble sort for CF. phew. please post any improvements.
<cfset tmparr = ArrayNew(2)>
<cfset tmparr[1][1] = 1>
<cfset tmparr[1][2] = "reca">
<cfset tmparr[2][1] = 4>
<cfset tmparr[2][2] = "recb">
<cfset tmparr[3][1] = 2>
<cfset tmparr[3][2] = "recc">
<cfset tmparr[4][1] = 5>
<cfset tmparr[4][2] = "recd">
<cfscript>
Function DualSorter(arrArray, DimensionToSort)
{
var row = 0;
var j = 0;
var StartingKeyValue = "";
var StartingOtherValue = "";
var NewStartingKey = "";
var NewStartingOther = "";
var swap_pos = "";
var OtherDimension = "";
var column = 1;
// Ensure that the user has picked a valid DimensionToSort
If (DimensionToSort eq 1){
OtherDimension = 0;}
If (DimensionToSort eq 0){
OtherDimension = 1;}
If (Otherdimension eq "") {
//Shoot, invalid value of DimensionToSort
Writeoutput("Invalid dimension for DimensionToSort: must be value of 1 or 0.");
break;
}
dimensiontosort = incrementvalue(dimensionto sort);
otherdimension = incrementvalue(otherdimens ion);
For (row = 1; row lte arraylen(arrarray);row=row +1){
//Start outer loop.
//Take a snapshot of the first element
//in the array because if there is a
//smaller value elsewhere in the array
//we'll need to do a swap.
StartingKeyValue = arrArray[row][DimensionToS ort];
StartingOtherValue = arrArray[row][OtherDimensi on];
// Default the Starting values to the First Record
NewStartingKey = arrArray[row][DimensionToS ort];
NewStartingOther = arrArray[row][OtherDimensi on];
swap_pos = row;
For (j = row + 1; j lte arraylen(arrarray);j=j+1){
//Start inner loop.
If (arrArray[j][DimensionToSo rt] gt NewStartingKey)
{
//This is now the lowest number -
//remember it's position.
swap_pos = j;
NewStartingKey = arrArray[j][DimensionToSor t];
NewStartingOther = arrArray[j][OtherDimension ];
}
}
If (swap_pos neq row) {
//If we get here then we are about to do a swap
//within the array.
arrArray [swap_pos][DimensionToSort ] = StartingKeyValue;
arrArray [swap_pos][OtherDimension] = StartingOtherValue;
arrArray [row][DimensionToSort] = NewStartingKey;
arrArray [row][OtherDimension] = NewStartingOther;
}
}
return arrarray;
}
writeoutput(arraylen(tmpar r)&"<br>") ;
tmparr = dualsorter(tmparr, 0);
for (n = 1; n lte arraylen(tmparr);n=n+1)
{
writeoutput(#tmparr[n][1]# &","&#tmpa rr[n][2]#& "<br>");
}
</cfscript>
<cfset tmparr = ArrayNew(2)>
<cfset tmparr[1][1] = 1>
<cfset tmparr[1][2] = "reca">
<cfset tmparr[2][1] = 4>
<cfset tmparr[2][2] = "recb">
<cfset tmparr[3][1] = 2>
<cfset tmparr[3][2] = "recc">
<cfset tmparr[4][1] = 5>
<cfset tmparr[4][2] = "recd">
<cfscript>
Function DualSorter(arrArray, DimensionToSort)
{
var row = 0;
var j = 0;
var StartingKeyValue = "";
var StartingOtherValue = "";
var NewStartingKey = "";
var NewStartingOther = "";
var swap_pos = "";
var OtherDimension = "";
var column = 1;
// Ensure that the user has picked a valid DimensionToSort
If (DimensionToSort eq 1){
OtherDimension = 0;}
If (DimensionToSort eq 0){
OtherDimension = 1;}
If (Otherdimension eq "") {
//Shoot, invalid value of DimensionToSort
Writeoutput("Invalid dimension for DimensionToSort: must be value of 1 or 0.");
break;
}
dimensiontosort = incrementvalue(dimensionto
otherdimension = incrementvalue(otherdimens
For (row = 1; row lte arraylen(arrarray);row=row
//Start outer loop.
//Take a snapshot of the first element
//in the array because if there is a
//smaller value elsewhere in the array
//we'll need to do a swap.
StartingKeyValue = arrArray[row][DimensionToS
StartingOtherValue = arrArray[row][OtherDimensi
// Default the Starting values to the First Record
NewStartingKey = arrArray[row][DimensionToS
NewStartingOther = arrArray[row][OtherDimensi
swap_pos = row;
For (j = row + 1; j lte arraylen(arrarray);j=j+1){
//Start inner loop.
If (arrArray[j][DimensionToSo
{
//This is now the lowest number -
//remember it's position.
swap_pos = j;
NewStartingKey = arrArray[j][DimensionToSor
NewStartingOther = arrArray[j][OtherDimension
}
}
If (swap_pos neq row) {
//If we get here then we are about to do a swap
//within the array.
arrArray [swap_pos][DimensionToSort
arrArray [swap_pos][OtherDimension]
arrArray [row][DimensionToSort] = NewStartingKey;
arrArray [row][OtherDimension] = NewStartingOther;
}
}
return arrarray;
}
writeoutput(arraylen(tmpar
tmparr = dualsorter(tmparr, 0);
for (n = 1; n lte arraylen(tmparr);n=n+1)
{
writeoutput(#tmparr[n][1]#
}
</cfscript>
Sub DualSorter( byRef arrArray, DimensionToSort )
Dim row, j, StartingKeyValue, StartingOtherValue, _
NewStartingKey, NewStartingOther, _
swap_pos, OtherDimension
Const column = 1
' Ensure that the user has picked a valid DimensionToSort
If DimensionToSort = 1 then
OtherDimension = 0
ElseIf DimensionToSort = 0 then
OtherDimension = 1
Else
'Shoot, invalid value of DimensionToSort
Response.Write "Invalid dimension for DimensionToSort: " & _
"must be value of 1 or 0."
Response.End
End If
For row = 0 To UBound( arrArray, column ) - 1
'Start outer loop.
'Take a snapshot of the first element
'in the array because if there is a
'smaller value elsewhere in the array
'we'll need to do a swap.
StartingKeyValue = arrArray ( row, DimensionToSort )
StartingOtherValue = arrArray ( row, OtherDimension )
' Default the Starting values to the First Record
NewStartingKey = arrArray ( row, DimensionToSort )
NewStartingOther = arrArray ( row, OtherDimension )
swap_pos = row
For j = row + 1 to UBound( arrArray, column )
'Start inner loop.
If arrArray ( j, DimensionToSort ) < NewStartingKey Then
'This is now the lowest number -
'remember it's position.
swap_pos = j
NewStartingKey = arrArray ( j, DimensionToSort )
NewStartingOther = arrArray ( j, OtherDimension )
End If
Next
If swap_pos <> row Then
'If we get here then we are about to do a swap
'within the array.
arrArray ( swap_pos, DimensionToSort ) = StartingKeyValue
arrArray ( swap_pos, OtherDimension ) = StartingOtherValue
arrArray ( row, DimensionToSort ) = NewStartingKey
arrArray ( row, OtherDimension ) = NewStartingOther
End If
Next
End Sub
if you need help converting it let me know.
CJ