Numeric Sort on QuickSort

Hi,

I’m trying to sort a list of records with “numeric sort” for a field in this case age.
I would like that QuiskSort return me result as in the sample below. Any idea?

Ame

set ml to {{age:“20”, fullname:“John”}, {age:“8”, fullname:“Peter”}, {age:“1”, fullname:“Olaf”}, {age:“2”, fullname:“Ruby”}, {age:“10”, fullname:“Paul”}}

quickSortL(ml, 1, 3)

– return {{age:“1”, fullname:“Olaf”}, {age:“20”, fullname:“John”}, {age:“8”, fullname:“Peter”}, {age:“2”, fullname:“Ruby”}, {age:“10”, fullname:“Paul”}}

– should return {{age:“1”, fullname:“Olaf”}, {age:“2”, fullname:“Ruby”}, {age:“8”, fullname:“Peter”}, {age:“10”, fullname:“Paul”}, {age:“20”, fullname:“John”}}

on quickSortL(theList, theLeft, theRight)
set i to theLeft
set j to theRight
set v to age of item ((theLeft + theRight) div 2) of theList
repeat while (j > i)
repeat while (age of item i of theList < v)
set i to i + 1
end repeat
repeat while (age of item j of theList > v)
set j to j - 1
end repeat
if (not i > j) then
tell theList to set {item i, item j} to {item j, item i}
set i to i + 1
set j to j - 1
end if
end repeat
if (theLeft < j) then quickSortL(theList, theLeft, j)
if (theRight > i) then quickSortL(theList, i, theRight)
end quickSortL

Here you go: (You should use tags.)

set ml to {{age:"20", fullname:"John"}, {age:"8", fullname:"Peter"}, {age:"1", fullname:"Olaf"}, {age:"2", fullname:"Ruby"}, {age:"10", fullname:"Paul"}}

set m to quickSortByAge(ml, 1, (count ml))
-- http://macscripter.net/viewtopic.php?id=38978
on quickSortByAge(theList, theLeft, theRight)
	set i to theLeft
	set j to theRight
	set v to age of item ((theLeft + theRight) div 2) of theList as integer -- pivot
	repeat while (j > i)
		repeat while (age of item i of theList as integer < v)
			set i to i + 1
		end repeat
		repeat while (age of item j of theList as integer > v)
			set j to j - 1
		end repeat
		if (not i > j) then
			tell theList to set {item i, item j} to {item j, item i} -- swap
			set i to i + 1
			set j to j - 1
		end if
	end repeat
	if (theLeft < j) then quickSortByAge(theList, theLeft, j)
	if (theRight > i) then quickSortByAge(theList, i, theRight)
end quickSortByAge

Hi McUsrII,

What you mean with “You should use tags?”

PS: you forget to return theList at the end of quickSort :wink:

Many thanks

Ame

Hello.

No need for returning anything, as the list is sorted intrinsically that is. I could have written

quickSort(ml,1,(count ml))

.

By tags I meant that you could have put your code in between the BBCode tags you get when you press the “Applescript” button above the message box, which you use when you enter a post. :wink:

Hi.

A more versatile approach would be to use a customisable Quicksort which subcontracts comparisons to an external handler referenced through a script object. So instead of writing a different Quicksort handler for every contigency, you use the same handler every time and just write different comparison plug-ins.

For ame’s query, the comparison handler has to return whether the text value of the ‘age’ property of one record greater than the text value of the ‘age’ property of another record when the two are compared numerically:

script byAge
	on isGreater(a, b)
		considering numeric strings
			return (a's age > b's age)
		end considering
	end isGreater
end script

The sort then passes pairs of records to the plug-in’s ‘isGreater’ handler instead of doing the comparisons itself.

set ml to {{age:"20", fullname:"John"}, {age:"8", fullname:"Peter"}, {age:"1", fullname:"Olaf"}, {age:"2", fullname:"Ruby"}, {age:"10", fullname:"Paul"}}

script byAge
	on isGreater(a, b)
		considering numeric strings
			return (a's age > b's age)
		end considering
	end isGreater
end script

CustomQuickSort(ml, 1, (count ml), byAge)

return ml

on CustomQuickSort(theList, theLeft, theRight, comparer)
	set i to theLeft
	set j to theRight
	set v to item ((theLeft + theRight) div 2) of theList
	repeat while (j > i)
		repeat while (comparer's isGreater(v, item i of theList))
			set i to i + 1
		end repeat
		repeat while (comparer's isGreater(item j of theList, v))
			set j to j - 1
		end repeat
		if (not i > j) then
			tell theList to set {item i, item j} to {item j, item i}
			set i to i + 1
			set j to j - 1
		end if
	end repeat
	if (theLeft < j) then CustomQuickSort(theList, theLeft, j, comparer)
	if (theRight > i) then CustomQuickSort(theList, i, theRight, comparer)
end CustomQuickSort

To sort again by ‘fullname’ instead of ‘age’, you just use a different comparison plug-in:

-- Everything as above except for:

script byFullname
	on isGreater(a, b)
		return (a's fullname > b's fullname)
	end isGreater
end script

CustomQuickSort(ml, 1, (count ml), byFullname)