QuickSort under OS X

With OS 9 I used the following QuickSort routine which run pretty fast:

on QuickSortcolor=#020202
[/color]set Laenge to count Liste
if Laenge < 2 then return Liste
set ListeKleiner to {}
set ListeGleich to {}
set ListeGroesser to {}
set Vergleich to item 1 of Liste
set Zaehler to 1
repeat while Zaehler <= Laenge
set Element to (item Zaehler of Liste)
if Element < Vergleich then
set end of ListeKleiner to Element
else if Element > Vergleich then
set end of ListeGroesser to Element
else
set end of ListeGleich to Element
end if
end repeat
return (QuickSortcolor=#020202 & [/color]ListeGleich & QuickSortcolor=#020202)
[/color]end QuickSort

Now with OS 10.2.6, AppleScript 1.9.1 it runs … and runs … and runs … until I cancel the script.

What’s going wrong here?

Is this a typo? If not, how is the “?” used. I have never seen it before.
Otherwise, I don’t see anything wrong.

Brad Bumgarner, CTA

Sorry, it’s a fault of the phpBB2-Skript.
In my script the ? means <=

Now I’ve corrected this in the above script.

Putting the language barrier aside, would this part of the script not result in an endless loop since the values of Zaehler and Laenge are never changed (as far as I can determine)?

set Zaehler to 1
	repeat while Zaehler is less than or equal to Laenge

– Rob

It’s a bit difficult because of the language issue but it appears that you are in a perpetual loop because of this:

repeat while Zaehler <= Laenge

yet you never increment Zaehler, it is always at 1. Are you sure this code worked on OS 9? If you just want a quick sort routine, try:

Jon

:oops:

I must have lost this line:

set Zaehler to Zaehler + 1

:frowning: :oops: :cry:

Thanks for your help!

@ Jon

After inserting the missing line, I’ve done some speed testing.

The routine you posted is very slow with larger lists.

A = my routine
B = the routine, you posted above

First test:

A list with 952 items (no duplicates)

A: 20 seconds
B: I have canceled the script after several minutes

Second test:

a list with 250 items (no duplicates)

A: 1 second
B: 107 seconds

Third test:

a list with 250 items (with duplicates)

A: 1 second
B: 108 seconds

I was just doing some testing and got the same results as well. For vanilla AS projects, I’ll be switching to your routine. For most of my internal projects, however, I usually rely on a Scripting Addition for sorting (such as Acme Script Widgets).

Jon

If you want a really fast sorting routine, take the one, Arthur J. Knapp posted at the AppleScript mailing list.

It needs 2 seconds for sorting a list with 1000 items.

on QuickSort(a, l, r)
(*

* Sorts “in-place”:
*
* set a to { 2, 3, 1 }
*
* QuickSort( a, 1, a’s length ) – no return value
*
* get a → { 1, 2, 3 }
[color=#020202]*)

[/color]local i, j, v> SD debugging[color=#020202]

([/color] Much thanks to Serge Belleudy-d’Espinose for that
* extra surge of speed. :slight_smile:
[color=#020202]
)
[/color]script o
property p : a
end script[color=#020202]

[/color]set i to l
set j to r
set v to o’s p’s item ((l + r) div 2[color=#020202])

[/color]repeat while (j > i[color=#020202])

  [/color][b]repeat[/b] [b]while[/b][color=#020202] ([/color][color=#B70A0A]o[/color][color=#020202]'s [/color][color=#B70A0A]p[/color][color=#020202]'s [/color]item [color=#B70A0A]i[/color][color=#020202] < [/color][color=#B70A0A]v[/color][color=#020202])
     [/color][b]set[/b] [color=#B70A0A]i[/color] [b]to[/b] [color=#B70A0A]i[/color][color=#020202] + [/color][color=#010580]1[/color][color=#020202]
  [/color][b]end[/b] [b]repeat[/b][color=#020202]
  
  [/color][b]repeat[/b] [b]while[/b][color=#020202] ([/color][color=#B70A0A]o[/color][color=#020202]'s [/color][color=#B70A0A]p[/color][color=#020202]'s [/color]item [color=#B70A0A]j[/color][color=#020202] > [/color][color=#B70A0A]v[/color][color=#020202])
     [/color][b]set[/b] [color=#B70A0A]j[/color] [b]to[/b] [color=#B70A0A]j[/color][color=#020202] - [/color][color=#010580]1[/color][color=#020202]
  [/color][b]end[/b] [b]repeat[/b][color=#020202]
  
  [/color][b]if[/b][color=#020202] ([/color][b]not[/b] [color=#B70A0A]i[/color][color=#020202] > [/color][color=#B70A0A]j[/color][color=#020202]) [/color][b]then[/b][color=#020202]
     
     (*[/color][color=#3C5846]    set { i, j } to { j, i }
             [/color][color=#020202]*)
     [/color][b]set[/b] [color=#B70A0A]o_s_p_s_item_i[/color] [b]to[/b] [color=#B70A0A]o[/color][color=#020202]'s [/color][color=#B70A0A]p[/color][color=#020202]'s [/color]item [color=#B70A0A]i[/color][color=#020202]
     [/color][b]set[/b] [color=#B70A0A]o[/color][color=#020202]'s [/color][color=#B70A0A]p[/color][color=#020202]'s [/color]item [color=#B70A0A]i[/color] [b]to[/b] [color=#B70A0A]o[/color][color=#020202]'s [/color][color=#B70A0A]p[/color][color=#020202]'s [/color]item [color=#B70A0A]j[/color][color=#020202]
     [/color][b]set[/b] [color=#B70A0A]o[/color][color=#020202]'s [/color][color=#B70A0A]p[/color][color=#020202]'s [/color]item [color=#B70A0A]j[/color] [b]to[/b] [color=#B70A0A]o_s_p_s_item_i[/color][color=#020202]
     
     [/color][b]set[/b] [color=#B70A0A]i[/color] [b]to[/b] [color=#B70A0A]i[/color][color=#020202] + [/color][color=#010580]1[/color][color=#020202]
     [/color][b]set[/b] [color=#B70A0A]j[/color] [b]to[/b] [color=#B70A0A]j[/color][color=#020202] - [/color][color=#010580]1[/color][color=#020202]
     
  [/color][b]end[/b] [b]if[/b][color=#020202]

[/color]end repeat[color=#020202]

[/color]if (l < j) then QuickSort(o’s p, l, j)
if (r > i) then QuickSort(o’s p, i, r)
return aend QuickSort

My problem with this routine: I don’t understand it. :cry:

Do you mean that you don’t know which parameters to feed the routine? If so, it shouldn’t be too difficult to contact Arthur for clarification. You might get the answer from him or someone else on the applescript-users mailing list.

If that’s not what you meant, and you just don’t understand the internal code, I wouldn’t worry about it. As long as code comes from a trusted source (I trust Arthur K.) , I will use it if even if I do not understand it. That’s the beauty of open source/shared code. I don’t understand everything about my computer but here I am, typing away! :wink:

– Rob

I would also trust Arthur’s code. The problem I have with his sort routine, however, is that I get an error when I try to sort lists with mixed values such as {“z”, 3, 2, 1, “a”}.

Jon

Hi Rob,

there’s no problem with the parameters.

set myList to {"3", "98", "1", "32", "13", "9", "5"}
set newList to QuickSort(myList, 1, myList’s length)

The first ist the variable that contains the list, the second is the point where the list will be splitted and the third is the count of items within that list.

What I meant was that I failed to analyze what’s going on there.


Let’s see if I can be coherent at 2:30 in the morning. :wink:

Arthur’s script sorts “in place” - ie. it rearranges the items in the original list. (It doesn’t create a sorted copy.) Because of its form, you have to specify start values for the indices that delimit the sort area in the list. To sort the entire list, the start indices must be the first and last in the list - ie. 1 and the list’s length.

on QuickSort(a, l, r)
   (*
         *    Sorts "in-place":
         *
         *        set a to { 2, 3, 1 }
         *
         *        QuickSort( a, 1, a's length ) -- no return value
         *
         *        get a --> { 1, 2, 3 }
         *)
 
   local i, j, v --> SD debugging
 
   (*    Much thanks to Serge Belleudy-d'Espinose for that
         *    extra surge of speed.    :-)
         *)
   script o
     property p : a
   end script

For arcane technical reasons, access to items in a list is faster if you use a reference to refer to the list rather than a simple variable. By assigning the list to a property ‘p’ in a script object ‘o’, you can call it ‘o’s p’ (a reference) rather than simply ‘a’ (a straightforward variable). Serge Belleudy-d’Espinose is credited with discovering this technique.

   set i to l
   set j to r
   set v to o's p's item ((l + r) div 2)

‘l’ and ‘r’ are the left and right limits of the sort in each particular iteration of the handler. ‘i’ and ‘j’ start off as copies of these and then move towards each other. ‘v’ is the value of an item approximately in the middle of the sort area. The goal for each iteration is that all items to the left of the centre item should less than or equal to it, and all items to the right should be greater than or equal to it.

   repeat while (j > i)

Repeat until the converging indices meet or cross.

   repeat while (o's p's item i < v)
      set i to i + 1
   end repeat

Move the left moveable index to the right until an item’s found that’s NOT less than the centre item.

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

Similarly, move the right moveable index to the left until an item’s reached that’s not greater than the centre item.

   if (not i > j) then
    
      (*    set { i, j } to { j, i }
                 *)
      set o_s_p_s_item_i to o's p's item i
      set o's p's item i to o's p's item j
      set o's p's item j to o_s_p_s_item_i
    
      set i to i + 1
      set j to j - 1
    
   end if
   end repeat

If the moveable indices haven’t crossed, exchange the item on the left with the item on the right and converge the indices again by one step each. Continue until the indices meet or cross in the middle, by which time all the items to the left will be less than or equal to the centre item and all the items to the right will be greater than or equal to it.

   if (l < j) then QuickSort(o's p, l, j)
   if (r > i) then QuickSort(o's p, i, r)
   return a
end QuickSort

If the moving right index hasn’t reach this iteration’s fixed left index, recursively subsort the items between them. Similarly, if the moving left index hasn’t reached this iteration’s fixed right index, recursively subsort the items between them. Each iteration sorts a different area of the same list. If you specify, say, ‘myList’ as a parameter when you call QuickSort, ‘myList’ will be sorted by the end of the process. The ‘return a’ is thus a complete waste of time and I’d guess it wasn’t in Arthur’s original script.