Sorting algorithms/Quicksort: Difference between revisions

Content added Content deleted
Line 896: Line 896:
===Straightforward===
===Straightforward===


Emphasising clarity, simplicity, performance, ''and'' correct AppleScript:
Emphasising clarity, quick sorting, ''and'' correct AppleScript:


<lang applescript>(* Quicksort (basic algorithm)
<lang applescript>-- In-place Quicksort (basic algorithm).
Algorithm: S.A.R. (Tony) Hoare, 1960.
-- Algorithm: S.A.R. (Tony) Hoare, 1960.
⚫
on quicksort(theList, l, r) -- Sort items l thru r of theList.
*)
⚫
set listLength to (count theList)

if (listLength < 2) then return
-- Sort range l thru r of a list, in place.
⚫
-- Convert negative and/or transposed range indices.
⚫
on quicksort(theList, l, r)
⚫
if (l < 0) then set l to listLength + l + 1
script o -- Script object containing both the target list and the recursive process.
⚫
if (r < 0) then set r to listLength + r + 1
⚫
if (l > r) then set {l, r} to {r, l}
⚫
-- Script object containing the list as a property (to allow faster references to its items)
-- and the recursive subhandler.
script o
property lst : theList
property lst : theList
Line 912: Line 918:
set j to r
set j to r
repeat until (i > j)
repeat until (i > j)
set leftValue to my lst's item i
set lv to my lst's item i
repeat while (leftValue < pivot)
repeat while (pivot > lv)
set i to i + 1
set i to i + 1
set leftValue to my lst's item i
set lv to my lst's item i
end repeat
end repeat
set rightValue to my lst's item j
set rv to my lst's item j
repeat while (rightValue > pivot)
repeat while (rv > pivot)
set j to j - 1
set j to j - 1
set rightValue to my lst's item j
set rv to my lst's item j
end repeat
end repeat
if (j > i) then
if (j > i) then
set my lst's item i to rightValue
set my lst's item i to rv
set my lst's item j to leftValue
set my lst's item j to lv
else if (i > j) then
else if (i > j) then
exit repeat
exit repeat
Line 940: Line 946:
end script
end script
set listLength to (count theList)
tell o to qsrt(l, r)
⚫
if (listLength > 1) then
⚫
-- Convert negative and/or transposed range indices.
⚫
if (l < 0) then set l to listLength + l + 1
⚫
if (r < 0) then set r to listLength + r + 1
⚫
if (l > r) then set {l, r} to {r, l}
⚫
-- Do the sort.
tell o to qsrt(l, r)
end if
return -- nothing. The input list has been sorted in place.
return -- nothing.
end quicksort
end quicksort
property sort : quicksort
property sort : quicksort


-- Test code:
-- Demo:
local aList
set aList to {28, 9, 95, 22, 67, 55, 20, 41, 60, 53, 100, 72, 19, 67, 14, 42, 29, 20, 74, 39}
set aList to {28, 9, 95, 22, 67, 55, 20, 41, 60, 53, 100, 72, 19, 67, 14, 42, 29, 20, 74, 39}
sort(aList, 1, -1) -- Sort the entire list.
sort(aList, 1, -1) -- Sort items 1 thru -1 of aList.
return aList</lang>
return aList</lang>


{{output}}
{{output}}
<lang applescript>{9, 14, 19, 20, 20, 22, 28, 29, 39, 41, 42, 53, 55, 60, 67, 67, 72, 74, 95, 100}</lang>
<lang applescript>{9, 14, 19, 20, 20, 22, 28, 29, 39, 41, 42, 53, 55, 60, 67, 67, 72, 74, 95, 100}</lang>

=={{header|Arc}}==
=={{header|Arc}}==
<lang Arc>(def qs (seq)
<lang Arc>(def qs (seq)
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Quicksort"