Re: Sorting IP addresses - Progress
Re: Sorting IP addresses - Progress
- Subject: Re: Sorting IP addresses - Progress
- From: Deivy Petrescu <email@hidden>
- Date: Sun, 21 Dec 2003 11:26:10 -0500
At 8:10 PM -0500 12/20/03, Graff wrote:
It turns out your quick sort implementation is
better than the one I adapted from that web
site. Your quick sort sorted 10,000 items in 72
seconds as opposed to 349 seconds for the quick
sort I adapted. Since my merge sort took 131
seconds for the same data set this means that
your quick sort is indeed the quickest sorting
implementation out of all of them for large data
sets.
- Ken
In reality, the shell sort , i.e. "sort -n -t.
..." is the fastest method and I'd think also the
easiest to program.
The only caveat, the file has to have Unix ending, not Mac ending.
However, of all the other sort routines the best
is Satimage's (Emmanuel's) or the French sort if
you will.
With a list of 1000 random items I get the
following times (using chrono, from Smile)
Ken Graff's version of the French sort ----> 11.359790000002
A variation of Graff's version ----> 71.947702000005 (*)
French sort ------------------------> 1.629958000005
A variation of French sort version -> 2.114130999995 (**)
Quicksort---------------------------> 7.056177000006
The variation is the following
Ken Graff's version of French Sort is:
on sort(listToSort)
if length of listToSort = 1 then return listToSort
set firstItem to item 1 of listToSort
set restOfList to rest of listToSort
set list1 to {}
set list2 to {}
repeat with currItem in restOfList
if firstItem < currItem then
set list2 to list2 &
currItem (*)(variation = set end list2 to
currItem )
else
set list1 to list1 &
currItem (*)variation = set end list1 to
currItem )
end if
end repeat
if length of list1 > 1 then set list1 to sort(list1)
if length of list2 > 1 then set list2 to sort(list2)
return list1 & firstItem & list2
end sort
Emmanuel's French Sort is:
on sort(lista)
set len to length of lista
if len <= 1 then return lista
set x to (item 1 of lista)
set lista to (rest of lista)
set lista1 to {}
set lista2 to {}
set len to length of lista
repeat with k from 1 to len
set j to (item k of lista)
if x < j then
set end of lista2 to j
(**)(variation = set list2 to list2 & j )
else
set end of lista1 to j
(**)(variation = set list1 to list1 & j)
end if
end repeat
if (length of lista1 > 1) and (length of lista2 > 1) then
return lista1 & x & lista2
else
return sort(lista1, tipo, field)
& x & sort(lista2, tipo, field)
end if
end sort
A very relevant point:
Using Serge Belleudy-d'Espinose trick (the
French list script??) of setting a list to a
script list (see below) actually slows up the
French sort. I did not tried it with other
scripts, since the time difference is significant.
here is the trick, and the FSR version of the trick:
____
script scpt
property mtrz : {}
end script
script scpt1
property mtrz : {}
end script
script scpt2
property mtrz : {}
end script
set lista to sort(lista)
return chrono
on sort(lista)
if length of lista <= 1 then return lista
set scpt's mtrz to lista
set x to item 1 of scpt's mtrz
set scpt's mtrz to rest of scpt's mtrz
set scpt1's mtrz to {}
set scpt2's mtrz to {}
repeat with i in scpt's mtrz
if x < i then
set scpt2's mtrz to scpt2's mtrz & i
else
set scpt1's mtrz to scpt1's mtrz & i
end if
end repeat
set l2 to scpt2's mtrz
set l1 to scpt1's mtrz
return sort(l1) & x & sort(l2)
end sort
____
--
Regards
Saudagues
Deivy
http://www.dicas.com
_______________________________________________
applescript-users mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/applescript-users
Do not post admin requests to the list. They will be ignored.