get newRadio("sortBy", "card", "Items,Spaces,Lines")
if (it = empty) then get newRadio("sortInput", "card", "Random,Presort")
if (it = empty) then get newRadio("sortRules", "card", "Exact,Ignorecase,International,Numeric")
if (it Γëá empty) then answer("openCard: " & errorstring(it))
pass openCard
end openCard
on closeCard
if (debugging() = true) then pass closeCard
get disposeRadio("sortBy")
get disposeRadio("sortRules")
get disposeRadio("sortInput")
pass closeCard
end closeCard
-- Handler called to demonstrate a sorting method
on doSort method -- method is quicksort, shellsort, or treesort
set cursor to watch
put cd fld "input" into data
-- get separator to sort on
if (hilite of button "Lines" = true) then
put return into separator
put the number of lines of data into size
put "Input: (lines=" & size & ")" into cd fld "InputTitle"
else if (hilite of button "Spaces" = true) then
put space into separator
put the number of words of data into size
put "Input: (words=" & size & ")" into cd fld "InputTitle"
else if (hilite of button "Items" = true) then
put "," into separator
put the number of items of data into size
put "Input: (items=" & size & ")" into cd fld "InputTitle"
end if
put hilite of button "Presort" into presort
-- make sure size isn't so big we'll spend a year waiting for sort
if (method = "treesort" and presort and size > 256) then
answer "Sort may take a very very long time." with "Continue" or "Cancel"
if (it = "Cancel") then exit doSort
end if
-- get method for comparing items
put the short name of selectedRadio("sortRules") into compare
-- presort data if necessary
if (hilite of button "Presort" = true) then
put listSort(data, compare, separator, false) into data
end if
-- sort using appropriate method
put the ticks into start
if (method = "shellsort" or method = "quicksort") then
get listSort(data, compare, separator, false, method)
else if (method = "treesort") then
get treeSort(data, compare, separator, false)
else
-- error
end if
put the ticks - start into start
put it into card field "Output"
put "Sort took " & start / 60.0 & " seconds."
end doSort
-- part 16 (field)
-- low flags: 00
-- high flags: 0007
-- rect: left=260 top=174 right=234 bottom=509
-- title width / last selected line: 0
-- icon id / first selected line: 0 / 0
-- text alignment: 0
-- font id: 3
-- text size: 9
-- style flags: 0
-- line height: 12
-- part name: Input
-- part 17 (field)
-- low flags: 01
-- high flags: 0007
-- rect: left=260 top=253 right=315 bottom=509
-- title width / last selected line: 0
-- icon id / first selected line: 0 / 0
-- text alignment: 0
-- font id: 3
-- text size: 9
-- style flags: 0
-- line height: 12
-- part name: Output
-- part 18 (field)
-- low flags: 01
-- high flags: 0000
-- rect: left=262 top=57 right=72 bottom=318
-- title width / last selected line: 0
-- icon id / first selected line: 0 / 0
-- text alignment: 0
-- font id: 3
-- text size: 10
-- style flags: 256
-- line height: 13
-- part name:
-- part 19 (field)
-- low flags: 01
-- high flags: 0000
-- rect: left=262 top=76 right=91 bottom=318
-- title width / last selected line: 0
-- icon id / first selected line: 0 / 0
-- text alignment: 0
-- font id: 3
-- text size: 10
-- style flags: 256
-- line height: 13
-- part name:
-- part 22 (field)
-- low flags: 01
-- high flags: 0002
-- rect: left=260 top=238 right=254 bottom=509
-- title width / last selected line: 0
-- icon id / first selected line: 0 / 0
-- text alignment: 0
-- font id: 3
-- text size: 10
-- style flags: 256
-- line height: 13
-- part name:
-- part 29 (button)
-- low flags: 00
-- high flags: C006
-- rect: left=317 top=75 right=91 bottom=385
-- title width / last selected line: 0
-- icon id / first selected line: 0 / 0
-- text alignment: 1
-- font id: 3
-- text size: 10
-- style flags: 256
-- line height: 13
-- part name: Random
----- HyperTalk script -----
on mouseUp
clickRadio sortInput, the name of the target
end mouseUp
-- part 30 (button)
-- low flags: 00
-- high flags: 8006
-- rect: left=384 top=75 right=91 bottom=451
-- title width / last selected line: 0
-- icon id / first selected line: 0 / 0
-- text alignment: 1
-- font id: 3
-- text size: 10
-- style flags: 256
-- line height: 13
-- part name: Presort
----- HyperTalk script -----
on mouseUp
clickRadio sortInput, the name of the target
end mouseUp
-- part 32 (button)
-- low flags: 00
-- high flags: 8006
-- rect: left=450 top=56 right=72 bottom=505
-- title width / last selected line: 0
-- icon id / first selected line: 0 / 0
-- text alignment: 1
-- font id: 3
-- text size: 10
-- style flags: 256
-- line height: 13
-- part name: Lines
----- HyperTalk script -----
on mouseUp
clickRadio sortBy, the name of the target
end mouseUp
-- part 33 (button)
-- low flags: 00
-- high flags: C006
-- rect: left=317 top=56 right=72 bottom=385
-- title width / last selected line: 0
-- icon id / first selected line: 0 / 0
-- text alignment: 1
-- font id: 3
-- text size: 10
-- style flags: 256
-- line height: 13
-- part name: Items
----- HyperTalk script -----
on mouseUp
clickRadio sortBy, the name of the target
end mouseUp
-- part 34 (button)
-- low flags: 00
-- high flags: 8006
-- rect: left=384 top=56 right=72 bottom=451
-- title width / last selected line: 0
-- icon id / first selected line: 0 / 0
-- text alignment: 1
-- font id: 3
-- text size: 10
-- style flags: 256
-- line height: 13
-- part name: Spaces
----- HyperTalk script -----
on mouseUp
clickRadio sortBy, the name of the target
end mouseUp
-- part 36 (button)
-- low flags: 00
-- high flags: A003
-- rect: left=327 top=130 right=149 bottom=445
-- title width / last selected line: 0
-- icon id / first selected line: 0 / 0
-- text alignment: 1
-- font id: 3
-- text size: 10
-- style flags: 256
-- line height: 13
-- part name: Make Random Data
----- HyperTalk script -----
on mouseUp
ask "How many random numbers?" with 512
if (it = empty) then exit mouseUp
put it into count
set cursor to watch
repeat with i=1 to count
put random(9999) & "," after list
end repeat
delete last char of list
put list into card field "Input"
clickRadio "sortRules", the name of card button "Numeric"
end mouseUp
-- part 37 (button)
-- low flags: 00
-- high flags: A003
-- rect: left=262 top=25 right=47 bottom=339
-- title width / last selected line: 0
-- icon id / first selected line: 0 / 0
-- text alignment: 1
-- font id: 0
-- text size: 12
-- style flags: 0
-- line height: 16
-- part name: Quicksort
----- HyperTalk script -----
on mouseUp
doSort quicksort
end mouseUp
-- part 38 (button)
-- low flags: 00
-- high flags: A003
-- rect: left=344 top=25 right=47 bottom=416
-- title width / last selected line: 0
-- icon id / first selected line: 0 / 0
-- text alignment: 1
-- font id: 0
-- text size: 12
-- style flags: 0
-- line height: 16
-- part name: Shellsort
----- HyperTalk script -----
on mouseUp
doSort shellsort
end mouseUp
-- part 42 (button)
-- low flags: 00
-- high flags: C006
-- rect: left=317 top=94 right=110 bottom=385
-- title width / last selected line: 0
-- icon id / first selected line: 0 / 0
-- text alignment: 1
-- font id: 3
-- text size: 10
-- style flags: 256
-- line height: 13
-- part name: Exact
----- HyperTalk script -----
on mouseUp
clickRadio sortRules, the name of the target
end mouseUp
-- part 43 (button)
-- low flags: 00
-- high flags: 8006
-- rect: left=384 top=94 right=110 bottom=483
-- title width / last selected line: 0
-- icon id / first selected line: 0 / 0
-- text alignment: 1
-- font id: 3
-- text size: 10
-- style flags: 256
-- line height: 13
-- part name: Ignorecase
----- HyperTalk script -----
on mouseUp
clickRadio sortRules, the name of the target
end mouseUp
-- part 44 (button)
-- low flags: 00
-- high flags: 8006
-- rect: left=384 top=109 right=125 bottom=483
-- title width / last selected line: 0
-- icon id / first selected line: 0 / 0
-- text alignment: 1
-- font id: 3
-- text size: 10
-- style flags: 256
-- line height: 13
-- part name: International
----- HyperTalk script -----
on mouseUp
clickRadio sortRules, the name of the target
end mouseUp
-- part 45 (button)
-- low flags: 00
-- high flags: 8006
-- rect: left=317 top=109 right=125 bottom=385
-- title width / last selected line: 0
-- icon id / first selected line: 0 / 0
-- text alignment: 1
-- font id: 3
-- text size: 10
-- style flags: 256
-- line height: 13
-- part name: Numeric
----- HyperTalk script -----
on mouseUp
clickRadio sortRules, the name of the target
end mouseUp
-- part 46 (button)
-- low flags: 00
-- high flags: A003
-- rect: left=422 top=25 right=47 bottom=494
-- title width / last selected line: 0
-- icon id / first selected line: 0 / 0
-- text alignment: 1
-- font id: 0
-- text size: 12
-- style flags: 0
-- line height: 16
-- part name: Treesort
----- HyperTalk script -----
on mouseUp
doSort treesort
end mouseUp
-- part 47 (field)
-- low flags: 00
-- high flags: 0000
-- rect: left=262 top=95 right=110 bottom=318
-- title width / last selected line: 0
-- icon id / first selected line: 0 / 0
-- text alignment: 0
-- font id: 3
-- text size: 10
-- style flags: 256
-- line height: 13
-- part name:
-- part 48 (field)
-- low flags: 01
-- high flags: 0002
-- rect: left=260 top=159 right=175 bottom=509
-- title width / last selected line: 0
-- icon id / first selected line: 0 / 0
-- text alignment: 0
-- font id: 3
-- text size: 10
-- style flags: 256
-- line height: 13
-- part name: InputTitle
-- part contents for background part 9
----- text -----
DemoStack 0.9
-- part contents for background part 1
----- text -----
Sort
-- part contents for background part 12
----- text -----
Card #6
-- part contents for card part 18
----- text -----
Sort By:
-- part contents for card part 19
----- text -----
Input:
-- part contents for card part 22
----- text -----
Output:
-- part contents for background part 14
----- text -----
This card demonstrates the sorting functions of ArrayList and BinaryTree. ArrayList can sort using one of two algorithms: quick sort or shell sort. BinaryTree sorts by inserting the data and then traversing the tree in in-order. At the end of this description are results from some benchmarks comparing each method.
For random data, you will notice that quick sort is always the best algorithm to use. Even though tree sort uses nearly the same amount of key comparisons as quick sort does, it is slower due to the time needed to traverse the tree after inserting the items and due to other overhead incurred while maintaing the tree. Shell sort is excellent for presorted data, while quick sort will be much slower than on random data. Finally, the current version of BinaryTree is horrendous when called with presorted data.
Remember that ArrayList implements several enhancements to the basic quick sort algorithm, so that even if it is called on presorted data it will not degenerate to quadratic behavior.
ΓÇó Tip: To get the items in a list in reverse order use the top function of ArrayList.
________________________________
Trying it out
The buttons "Quicksort" and "Shellsort" and "Treesort" execute a sort on the data in the "Input" field. The "Input" field contains the data to be sorted, while the "Output" field contains the sorted output. The time taken by each sort is displayed in the message box. Notice that this time includes the work done to insert the items into the list or tree; if you weren't just sorting the data, but preparing it for further processing, then you'd only have to insert the data into the list once.
___________________
Sorting by different things
The set of radio buttons labeled "Sort By" is used to select the character that separates items. When "Lines" is selected items are separated by the return character; when "Spaces" is selected the space character separates items, and when "Items" is selected the comma character is used as the separator. Thus you can sort data by lines, words, or HyperCard items.
ΓÇó Note: The "Sort By" options specify the separator character used for the sort. In the case of a sort by spaces, words may not be sorted correctly, since some words will include return characters or tabs.
__________________
Sorted vs. Unsorted Input
The set of radio buttons labeled "Input" control the form of the input. If the "Random" button is selected then the input is sorted as is, without doing any preprocessing. If the "Presort" button is selected then the input is sorted once before the timed sort is run, and then the timed sort sorts this already sorted data. This is supposed to demonstrate that shell sort is better than quick sort if the data are already sorted.
__________________
Different sorting methods
The comparison buttons control the rules for comparing items. The exact option sorts items according to their precise ASCII ordering. Ignorecase sorts items so that letters are grouped properly in the sort. Numeric compares items as numbers. Finally, International will sort items so that letters with diacritics are in their correct positions (instead of sorting them by their ASCII values). An international sort results in slower execution.
____________
Input and Output
The "Make Random Data" button replaces the input with randomly generated integers.
_______________________________
Following are timing results from some tests (run on a standard Macintosh Plus).
