Sunday, January 21, 2018

#1 2006-05-28 12:12:27 pm

Adam Bell
Administrator
From:: Nova Scotia, Canada
Registered: 2005-10-04
Posts: 4660

QuickSort Algorithm

Except for pathological cases, Tony Hoare's QuickSort algorithm is often used for sorting large lists and except for more complex algorithms is certainly among the fastest. Here's an AppleScript version of QuickSort. On my machine (dual-core G5/2.3GHz) it will sort a list of 1686 items (3 concatinated sets of the words of "lorem ipsum") in approximately 4.45 seconds. I'll send my list on request.

To sort an entire list, set leftEnd to 1 and rightEnd to count List. These arguments are required because the alogorithm is recursive - it successively divides and conquers.

Applescript:

Qsort(yourList, 1, count yourList)

The handler:

Applescript:

to Qsort(array, leftEnd, rightEnd) -- Hoare's QuickSort Algorithm
   script A
       property L : array
   end script
   set {i, j} to {leftEnd, rightEnd}
   set v to item ((leftEnd + rightEnd) div 2) of A's L -- pivot in the middle
   repeat while (j > i)
       repeat while (item i of A's L < v)
           set i to i + 1
       end repeat
       repeat while (item j of A's L > v)
           set j to j - 1
       end repeat
       if (not i > j) then
           tell A's L to set {item i, item j} to {item j, item i} -- swap
           set {i, j} to {i + 1, j - 1}
       end if
   end repeat
   if (leftEnd < j) then Qsort(A's L, leftEnd, j)
   if (rightEnd > i) then Qsort(A's L, i, rightEnd)
end Qsort

[EDIT: fixed last two lines, were sort(), now Qsort()]


iMac running OS X 10.13.1

Offline

 

#2 2006-05-28 03:39:12 pm

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 4488

Re: QuickSort Algorithm

Hi, Adam.

That looks very similar to an early version of the qsort that Arthur Knapp and I wrote a couple of years ago. I suppose Arthur got the algorithm from the same source. It sorts the actual list passed to it, rather than leaving it as it is and returning a sorted copy. Some people have said they find this confusing, but we think it's OK as long as potential users are aware of the fact.

We set out to write the fastest vanilla sort we could and included every AppleScript speed trim we could find. Arthur's research also turned up the idea of switching to an insertion sort for the "fine tuning". QuickSort is quite a coarse tool. It's very effective in the early stages of imposing order on chaos, but as the list becomes more nearly sorted, QuickSort still does a lot of recursing and checking even though it has to move fewer and fewer items around in the list. An insertion sort, on the other hand, while less efficient in the early stages of a sort, does a lot less work when less needs to be done. The sort below stops the QuickSort recursions at levels where 10 or less items need to be sorted, and finishes off with an insertion sort of the entire, nearly-sorted list. On my 2.0 GHz, dual-processor G5, your Qsort sorts a list of 4000 random integers with values between 0 and 10,000 in about 23.5-24.5 seconds. This does the same job in about 0.39 to 0.44 seconds:

13th September 2010: I've uploaded a new version of this sort, as part of a collection, to ScriptBuilders.

Applescript:

on qsort(theList, l, r)
script o
property cutoff : 10
property p : theList

on qsrt(l, r)
set i to l
set j to r
set v to my p's item ((l + r) div 2)

repeat while (j > i)
set u to my p's item i
repeat while (u < v)
set i to i + 1
set u to my p's item i
end repeat

set w to my p's item j
repeat while (w > v)
set j to j - 1
set w to my p's item j
end repeat

if (i > j) then
else
set my p's item i to w
set my p's item j to u
set i to i + 1
set j to j - 1
end if
end repeat

if (j - l < cutoff) then
else
qsrt(l, j)
end if

if (r - i < cutoff) then
else
qsrt(i, r)
end if
end qsrt

on isrt(l, r)
set x to l
set z to l + cutoff - 1
if (z > r) then set z to r

set v to my p's item x
repeat with y from (x + 1) to z
if (my p's item y < v) then
set x to y
set v to my p's item y
end if
end repeat

tell my p's item l
set my p's item l to v
set my p's item x to it
end tell

set u to my p's item (l + 1)
repeat with i from (l + 2) to r
set v to my p's item i
if (v < u) then
set my p's item i to u
repeat with j from (i - 2) to l by -1
if (v < my p's item j) then
set my p's item (j + 1) to my p's item j
else
set my p's item (j + 1) to v
exit repeat
end if
end repeat
else
set u to v
end if
end repeat
end isrt
end script

set listLen to (count theList)
if (listLen > 1) then -- otherwise the handler will error
-- Translate negative indices
if (l < 0) then set l to listLen + l + 1
if (r < 0) then set r to listLen + r + 1

if (r = l) then
-- No point in sorting just one item
else
-- Transpose transposed indices
if (l > r) then
set temp to l
set l to r
set r to temp
end if

if (r - l < o's cutoff) then
-- Skip the Quicksort if cutoff or less items
else
o's qsrt(l, r)
end if
o's isrt(l, r)
end if
end if

return -- nothing
end qsort


-- Demo: sort a list of 4000 integers between 0 and 10,000.
set l to {}
repeat with i from 1 to 4000
set end of my l to random number 10000
end repeat
set t to (GetMilliSec)
qsort(l, 1, -1)
((GetMilliSec) - t) / 1000

Note that, having had more time for development, this handler also allows negative indices for the sort range parameters and the left or the right one can be specified first.

There's also a CustomQsort version of this, if you're interested, whose parameters include a script object containing handlers which do the actual comparisons for the sort and return whether one item is "greater" or "less" than the other. This isn't quite as fast as qsort, but it's very powerful. Depending on the handlers passed, CustomQsort can sort a list of lists by particular items in the lists, records by particular properties, etc. It can even do reverse sorts.

Later edit:

The main cause of the speed difference between the two handlers appears to be this line in yours:

[code]tell A's L to set {item i, item j} to {item j, item i} -- swap[/code]
Apart from the "setting by list", which detracts slightly from the speed, the 'tell A's L' tells the result of getting the list to change those items. The list-in-a-script-object speed approach needs the reference to be told:

[code]tell (a reference to A's L) to set {item i, item j} to {item j, item i} -- swap[/code]

Last edited by Nigel Garvey (2010-11-13 08:00:28 am)


NG

Offline

 

#3 2006-05-28 06:37:37 pm

Adam Bell
Administrator
From:: Nova Scotia, Canada
Registered: 2005-10-04
Posts: 4660

Re: QuickSort Algorithm

I really "dug" the -1 argument rather than "count theList". Why don't I think of those things. (It doesn't work on my version because it finds the middle by summing the beginning and end div 2, but that would be easy to fix)

With my test list of text to be ASCII sorted, yours and Arthur's version is 10 times faster - an incredible speedup. With your random number sort which is several times larger than my list, the ratio is even more fantastic: 20 seconds for mine, approximately a third of a second for yours; 60:1. Wow. I think I'll keep the Garvey/Knapp sort in place of mine.

I will say that in reading up on the recursive QuickSort, there were several algorithms like yours that switched to more direct sorting as the sort progressed. I note that you used a cutoff of 10, and others I saw used 8. I also note that you have tucked the entire algorithm inside the script rather than just the properties. I'll play with that on my version just to see the effect.

I'll remember that there is also a CustomQSort handler or if you think it worthwhile, perhaps you'll post it here. In ScriptBuilders, Steve LoBasso has also posted "QuickSort 1.1" which seems to have many degrees of freedom. His is non-recursive to avoid large memory requirements.

Amazed as always, Nigel. It's clear that as a latecomer to the scene (I started AppleScripting in February of last year) I missed all the fun.

Adam


iMac running OS X 10.13.1

Offline

 

#4 2006-05-29 03:27:33 pm

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 4488

Re: QuickSort Algorithm

Adam Bell wrote:

I really "dug" the -1 argument rather than "count theList". Why don't I think of those things. (It doesn't work on my version because it finds the middle by summing the beginning and end div 2, but that would be easy to fix)


Hi, Adam.

Arthur and I thrashed out our version over several weeks of e-mail correspondence. We had plenty of time to come up with niceties like that.  smile

With my test list of text to be ASCII sorted, yours and Arthur's version is 10 times faster - an incredible speedup. With your random number sort which is several times larger than my list, the ratio is even more fantastic: 20 seconds for mine, approximately a third of a second for yours; 60:1. Wow. I think I'll keep the Garvey/Knapp sort in place of mine.


Did you notice the later edit at the end of my post? There's a line in your version that inadvertently bypasses the list-in-a-script-object reference. When that's sorted out, the difference in speed between the two versions is very much less!

I will say that in reading up on the recursive QuickSort, there were several algorithms like yours that switched to more direct sorting as the sort progressed. I note that you used a cutoff of 10, and others I saw used 8.


Arthur's a professional scripter and more versed in the literature than I am. It was his reading that turned up the main algorithms we used. A few empirical tests suggested that 10 was a reasonable cut-off value. I think we decided that the "perfect" value probably depended on the length and original order of the list itself — which of course can't be known in advance.

I also note that you have tucked the entire algorithm inside the script rather than just the properties. I'll play with that on my version just to see the effect.


I don't think it makes any difference to the performance. It's just a convenient way to have all the processes, including a recursive one, inside the same handler. It's an approach that's been criticised by some people, who feel it's better practice to include the main handler in the script object rather than vice versa. I'm not persuaded it's necessarily better, but this the basic shape of what they mean:

Applescript:

script qsort
   property cutoff : 10
   property p : missing value
   
   on qsrt(l, r)
       -- As in my earlier script.
   end qsrt
   
   on isrt(l, r)
       -- As in my earlier script.
   end isrt
   
   on sort(theList, l, r)
       set p to theList
       
       -- Do everything that the qsort() handler does
       -- in the earlier script, but don't mention 'o'!
       if (r - l < cutoff) then
           -- Skip the Quicksort if cutoff or less items
       else
           qsrt(l, r)
       end if
       isrt(l, r)
   end sort
end script

tell qsort to sort(myList, 1, -1)

I'll remember that there is also a CustomQSort handler or if you think it worthwhile, perhaps you'll post it here.


I'll post it later on. I'm having some more thoughts about it that I want to try out first.  smile

Amazed as always, Nigel. It's clear that as a latecomer to the scene (I started AppleScripting in February of last year) I missed all the fun.


I hope it's not all over yet!  yikes


NG

Offline

 

#5 2006-05-30 07:24:40 pm

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 4488

Re: QuickSort Algorithm

Here's the CustomQsort handler I mentioned earlier. Sorts work by comparing items in a list and repositioning them according to their relative values. But comparing items directly isn't always possible or desirable. You might want to sort a list of lists, or of records, or of files, or even of mixed classes. Or the sort order might need to be modified in some way. Each contingency requires a different method for determining which items are "greater" or "less" than others, which means having either several specialised sort handlers or a customisable one such as CustomQsort. CustomQsort does the physical work of moving items around in the list, but the comparisons are done by short handlers in a script object that's passed to CustomQsort as a parameter.

Arthur and I had slightly different preferences for what the script object should contain, so this is just my version:

13th September 2010: I've uploaded a new version of this sort with an improved customisation regime, as part of a collection, to ScriptBuilders. The new version, though, will accept customisation scripts written for the one below, which has been around for quite a while now.

Applescript:

on CustomQsort(theList, l, r, compObj)
   script o
       property cutoff : 10
       property p : theList
       
       on qsrt(l, r)
           set i to l
           set j to r
           set v to my p's item ((l + r) div 2)
           
           repeat while (j > i)
               
               set u to my p's item i
               repeat while (compObj's isLess(u, v))
                   set i to i + 1
                   set u to my p's item i
               end repeat
               
               set w to my p's item j
               repeat while (compObj's isGreater(w, v))
                   set j to j - 1
                   set w to my p's item j
               end repeat
               
               if (i > j) then
               else
                   set my p's item i to w
                   set my p's item j to u
                   
                   -- Inform the script object of this swap.
                   compObj's swap(i, j)
                   
                   set i to i + 1
                   set j to j - 1
               end if
           end repeat
           
           if (j - l < cutoff) then
           else
               qsrt(l, j)
           end if
           if (r - i < cutoff) then
           else
               qsrt(i, r)
           end if
       end qsrt
       
       on isrt(l, r)
           set x to l
           set z to l + cutoff - 1
           if (z > r) then set z to r
           
           set v to my p's item x
           repeat with y from (x + 1) to z
               if (compObj's isLess(my p's item y, v)) then
                   set x to y
                   set v to my p's item y
               end if
           end repeat
           
           tell my p's item l
               set my p's item l to v
               set my p's item x to it
           end tell
           
           -- Inform the script object of this swap.
           compObj's swap(l, x)
           
           set u to my p's item (l + 1)
           repeat with i from (l + 2) to r
               set v to my p's item i
               if (compObj's isLess(v, u)) then
                   set my p's item i to u
                   repeat with j from (i - 2) to l by -1
                       if (compObj's isLess(v, my p's item j)) then
                           set my p's item (j + 1) to my p's item j
                       else
                           set my p's item (j + 1) to v
                           
                           -- Inform the script object of this insertion.
                           compObj's shift(j + 1, i)
                           
                           exit repeat
                       end if
                   end repeat
               else
                   set u to v
               end if
           end repeat
       end isrt
   end script
   
   set listLen to (count theList)
   if (listLen > 1) then -- otherwise the handler will error
       -- Translate negative indices
       if (l < 0) then set l to listLen + l + 1
       if (r < 0) then set r to listLen + r + 1
       
       if (r = l) then
           -- No point in sorting just one item
       else
           -- Transpose transposed indices
           if (l > r) then
               set temp to l
               set l to r
               set r to temp
           end if
           
           if (r - l < o's cutoff) then
               -- Skip the Quicksort if cutoff or less items
           else
               o's qsrt(l, r)
           end if
           o's isrt(l, r)
       end if
   end if
   
   return -- nothing
end CustomQsort

The compObj parameter should be a script object containing these four handlers and anything else that may be required:

isLess(a, b): decides if the value of a is "less" than the value of b or not. (Returns 'true' or 'false'.)
isGreater(a, b): decides if the value of a is "greater" than the value of b, ditto.
swap(a, b): called by CustomQsort after each swap performed in the list being sorted. a and b are the indices of the swapped items. This handler would normally be left empty, but it could be used to do the same swap in another list.
shift(a, b): called by CustomQsort after each "insertion" performed in the list being sorted. The parameters indicate that item b of the list has been moved to position a after items a thru (b - 1) have been shifted uplist. This handler would also normally be left empty, but could be used to echo the moves in another list.

The idea is that you write your own script objects to control how the sort is done. For a straightforward sort similar to qsort's, isLess() and isGreater() would do simple comparisons and swap() and shift() would do nothing:

Applescript:

script standardSort
   on isLess(a, b)
       (a < b)
   end isLess
   
   on isGreater(a, b)
       (a > b)
   end isGreater
   
   on swap(a, b)
   end swap
   
   on shift(a, b)
   end shift
end script

CustomQsort(myList, 1, -1, standardSort)

If you wanted to sort one list and echo the moves in another — say you had a list of files that had to be sorted in parallel with a list of corresponding modification dates — you'd use the swap() and shift() handlers to perform the slave moves in the file list:

Applescript:

script slaveSort
   property slaveList : missing value
   
   on isLess(a, b)
       (a < b)
   end isLess
   
   on isGreater(a, b)
       (a > b)
   end isGreater
   
   -- Do the same swap in slaveList that CustomQsort has just done in the list it's sorting.
   on swap(a, b)
       tell item a of my slaveList
           set item a of my slaveList to item b of my slaveList
           set item b of my slaveList to it
       end tell
   end swap
   
   -- Do the same shift and insertion in slaveList that CustomQsort has just done in the list it's sorting.
   on shift(a, b)
       tell item b of my slaveList
           repeat with i from b - 1 to a by -1
               set item (i + 1) of my slaveList to item i of my slaveList
           end repeat
           set item a of my slaveList to it
       end tell
   end shift
end script

set slaveSort's slaveList to myFileList
CustomQsort(myDateList, 1, -1, slaveSort)
--> myDateList sorted by the dates it contains
--> myFileList sorted so that the files still correspond to the dates

For a spreadsheet-style sort, sorting a list of lists on, say, the third item in each list:

Applescript:

script listSort
   property i : missing value
   
   on isLess(a, b)
       (a's item i < b's item i)
   end isLess
   
   on isGreater(a, b)
       (a's item i > b's item i)
   end isGreater
   
   on swap(a, b)
   end swap
   
   on shift(a, b)
   end shift
end script

set listSort's i to 3
CustomQsort(myListOfLists, 1, -1, listSort)

For a reverse sort, simply lie to CustomQsort by swapping the contents of the isLess() and isGreater() handlers.  smile

Applescript:

script reverseSort
   on isLess(a, b)
       (a > b)
   end isLess
   
   on isGreater(a, b)
       (a < b)
   end isGreater
   
   on swap(a, b)
   end swap
   
   on shift(a, b)
   end shift
end script

CustomQsort(myList, 1, -1, reverseSort)

And so on.

Within the same script, handlers and properties that are common to different script objects can be shared. For example, if there's a standard sort and a reverse sort in the same script, the amount of code in one of the script objects could be reduced by making it a child of the other:

Applescript:

script standardSort
   on isLess(a, b)
       (a < b)
   end isLess
   
   on isGreater(a, b)
       (a > b)
   end isGreater
   
   on swap(a, b)
   end swap
   
   on shift(a, b)
   end shift
end script

script reverseSort
   property parent : standardSort

   on isLess(a, b)
       (a > b)
   end isLess
   
   on isGreater(a, b)
       (a < b)
   end isGreater
end

With standardSort as its 'parent', reverseSort inherits all standardSort's handlers (and would inherit its properties too, if it had any), so there's no need to write out the swap() and shift() handlers in reverseSort itself. The other two handlers, though, have to be different and so are written out, which overrides the inheritance as far as they're concerned. The two script objects thus have their own isLess() and isGreater() handlers, but share standardSort's swap() and shift() handlers.

It's possible to go even further with the above example, as reverseSort's isLess() and isGreater() handlers are the same as standardSort's isGreater() and isLess() handlers. These too can be shared by assigning them to the relevantly named variables in reverseSort. The full specification for the reverseSort script object would then be:

Applescript:

script reverseSort
   property parent : standardSort
   
   property isLess : standardSort's isGreater
   property isGreater : standardSort's isLess
end script

Last edited by Nigel Garvey (2010-11-13 08:09:09 am)


NG

Offline

 

#6 2006-07-29 05:09:15 am

Santa
Member
From:: Land of Oz
Registered: 2006-07-27
Posts: 486

Re: QuickSort Algorithm

G'day

I'm new at scripting, and wanted a fast sort, and found this via Google.

Problem is, I'm having trouble working out how to call the Qsort routine.

I've tried My qsort, tell Qsort, and just Qsort, but nothing calls the routine.

Could someone please help out a newbie.

Thanks, Santa


Just an enthusiastic old fart of an Apple user since the IIe days

Offline

 

#7 2006-07-29 07:11:30 am

Santa
Member
From:: Land of Oz
Registered: 2006-07-27
Posts: 486

Re: QuickSort Algorithm

I've solved it.

Apparently in the transfer of the code something happened to the "Qsort" words.

Once I re-typed in the first & last lines, & renamed the routine, all was well, thanks.

BUT, I've got another problem you guys might be able to help with. I want to sort a list of path names that your routine won't handle.

It's in the form...

set thelist to (selection as list)
(Sort thelist alphabetically)

I can sort the <name> of each item in thelist, but I need to keep the pathnames.

Can anyone help please?

Regards

Santa


Just an enthusiastic old fart of an Apple user since the IIe days

Offline

 

#8 2006-07-29 02:04:31 pm

Adam Bell
Administrator
From:: Nova Scotia, Canada
Registered: 2005-10-04
Posts: 4660

Re: QuickSort Algorithm

Hi Santa;

This is a simple replacement sort, but I wrote it  so I could take three lists of the same length containing related data and sort on one of them while keeping the other two in the same order. (I think the original idea was Kai Edwards'). You can easily modify it for only two lists.

Applescript:

to sort_items(sortList, SecondList, thirdList)
   script L
       property srt : sortList
       property sec : SecondList
       property thd : thirdList
   end script
   tell (count L's srt) to repeat with i from (it - 1) to 1 by -1
       set s to (L's srt)'s item i
       set r to (L's sec)'s item i
       set q to (L's thd)'s item i
       repeat with i from (i + 1) to it
           tell (L's srt)'s item i to if s > it then
               set (L's srt)'s item (i - 1) to it
               set (L's sec)'s item (i - 1) to (L's sec)'s item i
               set (L's thd)'s item (i - 1) to (L's thd)'s item i
           else
               set (L's srt)'s item (i - 1) to s
               set (L's sec)'s item (i - 1) to r
               set (L's thd)'s item (i - 1) to q
               exit repeat
           end if
       end repeat
       if it is i and s > (L's srt)'s end then
           set (L's srt)'s item it to s
           set (L's sec)'s item it to r
           set (L's thd)'s item it to q
       end if
   end repeat
end sort_items

Updated by adding the internal script to speed it up


iMac running OS X 10.13.1

Offline

 

#9 2006-07-29 02:26:10 pm

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 4488

Re: QuickSort Algorithm

I've tagged a reply onto Santa's thread in the OS X forum, pointing out the Finder's sort command, which might be what's needed.


NG

Offline

 

#10 2006-07-29 07:40:40 pm

Santa
Member
From:: Land of Oz
Registered: 2006-07-27
Posts: 486

Re: QuickSort Algorithm

G'day

I think I've found a bug in the Qsort routine.

When I sorted a list of only 149 items, it left the top (last) item unsorted.

It seems to think 89 if after 346 wink

I'm finding the routine very, very useful thanks, but wonder if someone could fix it for me. The coding is way beyound me!

Regards

Santa


Just an enthusiastic old fart of an Apple user since the IIe days

Offline

 

#11 2006-07-30 02:28:48 am

Santa
Member
From:: Land of Oz
Registered: 2006-07-27
Posts: 486

Re: QuickSort Algorithm

G'day again

I think there's also a bug in the Hoare's quicksort routine. I tried using it and it's leaving large numbers stranded somewhere in the middle of the list.

I need a reliable sort that allows me to get the maximum & minimum from both ends, as well as the sorted list, in a single list.

All this just to place icons on the desktop or windows.:P

Thanks Nigel, that sort was what I needed, but I'd rather not restrict my icon sort routine just for 10.4, so I've opted for a slower method, if I can just get a sort that works!

Regards, Santa

Model: G5
AppleScript: 1.10.7
Browser: Safari 419.3
Operating System: Mac OS X (10.4)


Just an enthusiastic old fart of an Apple user since the IIe days

Offline

 

#12 2006-07-30 08:12:19 am

Adam Bell
Administrator
From:: Nova Scotia, Canada
Registered: 2005-10-04
Posts: 4660

Re: QuickSort Algorithm

G'day, Santa;

I don't have a problem with the script in item 2 of this thread whether the sorted items are strings of characters or large numbers. Are you setting l to -1 and r to 1?


iMac running OS X 10.13.1

Offline

 

#13 2006-07-30 02:57:47 pm

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 4488

Re: QuickSort Algorithm

I suspect that Santa's sorting files with names like "89.jpg" and "346.jpg" and wants them sorted numerically rather than lexically.

The handlers above are sensitive to the AppleScript string-handling environment, so in Tiger, you could use the new considering numeric strings attribute:

Applescript:

set myList to {"346.jpg", "4.jpg", "87.jpg"}
considering numeric strings
   qsort(myList, 1, -1)
end considering

myList
--> {"4.jpg", "87.jpg", "346.pg"}

To sort Finder items on systems before Tiger, there's a script of mine in ScriptBuilders called FinderSort(), which imitates how I guessed sort would work in OS X when it was eventually reinstated. This sorts numeric strings numerically, but is a bit awkward to use and only works with collective Finder references, not with the list returned by the Finder's selection. (I guessed wrong there.)

It's possible to reproduce the considering numeric strings effect with systems earlier than Tiger, but it takes a lot more code. However, it's quite fast.

1. Get the names of the files/folders.
2. Pad out any numerics in the names to a fixed width with leading zeros.
3. Use a slave-sort script object with CustomQsort to sort the doctored names lexically, copying the sort moves in the list of files.

Applescript:

on CustomQsort(theList, l, r, compObj)
   script o
       property cutoff : 10
       property p : theList
       
       on qsrt(l, r)
           set i to l
           set j to r
           set v to my p's item ((l + r) div 2)
           
           repeat while (j > i)
               
               set u to my p's item i
               repeat while (compObj's isLess(u, v))
                   set i to i + 1
                   set u to my p's item i
               end repeat
               
               set w to my p's item j
               repeat while (compObj's isGreater(w, v))
                   set j to j - 1
                   set w to my p's item j
               end repeat
               
               if (i > j) then
               else
                   set my p's item i to w
                   set my p's item j to u
                   
                   -- Inform the script object of this swap.
                   compObj's swap(i, j)
                   
                   set i to i + 1
                   set j to j - 1
               end if
           end repeat
           
           if (j - l < cutoff) then
           else
               qsrt(l, j)
           end if
           if (r - i < cutoff) then
           else
               qsrt(i, r)
           end if
       end qsrt
       
       on isrt(l, r)
           set x to l
           set z to l + cutoff - 1
           if (z > r) then set z to r
           
           set v to my p's item x
           repeat with y from (x + 1) to z
               if (compObj's isLess(my p's item y, v)) then
                   set x to y
                   set v to my p's item y
               end if
           end repeat
           
           tell my p's item l
               set my p's item l to v
               set my p's item x to it
           end tell
           
           -- Inform the script object of this swap.
           compObj's swap(l, x)
           
           set u to my p's item (l + 1)
           repeat with i from (l + 2) to r
               set v to my p's item i
               if (compObj's isLess(v, u)) then
                   set my p's item i to u
                   repeat with j from (i - 2) to l by -1
                       if (compObj's isLess(v, my p's item j)) then
                           set my p's item (j + 1) to my p's item j
                       else
                           set my p's item (j + 1) to v
                           
                           -- Inform the script object of this insertion.
                           compObj's shift(j + 1, i)
                           
                           exit repeat
                       end if
                   end repeat
               else
                   set u to v
               end if
           end repeat
       end isrt
   end script
   
   set listLen to (count theList)
   if (listLen > 1) then -- otherwise the handler will error
       -- Translate negative indices
       if (l < 0) then set l to listLen + l + 1
       if (r < 0) then set r to listLen + r + 1
       
       if (r = l) then
           -- No point in sorting just one item
       else
           -- Transpose transposed indices
           if (l > r) then
               set temp to l
               set l to r
               set r to temp
           end if
           
           if (r - l < o's cutoff) then
               -- Skip the Quicksort if cutoff or less items
           else
               o's qsrt(l, r)
           end if
           o's isrt(l, r)
       end if
   end if
   
   return -- nothing
end CustomQsort

on getItemNames(theItems)
   set AppleScript's text item delimiters to ":"
   set theNames to {}
   repeat with thisItem in theItems
       set thisPath to thisItem as Unicode text
       set thisName to text item -1 of thisPath
       if ((count thisName) is 0) then set thisName to text item -2 of thisPath
       set end of theNames to thisName
   end repeat
   
   return theNames
end getItemNames

on padNumericsWithZeros(originalNames)
   set AppleScript's text item delimiters to return
   set originalNames to originalNames as Unicode text
   set theDigits to "0123456789" as Unicode text
   set theZeros to "00000000" as Unicode text
   set padWidth to (count theZeros)
   script o
       property doctoredNames : {}
   end script
   set i to 1
   considering case
       set numeric to (character i of originalNames is in theDigits)
       repeat with j from 1 to (count originalNames)
           set c to character j of originalNames
           if (numeric) then
               if (c is in theDigits) then
               else
                   set pad to padWidth + i - j
                   if (pad > 0) then set end of o's doctoredNames to text 1 thru pad of theZeros
                   set numeric to false
               end if
           else if (c is in theDigits) then
               if (j > i) then set end of o's doctoredNames to text i thru (j - 1) of originalNames
               set i to j
               set numeric to true
           end if
       end repeat
       if (numeric) then
           set pad to padWidth + i - j - 1
           if (pad > 0) then set end of o's doctoredNames to text 1 thru pad of theZeros
       end if
       if (i is not greater than j) then set end of o's doctoredNames to text i thru j of originalNames
   end considering
   set AppleScript's text item delimiters to ""
   
   return paragraphs of (o's doctoredNames as Unicode text)
end padNumericsWithZeros


tell application "Finder" to set theSelection to the selection

set astid to AppleScript's text item delimiters
set selectionNames to getItemNames(theSelection)
set doctoredNames to padNumericsWithZeros(selectionNames)
set AppleScript's text item delimiters to astid

script slaveSort
   property slaveList : missing value
   
   on isLess(a, b)
       (a < b)
   end isLess
   
   on isGreater(a, b)
       (a > b)
   end isGreater
   
   -- Do the same swap in slaveList that CustomQsort has just done in the list it's sorting.
   on swap(a, b)
       tell item a of my slaveList
           set item a of my slaveList to item b of my slaveList
           set item b of my slaveList to it
       end tell
   end swap
   
   -- Do the same shift and insertion in slaveList that CustomQsort has just done in the list it's sorting.
   on shift(a, b)
       tell item b of my slaveList
           repeat with i from b - 1 to a by -1
               set item (i + 1) of my slaveList to item i of my slaveList
           end repeat
           set item a of my slaveList to it
       end tell
   end shift
end script

set slaveSort's slaveList to theSelection
CustomQsort(doctoredNames, 1, -1, slaveSort)

theSelection

If you're more interested in the sorted names than in the sorted files/folders, substitute selectionNames for theSelection in the last three lines.

The above is very long (as you may have noticed!) but the CustomQsort handler can be saved as a separate script and loaded as a library.

Edit: Sorry. Although this works, it isn't quite as fast as I'd thought when the list contains a very large number of Finder items. The sort itself is virtually instantaneous, but the preparation of the names takes a while.

Last edited by Nigel Garvey (2006-07-31 05:22:51 am)


NG


Filed under: Finder

Offline

 

#14 2006-07-30 05:19:15 pm

Santa
Member
From:: Land of Oz
Registered: 2006-07-27
Posts: 486

Re: QuickSort Algorithm

G'day fellas.

Thanks for the replies. Here's an extract from my script. (this is to the long (shorter time) version of Qsort)

Applescript:


on mainCycle()
   tell application "Finder"
       
       set thelist to (selection as list)
       set distribute to number of items in thelist
       set thisItem to item 1 of thelist
       set we_are_on_desktop to ((folder of thisItem as alias) is (path to desktop folder))
       repeat with thisItem in thelist
           if we_are_on_desktop then
               set temp to desktop position of thisItem
           else
               set temp to position of thisItem
           end if
           set listofXY to listofXY & item 1 of temp & item 2 of temp as list
           set Xdifflist to Xdifflist & item 1 of temp as list
           set ydiffList to ydiffList & item 2 of temp as list
       end repeat
       
       my Qsort(Xdifflist, 1, (length of Xdifflist))
       my Qsort(ydiffList, 1, length of ydiffList)
       
       -- these are necessary 'cause Hoare's sort routine seems faulty!!!
       
       set LargestX to 0
       set SmallestX to 10000
       set LargestY to 0
       set SmallestY to 10000
       repeat with x from 1 to length of Xdifflist
           if LargestX < item x of Xdifflist then set LargestX to item x of Xdifflist
           if SmallestX > item x of Xdifflist then set SmallestX to item x of Xdifflist
           if LargestY < item x of ydiffList then set LargestY to item x of ydiffList
           if SmallestY > item x of ydiffList then set SmallestY to item x of ydiffList
       end repeat
   end tell
end mainCycle

Note that the fault is intermittant. I had arranged a block of icons alphabetically, and chose (from my full script) to arrange alphabetically again. The second time the reult of the sort saw the icons occupy only half the number of original rows, because the largest value of Y had not trickled to the top.

I stopped the script, re-ran it and on the second run it sorted the values correctly, placing the largest value of Y at the top.

Hoarse's just doesn't seem to run numbers by it. I just assumed these routines would sort numbers.

Regards

Santa

Model: G5
AppleScript: 1.10.7
Browser: Safari 419.3
Operating System: Mac OS X (10.4)


Just an enthusiastic old fart of an Apple user since the IIe days


Filed under: Finder

Offline

 

#15 2006-07-30 05:46:20 pm

Adam Bell
Administrator
From:: Nova Scotia, Canada
Registered: 2005-10-04
Posts: 4660

Re: QuickSort Algorithm

I've used them to sort dates and it certainly sorts a list of numbers only correctly. I think Nigel's "considering" clause is required if the list is mixed.


iMac running OS X 10.13.1

Offline

 

#16 2006-07-30 08:24:53 pm

Santa
Member
From:: Land of Oz
Registered: 2006-07-27
Posts: 486

Re: QuickSort Algorithm

G'day Adam

I definately think there's a bug in the Hoaer's Qsort Routine.

I've re-submitted my latest version of the icon arranger, but using a modified version of it I've been able to asertain there's an error that's reproducable.

I'll post the modified version here, and hope it's not too long.

Use it to arrange a window with lots of icons, alphabetically. It won't beep on the first pass.

Now arrange alphabetically again, while the icons are still selected. You'll get at least one beep (or at least, I can).

Rinse & Repeat smile

Fingers crossed it works for you as it does for me.

(Edit) I've just found it won't beep if it's run on a folder that's been organized by name by the Finder. The icons have to be physically shifted by the routine, before it will beep. Play around with it, scrunch 'em up tight, then arrange 'em Alphabetically.

Regards, Santa

Applescript:


-- ****************************
-- * Copyright 2006, Brian Christmas *
-- * *
-- * From the Sunny Land of Oz *
-- * Version 1.2 *
-- * 31/07/06 *
-- * *
-- * bec9@tpg.com.au *
-- ****************************
-- Qsort routine from MacScripter
-- [url]http://bbs.applescript.net/viewtopic.php?id=17340[/url]

-- This script works best if some approximate
-- organizing is done first, otherwise
-- extra columns may be added.

-- Also note that if insufficient side margins are not allowed for when arranging a window,
-- the Finder may 'shake' the window from side to side, thereby altering the icon placement.

-- In addition, if you have a window open showing the desktop icons in it, DON'T try to
-- arrange the window. It only organizes the ACTUAL desktop. Hairy things happen to it.
-- Feedback appreciated, especially suggestions to speed this up.

global overlapFlag
global we_are_on_desktop
global seedValue
global AlphabetMin

-- *******************************
-- **** Set this as minimum amount ****
-- **** allowed between columns ****
-- *******************************
set seedValue to 100

-- *******************************
-- **** Set this as minimum amount ****
-- **** of icons to offer ****
--**** alphabet sorting ****
-- *******************************
set AlphabetMin to 20

my mainCycle()

on mainCycle()
   tell application "Finder"
       set currX to 0
       set LargestY to 0
       set SmallestY to 0
       set SmallestX to 0
       set LargestX to 0
       set listofXY to ""
       set overlapFlag to 0
       set Xdifflist to ""
       set ydiffList to ""
       set columnCount to ""
       
       try
           -- make array of positions
           
           set thelist to (selection as list)
           set distribute to number of items in thelist
           --- ARE WE ON THE DESKTOP?
           if distribute = 0 then
               display dialog "There are no icons selected." & return & return & "Try selecting some, and running the script again." buttons {"OK"}
               
           end if
           set thisItem to item 1 of thelist
           set we_are_on_desktop to ((folder of thisItem as alias) is (path to desktop folder))
           
           -- Heaps of icons? then ask!
           set AlphaFlag to false
           if length of thelist > (AlphabetMin - 1) then
               display dialog " there are " & length of thelist & " icons selected." & return & return & "Do you want to sort them alphabetically or normally?" & return & return & "(it takes a while with large numbers)" buttons {"Alphabetically please", "Normally thanks", "Cancel"}
               set AlphaFlag to (the button returned of the result is "Alphabetically please")
           end if
           
           
           repeat with thisItem in thelist
               if we_are_on_desktop then
                   set temp to desktop position of thisItem
               else
                   set temp to position of thisItem
               end if
               set listofXY to listofXY & item 1 of temp & item 2 of temp as list
               --set listofXY to listofXY & item 2 of temp as list
               set Xdifflist to Xdifflist & item 1 of temp as list
               set ydiffList to ydiffList & item 2 of temp as list
           end repeat
           
           my Qsort(Xdifflist, 1, (length of Xdifflist))
           my Qsort(ydiffList, 1, length of ydiffList)
           
           -- these are necessary 'cause Hoare's sort routine is faulty!!!
           
           set LargestX to last item of Xdifflist
           set SmallestX to 10000
           set LargestY to 0
           set SmallestY to 10000
           repeat with x from 1 to length of Xdifflist
               if LargestX < item x of Xdifflist then
                   beep
                   set LargestX to item x of Xdifflist
               end if
               if SmallestX > item x of Xdifflist then set SmallestX to item x of Xdifflist
               if LargestY < item x of ydiffList then set LargestY to item x of ydiffList
               if SmallestY > item x of ydiffList then set SmallestY to item x of ydiffList
           end repeat
           
           if we_are_on_desktop then
               set seedValueadd to ((label position of icon view options of window of desktop) = right)
           else
               set seedValueadd to ((label position of icon view options of window 1) = right)
           end if
           
           -- If text is on right, double the minimum spacing
           if seedValueadd = true then set seedValue to seedValue * 2
           
           -- Now the guessing part, what to distribute as column spacing?
           
           set setX to seedValue
           repeat with x from ((length of Xdifflist) - 1) to 1 by -1
               set diff to ((item (x + 1) of Xdifflist) - (item x of Xdifflist))
               if diff < (2 + ((LargestX - SmallestX) / 2)) then
                   if (diff > seedValue - 1) then
                       set setX to diff
                   end if
               end if
           end repeat
           --Now, set width between columns
           
           set columnSpaces to ((LargestX - SmallestX + (setX / 2)) div setX)
           
           --Only 1 column? then set columnSpace to ....
           
           if columnSpaces < 2 then set columnSpaces to columnSpaces + 1
           set ColumnWidth to (LargestX - SmallestX) / columnSpaces
           if ColumnWidth < seedValue then set ColumnWidth to seedValue
           set columnCount to columnSpaces + 1
           set columnCountStore to 0
           repeat with x from 1 to columnSpaces
               set columnCountStore to columnCountStore & 0
           end repeat
           repeat with x from 1 to columnCount
               set minX to SmallestX + ((x - 1) * ColumnWidth) - (ColumnWidth / 2)
               set maxX to SmallestX + ((x - 1) * ColumnWidth) + (ColumnWidth / 2)
               
               repeat with thisItem in thelist
                   if we_are_on_desktop then
                       set temp to desktop position of thisItem
                   else
                       set temp to position of thisItem
                   end if
                   set tempY to item 2 of temp
                   set tempX to item 1 of temp
                   -- if icon falls in the range of column, add it up
                   if ((tempX = minX) or (tempX > minX)) and (tempX < maxX) then
                       set item x of columnCountStore to ((item x of columnCountStore) + 1)
                   end if
               end repeat
           end repeat
           
           if AlphaFlag then --> Alphabet arrange set
               set IconSpacing to (LargestY - SmallestY) / ((distribute / columnCount) div 1)
           else
               
               -- Now find Column with largest number of icons
               
               set maxCount to 2 ---> to avoid division by zero if only one row
               repeat with x from 1 to number of items in columnCountStore
                   if item x of columnCountStore > maxCount then
                       set maxCount to item x of columnCountStore
                   end if
               end repeat
               set IconSpacing to ((LargestY - SmallestY) / (maxCount - 1))
           end if
           
           if AlphaFlag then
               my SortbyAlphabet(thelist, SmallestX, LargestX, SmallestY, ColumnWidth, IconSpacing)
           else
               -- Now place Icons
               -- Loop ColumnCount times....
               repeat with MoveColumns from 1 to columnCount
                   set tempList to ""
                   set minX to SmallestX + ((MoveColumns - 1) * ColumnWidth) - (ColumnWidth / 2)
                   set maxX to SmallestX + ((MoveColumns - 1) * ColumnWidth) + (ColumnWidth / 2)
                   
                   repeat with thisItem in thelist
                       if we_are_on_desktop then
                           set temp to desktop position of thisItem
                       else
                           set temp to position of thisItem
                       end if
                       set tempX to item 1 of temp
                       if (((tempX = minX) or (tempX > minX)) and ((tempX < maxX) or (tempX = maxX))) then
                           --Build list of icon XY positions in column
                           if tempList = "" then
                               set tempList to tempX as list
                               set tempList to tempList & item 2 of temp
                           else
                               set tempList to tempList & tempX
                               set tempList to tempList & item 2 of temp
                           end if
                       end if
                   end repeat
                   -- This is the X value of the column
                   set tempX to SmallestX + ((MoveColumns - 1) * ColumnWidth)
                   --
                   -- Now go and shift a column of the little bastards around!
                   --
                   my ArrangeColumn(thelist, tempList, tempX, SmallestY, IconSpacing)
                   
               end repeat
           end if
       end try
       if overlapFlag > 0 then
           if overlapFlag = 1 then
               set Errormessage to "There was an overlapping icon." & return & return & "I'll try running the script again, as I've nudged it."
           else
               set Errormessage to "There were " & overlapFlag & " overlapping icons." & return & return & "I'll try running the script again, as I've nudged them."
           end if
           display dialog Errormessage buttons {"OK", "Cancel"}
           if (the button returned of the result is "OK") then
               my mainCycle() -- Do the run around again
           end if
       end if
   end tell
end mainCycle

-- =============================================================

on ArrangeColumn(thelist, tempList, currX, SmallestY, IconSpacing)
   tell application "Finder"
       set listofXY to ""
       try
           -- Start with a Y seed position, to overcome
           -- problem with 1 entry not seen as an item
           set Ylist to 0
           --
           -- Now make list of Y positions
           repeat with thisItem in thelist
               repeat
                   if we_are_on_desktop then
                       set temp to desktop position of thisItem
                   else
                       set temp to position of thisItem
                   end if
                   if temp is in tempList then
                       if item 2 of temp is in Ylist then --> Oops! Some icons together!
                           set tempShift to item 1 of temp & ((item 2 of temp) + 1 + overlapFlag)
                           set overlapFlag to overlapFlag + 1
                           --Nudge overlapping icons
                           if we_are_on_desktop then
                               set desktop position of thisItem to tempShift
                           else
                               set position of thisItem to tempShift
                           end if
                           -- now reset templist Y position
                           set x to 2
                           repeat
                               if item x of tempList = item 2 of temp then
                                   set item x of tempList to item 2 of tempShift
                                   exit repeat
                               else
                                   set x to (x + 2)
                                   if x > number of items in tempList then exit repeat --> just in case
                               end if
                           end repeat
                       else
                           set Ylist to Ylist & item 2 of temp
                           exit repeat
                       end if
                   else
                       exit repeat
                   end if
               end repeat
           end repeat
           --
           -- Sort Y positions
           my Qsort(Ylist, 1, length of Ylist)
           --
           -- Now position each
           repeat with thisItemTwo in thelist
               if we_are_on_desktop then
                   set temp to desktop position of thisItemTwo
                   if temp is in tempList then
                       set tempY to item 2 of temp
                       repeat with countdown from 2 to (number of items in Ylist)
                           if item countdown of Ylist = tempY then
                               set currY to SmallestY + ((countdown - 2) * IconSpacing)
                               set countdown to (number of items in Ylist)
                           end if
                       end repeat
                       set desktop position of thisItemTwo to {currX, currY}
                   end if
               else
                   set temp to position of thisItemTwo
                   if temp is in tempList then
                       set tempY to item 2 of temp
                       repeat with countdown from 2 to (number of items in Ylist)
                           if item countdown of Ylist = tempY then
                               set currY to SmallestY + ((countdown - 2) * IconSpacing)
                               set countdown to number of items in Ylist
                           end if
                       end repeat
                       set position of thisItemTwo to {currX, currY}
                   end if
               end if
           end repeat
       end try
   end tell
end ArrangeColumn

on SortbyAlphabet(thelist, SmallestX, LargestX, SmallestY, ColumnWidth, IconSpacing)
   
   tell application "Finder"
       try
           set tempList to ""
           -- First, sort list of icons alphabetically
           set xx to length of thelist
           repeat with x from 1 to xx
               set firstGo to name of item x of thelist as string
               if tempList = "" then
                   set tempList to firstGo as list
               else
                   set tempList to tempList & firstGo as list
               end if
           end repeat
           my Qsort(tempList, 1, xx)
           set iconPos to 1
           repeat with mainCount from 1 to xx
               set Xposition to SmallestX + ((iconPos - 1) * ColumnWidth)
               set tempName to item mainCount of tempList
               repeat with thisItem in thelist
                   if tempName = name of thisItem then
                       if we_are_on_desktop then
                           set desktop position of thisItem to {Xposition, SmallestY}
                       else
                           set position of thisItem to {Xposition, SmallestY}
                       end if
                       set iconPos to iconPos + 1
                       if iconPos > (((LargestX - SmallestX) / ColumnWidth) + 1) then
                           set iconPos to 1
                           set SmallestY to SmallestY + IconSpacing
                       end if
                       exit repeat
                   end if
               end repeat
           end repeat
       end try
   end tell
end SortbyAlphabet


to Qsort(array, leftEnd, rightEnd) -- Hoare's QuickSort Algorithm
   script A
       property L : array
   end script
   set {i, j} to {leftEnd, rightEnd}
   set v to item ((leftEnd + rightEnd) div 2) of A's L -- pivot in the middle
   repeat while (j > i)
       repeat while (item i of A's L < v)
           set i to i + 1
       end repeat
       repeat while (item j of A's L > v)
           set j to j - 1
       end repeat
       if (not i > j) then
           tell A's L to set {item i, item j} to {item j, item i} -- swap
           set {i, j} to {i + 1, j - 1}
       end if
   end repeat
   if (leftEnd < j) then Qsort(A's L, leftEnd, j)
   if (rightEnd > i) then Qsort(A's L, i, rightEnd)
end Qsort

(Edit) This was the bit that was modified

Applescript:

set LargestX to last item of Xdifflist
set SmallestX to 10000
set LargestY to 0
set SmallestY to 10000
repeat with x from 1 to length of Xdifflist
if LargestX < item x of Xdifflist then
beep
set LargestX to item x of Xdifflist
end if
if SmallestX > item x of Xdifflist then set SmallestX to item x of Xdifflist
if LargestY < item x of ydiffList then set LargestY to item x of ydiffList
if SmallestY > item x of ydiffList then set SmallestY to item x of ydiffList
end repeat

Model: G5
AppleScript: 1.10.7
Browser: Safari 419.3
Operating System: Mac OS X (10.4)

Last edited by Santa (2006-07-30 08:51:30 pm)


Just an enthusiastic old fart of an Apple user since the IIe days


Filed under: Finder

Offline

 

#17 2006-07-31 03:02:00 am

Santa
Member
From:: Land of Oz
Registered: 2006-07-27
Posts: 486

Re: QuickSort Algorithm

This is really, really weird.

I've got 151 icons, arranged in a 12x12 grid, alphabetically, with an extra row of 7 across the bottom left.

If I re-sort alphabetically, using the script above, I get an error from the Hoare's Qsort algorithm.

If I move any single icons of rows 1,2,3,4 or 6,7,8,9, or 11 or 12 of the far right column in just a fraction, I get no error.

If I move in icon 5 or 10, I still get an error in the sort. Repeatably.

Does this make any sense?

I'm heading to Europe on Wednesday, for 8 weeks hols, so someones got plenty of time to give me an answer. Anyone?

Bewilderdly yours, cool  (an old fart in the sun)

Santa

(edit) I spread the icons out slightly, and now I'm getting errors (beeps) no matter what I do to the right column, or any of them.
I think there's bad, bad gremlins hard at work in my processor, if I listen carefully I'm sure I can hear the little B*****ds hammering.
My icon arranging algorithim traps any errors, so it's no big deal, just that things like this gnaw at my old, delicate nature big_smile

Model: G5
AppleScript: 1.10.7
Browser: Safari 419.3
Operating System: Mac OS X (10.4)

Last edited by Santa (2006-07-31 04:54:32 am)


Just an enthusiastic old fart of an Apple user since the IIe days

Offline

 

#18 2006-07-31 05:28:19 am

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 4488

Re: QuickSort Algorithm

Hi, Brian.

The problem's not with the sort routines. At the top of mainCycle(), you've intialised listofXY, Xdifflist, and ydiffList to empty strings, not to empty lists. Since you're using concatenation to build up the lists, the first number that's concatenated to each is coerced to string:

Applescript:

set Xdifflist to ""
set temp to {89, 40}

set Xdifflist to Xdifflist & item 1 of temp
--> "89"

You coerce the result of that to list, so that thereafter, Xdifflist is a list and any further numbers will be coerced to list for concatenation to a list, rather than to string for concatenation to a string:

Applescript:

set Xdifflist to ""
set temp to {89, 40}

set Xdifflist to Xdifflist & item 1 of temp as list
--> {"89"}

set temp to {346, 40}
set Xdifflist to Xdifflist & item 1 of temp as list
--> {"89", 346}

You're thus sorting lists where one of the "numbers" is actually a string. It's that which isn't necessarily being sorted as you'd like. (The results of the number/numeric string comparisons within the sort depend on whether the number's being compared with the string or the string with the number!)

So, you should initialise those three variables to empty lists instead:

Applescript:

set listofXY to {}
set Xdifflist to {}
seet ydiffList to {}

It's also more efficient to append items to lists, rather than concatenating them:

Applescript:

set end of Xdifflist to item 1 of temp

The sort routines having been exonerated, any further problems with the script should properly be posted to the OS X forum.

Enjoy your holiday!  smile


NG

Offline

 

#19 2006-07-31 05:46:22 am

Santa
Member
From:: Land of Oz
Registered: 2006-07-27
Posts: 486

Re: QuickSort Algorithm

Thank you very, very much Nigel.

It's been driving me nuts, being a newbie.

A lesson well learnt.

Santa


Just an enthusiastic old fart of an Apple user since the IIe days

Offline

 

#20 2006-08-05 07:38:27 pm

Kevin Bradley
Administrator
From:: Independence, MO
Registered: 2006-03-13
Posts: 548
Website

Re: QuickSort Algorithm

Hey, glad to see this thread, it helped me a lot.  I wrote my own version, using the "optimized pivot" method and got this code:

Applescript:

on quickSort(theList)
   --public routine, called from your script
   script bs
       property alist : theList
       
       on Qsort(leftIndex, rightIndex)
           --private routine called by quickSort.
           --do not call from your script!
           if rightIndex > leftIndex then
               set pivot to ((rightIndex - leftIndex) div 2) + leftIndex
               set newPivot to Qpartition(leftIndex, rightIndex, pivot)
               set theList to Qsort(leftIndex, newPivot - 1)
               set theList to Qsort(newPivot + 1, rightIndex)
           end if
           
       end Qsort
       
       on Qpartition(leftIndex, rightIndex, pivot)
           --private routine called by quickSort.
           --do not call from your script!
           set pivotValue to item pivot of bs's alist
           set temp to item pivot of bs's alist
           set item pivot of bs's alist to item rightIndex of bs's alist
           set item rightIndex of bs's alist to temp
           set tempIndex to leftIndex
           repeat with pointer from leftIndex to (rightIndex - 1)
               if item pointer of bs's alist ≤ pivotValue then
                   set temp to item pointer of bs's alist
                   set item pointer of bs's alist to item tempIndex of bs's alist
                   set item tempIndex of bs's alist to temp
                   set tempIndex to tempIndex + 1
               end if
           end repeat
           set temp to item rightIndex of bs's alist
           set item rightIndex of bs's alist to item tempIndex of bs's alist
           set item tempIndex of bs's alist to temp
           
           return tempIndex
       end Qpartition
       
   end script
   
   if length of bs's alist > 1 then bs's Qsort(1, length of bs's alist)
   return bs's alist
end quickSort

I've run it against Adam's and Nigel's versions and it performs in between the them.  On my 450mhz iMac, Nigels took 2 seconds to sort 4000 numbers, Adam's took 7 seconds (after I made Nigel's fix for the "reference to"), and mine took 4.  I was honestly surprised, as I figured the recursive nature of mine would hurt its performance, but it didn't seem to.

The "optimized pivot" takes the pivot and actually puts it in the appropriate position before beginning to sort the sides. 

Anyway, after I wrote mine, I went back and looked at Nigel's and Adam's and tweaked mine a bit to help it along.  Moving my Qsort and Qpartition routines into the script object was a huge help!

The sharing of code is the single greatest advantage any of us have.  I'm so glad we have MacScripter!


Nitewing '98
--
I distrust morning people, largely because I suspect them of getting together early one day while the rest of us were asleep and setting up the rules of civilization.

Offline

 

#21 2006-08-06 08:29:51 am

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 4488

Re: QuickSort Algorithm

Hi, Kevin.

That "optimized pivot" idea looks very interesting. Thanks for posting it. I'm going to have a happy couple of days trying to analyse it to see if Arthur's and my effort can benefit from it!  smile

Meanwhile, I've taken the liberty of applying a couple of optimisations to your Qpartition() handler. Basically, they use existing variable values to reduce the number of times the list is accessed. There's also an exploitation of an AppleScript quirk whereby "simple" comparisons are faster than "compound" ones. It's faster to do this …

Applescript:

if a > b then
else
   -- Do something.
end if

… than this:

Applescript:

if a ≤ b then
   -- Do something.
end if

Similarly with ≥ and not. It's faster to test their antitheses than to test them. The difference is minimal, but every little helps in a large sort!

Applescript:

on Qpartition(leftIndex, rightIndex, pivot)
   --private routine called by quickSort.
   --do not call from your script!
   set pivotValue to item pivot of bs's alist
   --set temp to item pivot of bs's alist -- We already have this as pivotValue.
   set item pivot of bs's alist to item rightIndex of bs's alist
   --set item rightIndex of bs's alist to temp -- No need to put it back in the list.
   set tempIndex to leftIndex
   repeat with pointer from leftIndex to (rightIndex - 1)
       set temp to item pointer of bs's alist -- temp set here to save getting the item twice.
       if temp > pivotValue then --≤ pivotValue then
       else
           --set temp to item pointer of bs's alist -- Moved up.
           set item pointer of bs's alist to item tempIndex of bs's alist
           set item tempIndex of bs's alist to temp
           set tempIndex to tempIndex + 1
       end if
   end repeat
   --set temp to item rightIndex of bs's alist -- Already in pivotValue.
   set item rightIndex of bs's alist to item tempIndex of bs's alist
   set item tempIndex of bs's alist to pivotValue --temp
   
   return tempIndex
end Qpartition


NG

Offline

 

#22 2006-08-06 08:39:50 am

Kevin Bradley
Administrator
From:: Independence, MO
Registered: 2006-03-13
Posts: 548
Website

Re: QuickSort Algorithm

Nigel wrote:

Meanwhile, I've taken the liberty of applying a couple of optimisations to your Qpartition() handler. Basically, they use existing variable values to reduce the number of times the list is accessed. There's also an exploitation of an AppleScript quirk whereby "simple" comparisons are faster than "compound" ones.


Funny you should mention.  As I was writing this (and the other sorts - bubble, insertion, and merge) I found myself wondering if there was a difference, but I didn't code it up to see if there was.

Thanks Nigel! cool


Nitewing '98
--
I distrust morning people, largely because I suspect them of getting together early one day while the rest of us were asleep and setting up the rules of civilization.

Offline

 

#23 2006-10-24 06:30:49 am

ekel75
Member
Registered: 2006-08-10
Posts: 4

Re: QuickSort Algorithm

Hey everybody
as I'm not the perfect scripter as you guys, I'm having a hard time to transform the qsort routine into a qsort the would match my needs.
I've been using Kevins's pivot version at the moment - and was also unsuccesfully trying to implement Nigel's superfast version (I'm working in a tell application routine and I couldn't call Nigel's routine through that)

What I actually want to achieve is removing the duplicates, while sorting the list.

As I didn't get that done, for the moment, I'm rearranging the sorted list like that:

Applescript:


               set srtLst to my quickSort(Lst)
       set lgthsrtLst to srtLst's length
       set Lst to {}
       repeat with x1 from 1 to lgthsrtLst
           set TmpItm to item x1 of srtLst
           if x1 < (lgthsrtLst) then
               if TmpItm = item (x1 + 1) of srtLst then
               else
                   set Lst to Lst & TmpItm
               end if
           end if
           if x1 = (lgthsrtLst) then set Lst to Lst & TmpItm
       end repeat

It would probably be much faster, if I'd erase the duplicates directly in the qsort handler.
could you give me a hint on how to get that done?

Thank you so very much!
And most important thank you so much for posting your wisdom in general!!

ekel75



PS. do you know which is faster, using a variable for 3 to 4 instances in a script

Applescript:

           set lgthCalcNum to CalcNum's length
           if (lgthCalcNum) > 6 then set CalcNum to (text 1 thru ((lgthCalcNum) - 6) of CalcNum) & "." & text ((lgthCalcNum) - 5) thru (lgthCalcNum) of CalcNum

or not!? ( like this )
   

Applescript:

       if (CalcNum's length) > 6 then set CalcNum to (text 1 thru ((CalcNum's length) - 6) of CalcNum) & "." & text ((CalcNum's length) - 5) thru (CalcNum's length) of CalcNum

Model: Desktop G4 800MHz
AppleScript: AppleScript D1-1.9.3
Browser: Firefox 1.5.0.7
Operating System: Mac OS X (10.4)

Last edited by ekel75 (2006-10-24 08:32:33 am)

Offline

 

#24 2006-10-24 05:56:22 pm

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 4488

Re: QuickSort Algorithm

Hi, ekel75.

I don't think that combining a sort with removing the duplicates would actually be faster. Sorts do a large number of item comparisons – often a very large number. The comparisons check if one item is greater or less than another. It would greatly increase the workload if each stage of the sort also included a check to see if the items were equal, and making a new list every time a duplicate was found would increase it even more. There may be an effective way to reduce the slow-down, but I can't see it.

Your process of sorting the list first and then building another without the duplicates is probably the best way. I'd code it something like this:

Applescript:

-- A script object for speed of access to the lists.
script o
   property sortedList : missing value
   property prunedList : missing value
end script

-- Do the sort.
set o's sortedList to quickSort(myList)

-- Since the list has been sorted, equal values will be together, not randomly distributed.

-- Initialise a check value to the first item in the sortedList
set checkValue to item 1 of o's sortedList
-- Start off the pruned list with that value.
set o's prunedList to {checkValue}
repeat with i from 2 to (count o's sortedList)
   set thisValue to item i of o's sortedList
   if (thisValue is checkValue) then
       -- If this value's a duplicate, skip it.
   else
       -- Otherwise, we've reached (a possible run of) a new value.
       -- Append this value to the pruned list and make it the new check value.
       set end of o's prunedList to thisValue
       set checkValue to thisValue
   end if
end repeat
set myList to o's prunedList

Another way, if the items in the list are all of the same class and you know when you write the script what that will be, is this:

Applescript:

-- A script object for speed of access to the list.
script o
   property sortedList : missing value
end script

-- Do the sort.
set o's sortedList to quickSort(myList)

-- Since the list has been sorted, equal values will be together, not randomly distributed.

-- Initialise a check value to the first item in the sortedList
set checkValue to item 1 of o's sortedList
repeat with i from 2 to (count o's sortedList)
   set thisValue to item i of o's sortedList
   if (thisValue is checkValue) then
       -- If this value's a duplicate, replace it with 'missing value'
       set item i of o's sortedList to missing value
   else
       -- Otherwise, we've reached (a possible run of) a new value.
       -- Make it the new check value.
       set checkValue to thisValue
   end if
end repeat

-- Assuming that this is a list of integers, return the integers (not the 'missing values').
set myList to o's sortedList's integers

I've just seen the addendum to your post. The version with the variable should be slightly faster, but the difference will be miniscule with just those two lines. Basically, retrieving a value from a variable is faster than calling a function or using a reference to work it out again.


NG

Offline

 

#25 2006-10-25 06:31:57 am

ekel75
Member
Registered: 2006-08-10
Posts: 4

Re: QuickSort Algorithm

Dear Nigel,

thank you very much for your quick response and all your effort!
I like your routine very much. My approach has the same basic principle but your's just got that neatly programmed twist to it.
Simply pro! wink Thank you very much for making me understand Applescript +  programming more and more smile

So now I'm trying to implement your second version, since it's all the same class.
I tried it with an empty script and worked like a charm.

Trying to implement it doesn't work too well though sad

I'm in a < tell application > routine, and some of the stuff from Applescript has to be handled differently from within < tell application, >
which I haven't fully figured out yet. (Which is why I'm not using your quicksort sad ) Calling subroutines works fine though,
so I tried to put your script into a new handler and calling it up like that:


Applescript:

tell application "Adobe InDesign CS2"
   activate
tell document 1
...
       set Lst to my pruneList(Lst)
...
end tell
end tell

--
--Subroutines

on quickSort(theLst)
...
end quickSort

on pruneList(thePruneLst)
   script o
       property sortedList : missing value
   end script
   set o's sortedList to my quickSort(thePruneLst)
   -- Initialise a check value to the first item in the sortedList
   set checkValue to item 1 of o's sortedList
   repeat with i from 2 to (count o's sortedList)
       set thisValue to item i of o's sortedList
       if (thisValue is checkValue) then
           -- If this value's a duplicate, replace it with 'missing value'
           set item i of o's sortedList to missing value
       else
           -- Otherwise, we've reached (a possible run of) a new value.
           -- Make it the new check value.
           set checkValue to thisValue
       end if
   end repeat
   return o's sortedList's text
end pruneList

But somehow I'm not getting it right. Am I not allowed to call the quickSort handle from within a second handler ?
Are some values not transported right!?!? hmm

thank you very much for your help!

ekel75


--
-- FOUND IT !?!
--
I guess I found it myself, though I still don't get why it worked before!

the list "Lst" is not actual text but a reference to text within an Indesign Document...
it looks like this
{text from character 1 to character 7 of cell id 0 of table id 853847 of cell id 26 of table id 853696 of cell id 2 of table id 853446 of text frame id 852504 of page id 852502 of spread id 852497 of document "testdoc.indd" of application "Adobe InDesign CS2", ...}
so I included this:

Applescript:

       set Lst to (search with find attributes {applied character style:CharStyle})
       repeat with x from 1 to (count of Lst)
           set item x of Lst to item x of Lst as text
       end repeat
       set Lst to my pruneList(Lst)

what do you think? you probably have some slick coded idea up your sleeve right as you're reading this wink

greetz e/

Last edited by ekel75 (2006-10-25 06:42:30 am)


Filed under: adobe

Offline

 

Board footer

Powered by FluxBB

RSS (new topics) RSS (active topics)