Re: Sort Multidimensional Array by Column 5
Re: Sort Multidimensional Array by Column 5
- Subject: Re: Sort Multidimensional Array by Column 5
- From: Jon Pugh <email@hidden>
- Date: Tue, 5 Oct 2010 21:10:13 -0700
At 4:29 PM +0100 10/5/10, Richard Lake wrote:
>If anyone can offer a working solution I'd like to hear it.
Pulled out of my archive, this is an AppleMod from long ago.
I did not write this, but I did test that it worked for your given data set.
Jon
-- mark ADL BLOCK<B
(*::dotd ADL 1.0 -- experimental comment block
::-================================
::name quickSort
::auth Serge Belleudy-d'Espinose
::mail email@hidden
::vers 3.0
::date 2002/02/25
::---------------------------------
::desc
quickSort is a highly efficient quick sort mod. It is able to sort a list of single items, lists, or records, with optional weights.
::inet <http://hissa.nist.gov/dads/>
Dictionary of Algorithms, Data Structures, and Problems
where it all began
::note
Also includes flatSort, a quick sort variant that uses less recursion to avoid stack overflow errors on fairly large lists, and is also far slower!
See quickSort for flatSort syntax.
Note for previous users: the name of qSort has been changed to quickSort, however calls with the old names will be redirected.
::ackn
My deepest thanks to the following for their improvements: Has, Francois Delyon, and to Greg Strange for the whole AppleMods thing.
::hist
2002
02/25 3.0 -- now sorts records
totally rewritten from scratch with a more efficient and flexible design
now sorts records
up to 30% faster on sorting lists
includes flatSort
bug fixes in initial coercions
2001
11/20 2.0b -- same code
rewritten to unify the handlers into a single object; no other visible change
11/08 2.0 -- multi-column version
now sorts multi-column lists with optional weights (slower); still as fast on single-columns lists
11/07 1.2 -- 'dutch flag' variation
slightly faster due to some rewrite (FD)
will be much faster on small ranges, where the previous one would collapse
::-================================
:qs:synt
quickSort([values])
[values] list -- list of single items to sort
Result: list -- list of sorted items
quickSort({Values:[values], Weights:[weights]})
[values] list; mandatory -- list of sub-lists to sort
[weights] list; optional -- position numbers of the sub-list items in sorting order
Result: list -- list of sorted sub-lists
quickSort({Values:[values], Weights:[weights]})
[values] list; mandatory -- list of sub-records
[weights] list; mandatory -- names of the sub-record properties in sorting order
Result: list -- list of sorted subb-records
:qs:desc
quickSort will sort a list of single items ie integers, strings or dates, a list of lists, or a list of records. When sorting lists or records, quickSort will allow the user to specify weights for the sub-items. See the examples and notes for details.
:qs:xmpl
quickSort({3, 2, 1}) -- (1)
Result: {1, 2, 3}
quickSort({"three", "two", "one"})
Result: {"one", "two", "three"}
quickSort({{2, 1}, {1, 1}, {1, 4}, {1, 3}, {1, 2}}) -- (2a) (2b)
Result: {{1, 1}, {1, 4}, {1, 3}, {1, 2}, {2, 1}}
quickSort({Values:{{2, 1}, {1, 1}, {1, 4}, {1, 3}, {1, 2}}, Weights:{1, 2}}) -- (3a) (3b)
Result: {{1, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 1}}
quickSort({Values:{{2, 1}, {1, 1}, {1, 4}, {1, 3}, {1, 2}}, Weights:{2, 1}})
Result: {{1, 1}, {2, 1}, {1, 2}, {1, 3}, {1, 4}}
quickSort({Values:{{Primo:1, Secundo:2}, {Secundo:1, Primo:2}}, Weights:{"primo"}}) -- (4a) (4b)
Result: {{Primo:1, Secundo:2}, {Secundo:1, Primo:2}}
quickSort({Values:{{Primo:1, Secundo:2}, {Secundo:1, Primo:2}}, Weights:{"secundo", "primo"}}) (5)
Result: {{Secundo:1, Primo:2}, {Primo:1, Secundo:2}}
:qs:note
(1) all values must match: integers with integers, strings with strings; sub-lists and sub-records can contain different kinds of sub-items as long as they also match
(2a) when sorting lists while using the simple syntax, quickSort will only check the first item of each sub-list
(2b) empty sub-lists will break quickSort
(3a) when using the complex syntax, the Weights parameter allows the user to specify a list of sub-list item indexes in sorting order. For example, Weights: {3, 4} means third sub-list item first, fourth sub-list item second- and not weight of 3 for the first sub-list item and weight of 4 for the second sub-list item
(3b) the Weights parameter will be checked against the first sub-list; hence all subsequent sub-lists must be as long or longer
(4a) when sorting records, it is mandatory to use thecomplex syntax and the Weights parameters and specify at least one property name; failing to do so, quickSort will be unable to sort the records- it will display a warning message but it won't break
(4b) label names must match those in the sub-records; hence, all records must share the same labels- extra labels won't be used
(5) it's important to understand that sorting records requires coercing them to lists first; however since record properties are unordered by essence, the coercion use by quickSort is based on the label names so the sorting is correct whatever the differences of orders between records
Dedicated to A. on a day to remember
::-================================
*)
property kErrMess : "quickSort> "
-- mark SORT OBJECTS<B
script sortObjects
-- mark OBJECTS
to getRecord()
end getRecord
--
to swapSingle(swapIndex)
set {xItem, yItem} to {item (item 1 of swapIndex), item (item 2 of swapIndex)} of its lMain
if xItem > yItem then return {yItem, xItem}
{xItem, yItem}
end swapSingle
--
to swapList(swapIndex)
set {xItem, yItem} to {item (item 1 of swapIndex), item (item 2 of swapIndex)} of its lMain
repeat with iWeight in its lWeights
set xValue to item iWeight in xItem
set yValue to item iWeight in yItem
if xValue > yValue then return {yItem, xItem}
if xValue < yValue then return {xItem, yItem}
end repeat
{xItem, yItem}
end swapList
--
to swapRecord(swapIndex)
set {xItem, yItem} to {item (item 1 of swapIndex), item (item 2 of swapIndex)} of its lMain
set xRecord to getRecord(xItem)
set yRecord to getRecord(yItem)
set vWidth to length of its lWeights
repeat with i from 1 to vWidth
set xValue to item i in xRecord
set yValue to item i in yRecord
if xValue > yValue then return {yItem, xItem}
if xValue < yValue then return {xItem, yItem}
end repeat
{xItem, yItem}
end swapRecord
--
to splitSingle()
set mItem to middle item of its lMain
repeat with vItem in its lMain
set vItem to contents of vItem
if vItem < mItem then
set end of its lLow to vItem
else if vItem = mItem then
set end of its lMiddle to vItem
else
set end of its lHigh to vItem
end if
end repeat
end splitSingle
--
to splitList()
set mItem to middle item of its lMain
set iWeight to item 1 of its lWeights
set mValue to item iWeight in mItem
repeat with vItem in its lMain
set vItem to contents of vItem
set vValue to item iWeight in vItem
if vValue < mValue then
set end of its lLow to vItem
else if vValue > mValue then
set end of its lHigh to vItem
else
set end of its lMiddle to vItem
end if
end repeat
if ((length of its lMiddle) > 1) and ((length of its lWeights) > 1) then
set {oldWeights, its lWeights} to {its lWeights, rest of its lWeights}
set its lMiddle to sortPoly(its lMiddle)
set its lWeights to oldWeights
end if
end splitList
--
to splitRecord()
set mItem to middle item of its lMain
set mValue to item 1 of getRecord(mItem)
repeat with vItem in its lMain
set vItem to contents of vItem
set vValue to item 1 of getRecord(vItem)
if vValue < mValue then
set end of its lLow to vItem
else if vValue > mValue then
set end of its lHigh to vItem
else
set end of its lMiddle to vItem
end if
end repeat
if ((length of its lMiddle) > 1) and ((length of its lWeights) > 1) then
set {oldWeights, its lWeights} to {its lWeights, rest of its lWeights}
set its lMiddle to sortPoly(its lMiddle)
set its lWeights to oldWeights
end if
end splitRecord
-- mark SORT METHODS
to quickSortPoly(vList)
script listObject
property lMain : vList
property lLow : {}
property lMiddle : {}
property lHigh : {}
end script
tell listObject
set vLength to (length of its lMain)
if vLength < 2 then return its lMain
if vLength = 2 then return swapPoly({1, 2})
splitPoly()
if (length of its lLow) > 1 then set its lLow to sortPoly(its lLow)
if (length of its lHigh) > 1 then set its lHigh to sortPoly(its lHigh)
its lLow & its lMiddle & its lHigh
end tell
end quickSortPoly
--
to flatSortPoly(vList)
script listObject
property lMain : vList
property lLow : {}
property lMiddle : {}
property lHigh : {}
property lStack : {}
property lResult : {}
end script
tell listObject
repeat
set lLength to (length of its lMain)
if lLength < 3 then -- pile down
if lLength = 2 then
set its lResult to (its lResult & swapPoly({1, 2}))
else
set its lResult to (its lResult & its lMain)
end if
if its lStack = {} then exit repeat
set {leftItem, rightItem} to (item -1 of its lStack)
set its lResult to (its lResult & leftItem)
set its lMain to rightItem
set its lStack to (reverse of rest of reverse of its lStack)
else -- pile up
set {its lLow, its lMiddle, its lHigh} to {{}, {}, {}}
splitPoly()
set {its lMain, (end of its lStack)} to {its lLow, {its lMiddle, its lHigh}}
end if
end repeat
its lResult
end tell
end flatSortPoly
end script
-- mark -
-- mark SORT OBJECT<B
script sortObject
property lValues : missing value
property lWeights : missing value
-- placeholders for handlers
property swapPoly : missing value
property splitPoly : missing value
property sortPoly : missing value
property getRecord : missing value
-- mark CHECKS
to checkParam()
if (class of its lValues) = record then checkRecord() -- record parameter
if (class of its lValues) = list then -- list parameter
checkList()
else -- other parameter
set its lValues to {its lValues}
end if -- record/list/other parameter
end checkParam
--
to checkRecord()
set its lValues to its lValues & {Values:missing value, Weights:missing value}
if (Values of its lValues = missing value) then error kErrMess & "missing Values property, see doc for syntax"
set {its lValues, its lWeights} to {Values, Weights} of its lValues
end checkRecord
--
to checkList()
try
set vFirstClass to class of (item 1 of its lValues)
on error
error kErrMess & "empty list"
end try
if (vFirstClass = record) then -- records list
checkListRecords()
else if (vFirstClass = list) then -- lists list
checkListLists()
else -- other items list
tell sortObject
set its swapPoly to swapSingle of sortObjects
set its splitPoly to splitSingle of sortObjects
end tell
end if -- records/lists/other items list
end checkList
--
to checkListRecords()
set vWeights to its lWeights
if (vWeights = missing value) then error kErrMess & "missing Weights property, see doc for syntax" -- no initial Weights parameter
try
set vWeights to strings of vWeights
if (length of vWeights = 0) then error
on error
error kErrMess & "incorrect Weights property, see doc for syntax"
end try
-- construct handler
set {oldTIDs, AppleScript's text item delimiters} to {AppleScript's text item delimiters, ", "}
set sLabels to vWeights as string
set AppleScript's text item delimiters to oldTIDs
set vScript to run script "
script
to getRecord(vParam)
return {" & sLabels & "} of vParam
end getRecord
end script"
try
tell vScript to getRecord(item 1 of lValues)
on error errMess number errNum
error kErrMess & "values and Weights don't match, see doc for syntax"
end try
tell sortObject
set its lWeights to vWeights
set its getRecord to getRecord of vScript
set its swapPoly to swapRecord of sortObjects
set its splitPoly to splitRecord of sortObjects
end tell
end checkListRecords
--
to checkListLists()
set vWidth to length of (item 1 of its lValues)
if (vWidth < 1) then error kErrMess & "empty list"
if (vWidth = 1) then -- single-item sub-list
tell sortObject
set its swapPoly to swapSingle of sortObjects
set its splitPoly to splitSingle of sortObjects
end tell
else if (vWidth > 1) then -- multiple item sub-list
try
set vWeights to (integers of its lWeights)
on error
set vWeights to {}
end try
if (length of vWeights) > 0 then -- non-empty Weights list
repeat with i from 1 to length of vWeights
if ((item i of vWeights) > vWidth) then set (item i of vWeights) to vWidth
end repeat
else -- empty Weights list
set vWeights to {1}
end if -- non-empty/empty Weights list
tell sortObject
set its lWeights to vWeights
set its swapPoly to swapList of sortObjects
set its splitPoly to splitList of sortObjects
end tell
end if -- empty/single-item/multiple item sub-list
end checkListLists
end script
-- mark -
-- mark MAIN CALLS<B
to quickSort(vParam)
tell sortObject
set its sortPoly to quickSortPoly of sortObjects
set its lValues to vParam
checkParam()
sortPoly(its lValues)
end tell
end quickSort
--
to flatSort(vParam)
tell sortObject
set its sortPoly to flatSortPoly of sortObjects
set its lValues to vParam
checkParam()
sortPoly(its lValues)
end tell
end flatSort
property qSort : its quickSort -- legacy code fix
-- your example
set formData to {{"7C925871-2545-458E-9E1A-F3362F5010BE", "CFB29657-ABBA-4AAC-83CF-F436D1AFE3BE", "2ADC20E6-6AB3-4FD9-B137-BAD34D1B580D", "QT", "2942", "C0067C", "Conocophillips", "A Name", "An Address[]2nd Line[]3rd Line[]Etc[]", "email@address", "No", "1", "No", ""}, {"7C925871-2545-458E-9E1A-F3362F5010BE", "97A6977D-B0F4-480B-ACA5-9977E7307996", "2CAC23D0-AEF7-4194-AD1C-201B053298A0", "SO", "3111", "C0067C", "Conocophillips", "A Name", "An Address[]2nd Line[]3rd Line[]Etc[]", "aemail@address", "No", "1", "No", ""}, {"059B2178-D55B-4542-A794-0B4079F6B007", "C6484FD1-989C-4DA5-8AF8-161769BB1146", "5734F334-2851-496A-82D0-B6A7658ACA53", "SO", "3112", "B0063C", "Exova", "A Name", "An Address[]2nd Line[]3rd Line[]Etc[]", "email@address", "Yes", "1", "Yes", ""}}
reverse of quickSort({Values:formData, Weights:{5}})
_______________________________________________
Do not post admin requests to the list. They will be ignored.
AppleScript-Users mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
Archives: http://lists.apple.com/archives/applescript-users
This email sent to email@hidden